第六章、可归约性.ppt

计算理论导引 第二部分 可计算理论 第6章 可归约性 可归约性-1 归约 就是将一个问题转化为另一个问题的方法，使得可以用第二个问题的解来解第一个问题。 例如，假设要在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。 可归约性 总是涉及到两个问题，称之为A和B。如果A可归约到B，就可用B的解来解A。可归约性说的不是怎样去解A或B，而是在知道B的解时怎么去解A。在上述例子中，A是城市认路问题，B是得到地图问题。 可归约性-2 数学问题中也有可归约性。例如，测量一个矩形的面积问题可归约到测量它的高和宽问题。 当A可归约到B时，解A不可能比解B更难，因为B的一个解给出了A的一个解。 根据可计算性理论， 如果A可归约到B，且B是可判定的，则A也是可判定的。 如果A是不可判定的．A可归约到B，则B是不可判定的。 后者在证明许多问题的不可判定性时起着关键作用。 6.1 语言理论中的不可判定问题-1 简单地说，下面方法可用来证明一个问题是不可解的：先证明另外一个问题是不可判定的，再将此问题归约到它。 ATM是不可判定的，即确定一个图灵机是否接受一个给定的输入问题是不可判定的。下面考虑一个与之相关的问题：HALTTM，即确定一个图灵机对给定的输入是否停机(通过接受或拒绝)问题。 6.1 语言理论中的不可判定问题-2 定理6.1 HALTTM是不可判定的。 HALTTM＝{＜M，w＞M是一个TM，且对输入w停机 } 证明思路 假设TM R判定HALTTM 。利用R可以构造一个判定ATM的TM S。假装你就是S。当形如＜M，w＞的一个输入提供给你时： 如果M接受w，你必须输出接受； 如果M进入循环或拒绝w，你必须输出拒绝。 6.1 语言理论中的不可判定问题-3 但是你不能确定M是否在循环，并且当M循环时，你的模拟将不会终止。故这个思路行不通。 换用“有个判定HALTTM的TM R”这个假设。使用R，你可以检查M对w是否停机： 如果R指出M对w不停机，你就拒绝，因为＜M，w＞不在ATM中。 如果R指出M对w确实停机，你就模拟它，而不会有死循环的危险。 这样，如果TM R存在，就能判定ATM， 6.1 语言理论中的不可判定问题-4 证明 假设TM R判定HALTTM，构造TM S来判定ATM： S＝“在输入＜M，w＞上，此处＜M，w＞是TM M和串w的编码： 在输入＜M，w＞上运行TM R。 如果R拒绝(不停机)，则拒绝。 如果R接受．则在w上模拟M，直到它停机。 如果M接受，则接受；如果M拒绝，则拒绝。” 显然，如果R判定HALTTM，则S判定ATM。因为ATM是不可判定的，故HALTTM也必定是不可判定的。 6.1 语言理论中的不可判定问题-5 ETM＝{＜M＞| M是一个TM，且L(M)＝Φ} 定理6.2 ETM是不可判定的。 证明思路：设R是判定ETM的一个TM．考虑怎样用R来构造判定ATM的TM S。构造S的一个想法是：在输入＜M＞上运行R且看它是否接受： 如果是．则知道L(M)是空集，因此也就知道M不接受w。 如果否，则知道L(M)不是空集，即M接受某个串，但不知道M是否接受这个特定的串w。 6.1 语言理论中的不可判定问题-7 修改＜M＞，使得M所能识别的唯一的串就是w。故它的语言不空当且仅当它接受w 。 再用R来检查这个修改型是否识别空语言。 如果它接受，则此修改型机器不接受任何串，因而M也就不接受 w。 如果它拒绝，此修改型机器只接受w，因而M也就接受w。 6.1 语言理论中的不可判定问题-8 证明 修改型机器M1。 M1＝“在输入x上， 如果x≠w，则拒绝。 如果x＝w，则在x上运行M，当M接受时，就接受，” 这个机器以w作为它的描述的一部分。检查x=w是否成立的方法很显然，即扫描输入并且一个字符一个字符地将它和w比较，就可确定它们是否相同。 再假设TM R判定ETM。如下构造判定ATM的TM S： 6.1 语言理论中的不可判定问题-9 S＝“在输入＜M，w＞上，此处＜M，w＞是TM M和串w的编码： 用M和w的描述来构造上述TM M1。 在输入＜M1＞上运行R。 如果R接受(空语言)、则拒绝；如果R拒绝，则接受。” 如果R是ETM的判定器，则S就是ATM的判定器。而ATM的判定器是不存在的，故我们知道ETM必定是不可判定的。 6.1 语言理论中的不可判定问题-10 REGULARTM＝{＜M＞M是一个TM，且L(M)是一个正则语言} 定理6.3 REGULARTM是不可判定的。 证明思路 假设REGULARTM是由TM R判定的，构造一个判定ATM的TM S。构造S的思路是：先取S的输