第六章：可规约性.ppt

*计算理论第六章可归约性*前言本章讨论另外几个不可解的问题。在讨论过程中,将介绍一个基本方法,可用来证明问题是计算上不可解的,这个方法称为可归约性。归约旨在将一个问题转化为加一个问题,且使得可以用第二个问题的解来解第一个问题,在日常生活中,虽然不这样称呼,但时常会遇见可归约性问题。例如,在一个新城市中认路,如果有一张地图,事情就容易了。这样,就将在城市认路问题归约为得到地图问题。*前言可归约性总是涉及两个问题,称之为A和B。如果A可归约到B,就可用B的解来解A。可归约性说的不是怎样去解A或B,而是在知道B的解时怎么去解A。归约的目的在于:将一个问题转化为另一个问题;且用第二个问题的解来解第一个问题。归约的应用(A可归约到B)如果B是可判定的,则A也是可判定的。如果A是不可判定的,则B也是不可判定的。*(自学) *语言理论中的不可判定问题ATM={<M,w>|M是一个TM,且接受w}ATM是不可判定的,即确定一个图灵机是否接受一个给定的输入问题是不可判定的。下面考虑一个与之相关的问题:HALTTM,即确定一个图灵机对给定输入是否停机(通过接受或拒绝)问题。若将ATM归约到HALTTM,就可以利用ATM的不可判定性证明HALTTM的不可判定性。HALTTM的形式化描述HALTTM={<M,w>|M是一个TM,且对输入w停机}*。证明思路:反证法。(将ATM归约到HALTTM)假设TMR判定HALTTM,利用R可以构造一个判定ATM的TMS。使用R,可以检查M对w是否停机,如果M对w不停机,S就拒绝,因为<M,w>不在ATM中。如果M对w确实停机,S就模拟它,而不会有死循环的危险。这样,如果TMR存在,就能判定ATM。*。假设TMR判定HALTTM,由之可以构造TMS来判定ATM,其构造如下:S=“在输入<M,w>上,此处<M,w>是TMM和串w的编码:1)在输入<M,w>上运行TMR。2)如果R拒绝,则拒绝。3)如果R接受,则在w上模拟M,直到它停机。4)如果M已经接受,则接受;如果M已经拒绝,则拒绝。”显然,如果R判定HALTTM,则S判定ATM。因为ATM是不可判定的,故HALTTM也必定是不可判定的。*。假设ETM是可判定的,以此证明ATM是可判定的。设R是判定ETM的一个TM,考虑用R来构造判定ATM的S。当S收到输入<M,w>时,如何运行?构造S的一个想法是:输入<M>上运行R且看它是否接受。如果是,知道L(M)是空集,因此M不接受w。如果R拒绝w,则只知道L(M)不空,即M接受某个串,但是不知道是否接受这个特定的w。因此,不能在<M>上运行R。目标:修改<M>,使得除了w外,M对所有串都拒绝。ETM={M|M是一个TM,且L(M)=}空问题*。=“在输入x上: 1)如果x≠w,则拒绝。 2)如果x=w,则在x上运行M,当M接受时,就接受。”这个机器以w作为它的描述的一部分。检查x=w是否成立的方法很显然,即扫描输入并用一个字符一个字符地将它与w进行比较,就可确定它们是否相同。ETM={M|M是一个TM,且L(M)=}空问题*语言理论中的不可判定问题再假设TMR判定ETM。如下构造判定ATM的TMS:S=“在输入<M,w>上,此处<M,w>是TMM和串w的编码: 1)用M和w的描述来构造上述TMM1。 2)在输入<M1>上运行R。 3)如果R接受,则拒绝;如果R拒绝,则接受。”如果R是ETM的判定器,则S就是ATM的判定器。而ATM的判定器是不存在的,故ETM必定是不可判定的。。ETM={M|M是一个TM,且L(M)=}空问题