第六章、可归约性

1、1,第二部分 可计算理论,第6章 可归约性,2,可归约性-1,归约 就是将一个问题转化为另一个问题的方法，使得可以用第二个问题的解来解第一个问题。例如，假设要在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。 可归约性 总是涉及到两个问题，称之为A和B。如果A可归约到B，就可用B的解来解A。可归约性说的不是怎样去解A或B，而是在知道B的解时怎么去解A。在上述例子中，A是城市认路问题，B是得到地图问题。,3,可归约性-2,数学问题中也有可归约性。例如，测量一个矩形的面积问题可归约到测量它的高和宽问题。 当A可归约到B时，解A不可能比解B更难，因为B的一

2、个解给出了A的一个解。 根据可计算性理论， 如果A可归约到B，且B是可判定的，则A也是可判定的。 如果A是不可判定的A可归约到B，则B是不可判定的。 后者在证明许多问题的不可判定性时起着关键作用。,4,6.1 语言理论中的不可判定问题-1,简单地说，下面方法可用来证明一个问题是不可解的：先证明另外一个问题是不可判定的，再将此问题归约到它。 ATM是不可判定的，即确定一个图灵机是否接受一个给定的输入问题是不可判定的。下面考虑一个与之相关的问题：HALTTM，即确定一个图灵机对给定的输入是否停机(通过接受或拒绝)问题。,5,6.1 语言理论中的不可判定问题-2,定理6.1 HALTTM是不可判定的

3、。 HALTTMM，wM是一个TM，且对输入w停机 证明思路 假设TM R判定HALTTM 。利用R可以构造一个判定ATM的TM S。假装你就是S。当形如M，w的一个输入提供给你时： 如果M接受w，你必须输出接受； 如果M进入循环或拒绝w，你必须输出拒绝。,6,6.1 语言理论中的不可判定问题-3,但是你不能确定M是否在循环，并且当M循环时，你的模拟将不会终止。故这个思路行不通。 换用“有个判定HALTTM的TM R”这个假设。使用R，你可以检查M对w是否停机： 如果R指出M对w不停机，你就拒绝，因为M，w不在ATM中。 如果R指出M对w确实停机，你就模拟它，而不会有死循环的危险。 这样，如果

4、TM R存在，就能判定ATM，,7,证明 假设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 语言理论中的不可判定问题-4,8,ETMM| M是一个TM，且L(M) 定理6.2 ETM是不可判定的。 证明思路：设R是判定ETM的一个TM考虑怎样用R来构造判定ATM的TM S。构

5、造S的一个想法是：在输入M上运行R且看它是否接受： 如果是则知道L(M)是空集，因此也就知道M不接受w。 如果否，则知道L(M)不是空集，即M接受某个串，但不知道M是否接受这个特定的串w。,6.1 语言理论中的不可判定问题-5,9,修改M，使得M所能识别的唯一的串就是w。故它的语言不空当且仅当它接受w 。 再用R来检查这个修改型是否识别空语言。 如果它接受，则此修改型机器不接受任何串，因而M也就不接受 w。 如果它拒绝，此修改型机器只接受w，因而M也就接受w。,6.1 语言理论中的不可判定问题-7,10,证明 修改型机器M1。 M1“在输入x上， 如果xw，则拒绝。 如果xw，则在x上运行M，

6、当M接受时，就接受，” 这个机器以w作为它的描述的一部分。检查x=w是否成立的方法很显然，即扫描输入并且一个字符一个字符地将它和w比较，就可确定它们是否相同。 再假设TM R判定ETM。如下构造判定ATM的TM S：,6.1 语言理论中的不可判定问题-8,11,S“在输入M，w上，此处M，w是TM M和串w的编码： 用M和w的描述来构造上述TM M1。 在输入M1上运行R。 如果R接受(空语言)、则拒绝；如果R拒绝，则接受。” 如果R是ETM的判定器，则S就是ATM的判定器。而ATM的判定器是不存在的，故我们知道ETM必定是不可判定的。,6.1 语言理论中的不可判定问题-9,12,REGULA

7、RTMMM是一个TM，且L(M)是一个正则语言 定理6.3 REGULARTM是不可判定的。 证明思路 假设REGULARTM是由TM R判定的，构造一个判定ATM的TM S。构造S的思路是：先取S的输入为M，w，再修改M使得：修改后的TM识别一个正则语言，当且仅当M接受w。,6.1 语言理论中的不可判定问题-10,13,设计M2使得：当M不接受w时，它识别非正则语言0n1n|n0；当M接受w时，它识别正则语言*。必须说明S是怎样从M和w来构造这样的M2的。方法是：M2自动接受所有在0n1n|n0中的串，另外，如果M还接受w，则M2就接受所有其它的串。 证明 设R是判定REGULARTM的一个

8、TM，构造判定ATM的TM S。,6.1 语言理论中的不可判定问题-11,14,S“对于输入M，w，其中M是TM，w是串： 构造下述TM M2： M2=“在输入x上： 如果x具有形式0n1n，则接受。 如果x不具有此形式，则在输入w上运行M。如果M接受w，则接受。” 在输入M2上运行R。 如果R接受，则接受；如果R拒绝，则拒绝。”,6.1 语言理论中的不可判定问题-12,15,定理6.4 EQTM是不可判定的。 EQTMM1，M2|M1和M2都是TM，且L(M1)L(M2) 证明思路 假设EQTM是可判定的。如果能给出从ETM到EQTM的归约，就证明了ETM也是可判定的。 ETM是检查一个TM

9、的语言是否为空的问题。EQTM是检查两个TM的语言是否相同的问题。,6.1 语言理论中的不可判定问题-13,16,如果两个语言中碰巧有一个为空，只要检查另一个TM的语言是否为空即可，即检查语言ETM。故当两个TM中有一个是用来识别空语言时，问题EQTM 就是问题ETM。 证明 设TM R判定EQTM，构造判定ETM的TM S：,6.1 语言理论中的不可判定问题-14,17,S“对于输入M，其中M是TM； 在输入M，M1上运行R其中M1是拒绝所有输入的图灵机。 如果R接受，则接受；如果R拒绝，则拒绝。” 如果R判定EQTM，则S判定ETM。但由定理6.2，ETM是不可判定的。故EQTM也必定是不

10、可判定的。,6.1 语言理论中的不可判定问题-15,18,计算历史方法是证明ATM可归约到某些语言的重要技术。在证明某个问题的不可判定性时，如果此问题涉及的是检查某样东西的存在性，则这个方法常常很有用。例如，这个方法曾用来证明希尔伯特第十问题的不可判定性。希尔伯特第十问题是检查一个多项式的整数根的存在性。 图灵机在输入上的计算历史就是当这个图灵机处理此输入时所经过的格局序列。它是这个机器所经历的计算的完整记录。,6.1 利用计算历史的规约-1,19,定义6.5 设M是一个图灵机，w是一个串。M在w上的一个接受计算历史是一个格局序列C1，C2，Cl，其中：C1是M在w上的起始格局，Cl是M的一个

11、接受格局且每个Ci都是Ci-1的合法结果，即符合M的规则。 M在w上的一个拒绝计算历史可类似定义，只是Cl应是一个拒绝格局。,6.1 利用计算历史的规约-2,20,计算历史都是有限序列。如果M在w上不停机，则M在w上既没有接受也没有拒绝计算历史存在。确定型机器在任何给定的输入上最多只有一个计算历史。非确定型机器即使在单个输入上也可能有多个计算历史，它们与各个计算分支相对应。 定义6.6 线性界限自动机(LBA) 是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点(两个特殊字符)，则读写头就待在原地不动。,6.1 利用计算历史的规约-3,2

12、1,线性界限自动机是只有有限存储的图灵机，如图6-l所示。它只能解这样的问题，其所需要的存储不得超过用作输入的带区域。使用一个比输入字母表要大一些的带字母表，就能使得可用存储增加到常数倍。也就是说，对于长度为n的输入，可用存储量关于n是线性的。这就是此模型的名称的由来。,6.1 利用计算历史的规约-4,22,设ALBA是LBA是否接受它的输入的问题。尽管ALBA与不可判定问题ATM在图灵机被限制为LBA时是相同的，我们还是可以证明ALBA是可判定的。设 ALBAM，w|M是一个接受串w的LBA 在证明ALBA的可判定性之前，证明后面的引理是有用的。它指出：当一个LBA的输入是一个长度为n的串时

13、，只能有有限多个格局。,6.1 利用计算历史的规约-5,23,引理6.7 设M是有q个状态和g个带符号的LBA。对于长度为n的带子，M恰有qngn个不同的格局。 证明 M的格局就像计算中间的一个快相。 格局由控制状态、读写头位置和带内容组成。这里，M有q个状态。它的带长度是n，所以读写头可能处于n个位置之一，且gn多个带符号串可能出现在带上。此三个量的乘积就是带长为n的M的格局总数。,6.1 利用计算历史的规约-6,24,定理6.8 ALBA是可判定的。 证明思路 为了判定LBA是否接受输入w，在w上模拟M。在模拟过程中，如果M停机且接受或拒绝，则相应地接受或拒绝。如果M在w上循环，困难就出现

14、了。只有知道已进入循环时，才能停机且拒绝。调查M何时陷入循环的思路是：当M在w上计算时，它从一个格局进入另一个格局。如果M曾经重复过一个格局，它将继续一再地重复这个格局，因此就陷入了循环。,6.1 利用计算历史的规约-7,25,因为M是一个LBA，可利用的带方格的数量是有限的。由引理6.7，在这个有限量的带上， M只可能处于有限多个格局中。所以，要使M不进入曾经进入过的任何格局，就只有有限多个格局可以选择。引理6.7给出了所能选择的最大格局数k，通过在M上模拟k步就能知道M是否进入了循环。如果到那时，M还没有停机，它肯定陷入了循环。,6.1 利用计算历史的规约-8,26,证明 判定ALBA的算

15、法如下： L“对于输入M，w其中M是LBA，w是串： 在w上模拟M qngn步，或者直到它停机。 如果M停机，则当它接受时接受，拒绝时拒绝。如果它还没有停机，就拒绝。” 如果M在w上运行qngn步还没有停机，根据引理6.7，它必定在重复某个格局，即陷入了循环。这就是算法为什么在此情形下拒绝的原因。,6.1 利用计算历史的规约-9,27,定理6.9 ELBA是不可判定的。 ELBAM|M是一个LBA，且L(M) 证明思路 证明使用从ATM出发的归约。要证明：如果ELBA是可判定的，则ATM也是可判定的。现在假设ELBA是可判定的，怎么使用这个假设来判定ATM呢?对于TM M和输入串w，构造一个L

16、BA B，再检查L(B)是否为空，就可确定M是否接受w。,6.1 利用计算历史的规约-10,28,B识别的语言构成了M在w上的所有接受计算历史。如果M接受w，这个语言就包含一个串，因此是非空的。如果M不接受w，这个语言就是空的。如果能确定B的语言是否为空，显然就能确定M是否接受w。 现在描述怎样从M和w构造B。注意，不仅仅需要证明B的存在性，还必须构造一个图灵机，它能从给定的M和w的描述，产生B的描述。,6.1 利用计算历史的规约-11,29,设x是M在w上的一个接受计算历史，构造B，使之接受输入x。回忆一下，M的一个接受计算历史是，M在接受串w时，经历的格局序列C1，C2， Cl 。出于证明

17、的需要，将接受计算历史表示成单个串，格局间以符号#相互隔开。,6.1 利用计算历史的规约-12,30,LBA B如下运行。如果x是M在w上的一个接受计算历史，则当B收到输入x时，应该接受。首先，B根据分界符将x分解为串C1，C2， Cl。然后B检查Ci是否满足计算历史的三个条件； C1是M在w上的起始格局。 每个Ci+1都是Ci的合法结果。 Cl是M的一个接受格局。,6.1 利用计算历史的规约-13,31,M在w上的起始格局应该是串q0 w1 w2wn，其中q0是M在w上的起始状态。这个串是直接装在B中的，所以B能够检查第一个条件 。接受格局是包含状态qaccept的格局。所以B只要通过扫描C

18、l看能否找到qaccept，就可检查第三个条件。第二个条件的检查是最困难的。对每对相邻的格局，B要检查Ci+1是否为Ci的合法结果。这个步骤包括：,6.1 利用计算历史的规约-14,32,除了Ci中读写头下位置及其相邻位置外，验证Ci和Ci+1是相同的，而上述几个位置必须根据转移函数来更新。B通过在Ci和Ci+1的相应位置间来回移动，验证更新是否适当。为了在来回移动时跟踪当前位置，B用点在带上标记当前位置。如果条件1、2和3都满足，则B接受输入。,6.1 利用计算历史的规约-15,33,图6-3是检查这样一个TM计算历史的示意图。,6.1 利用计算历史的规约-16,34,证明 现在构造从ATM

19、到ELBA的归约。假设TM R判定ELBA。如下构造判定ATM的TM S： S“对于输入M，w，其中M是TM，w是串： 如在证明思路中所描述的那样从M和w构造LBA B； 在输入B上运行R。 如果R拒绝，则接受；如果R接受，则拒绝。”,6.1 利用计算历史的规约-17,35,如果R接受B，则L(B)。M在w上就没有接受计算历史，M也就不接受w。因此，S就拒绝M，w。 类似地，如果R拒绝B，则B的语言不空。B能够接受的唯一串，是M在w上的接受计算历史。这样，M必定接受w。相应地，S也就接受M，w。,6.1 利用计算历史的规约-18,36,定理5.7证明了ECFG是一个可判定语言，现在要证明ALL

20、CFG是不可判定的。即检查一个上下文无关文法是否派生所有可能的串。 定理6.10 ALLCFG是不可判定的。 ALLCFG=G|G是一个CFG且L(G)* 证明 用反证法。为得到矛盾，假设ALLCFG是可判定的，用这个假设来证明ATM是可判定的。,6.1 利用计算历史的规约-19,37,现在来描述怎样运用ALLCFG的判定过程来判定ATM。对于TM M和输入串w，首先构造一个CFG G，使得它派生所有串当且仅当M不接受w。所以，如果M接受w，则存在一个特别的串，G不派生它。这个串应该是M在w上的计算历史。即：设计G，使之派生所有不是M在w上接受计算历史的串。 为了使得CFG G派生所有不是M在

21、w上接受计算历史的串，采用下面的策略。,6.1 利用计算历史的规约-20,38,将M在w上的接受计算历史表示成#C1#C2#Cl#，其中Ci是M在w上计算的第i步的格局。然后G派生出满足下述条件的所有串： 不以C1开始。 不以一个接受格局结束。 在M的规则下，某个Ci不恰好派生Ci+1。 如果M不接受w，就没有接受计算历史存在故所有串都因这样或那样的问题而不能成为接受计算历史，因此G将派生所有串，此正是所希望的。,6.1 利用计算历史的规约-21,39,6.1 利用计算历史的规约-22,假设ALLCFG是可判定的，即有TM R判定 ALLCFG=G|G是一个CFG且L(G)*。 在输入G上运行

22、R。 如果R接受，那么G派生所有可能的串，即所有可能的串中没有接受计算历史，则M不接受w。 如果R拒绝，那么G不派生所有可能的串，即所有可能的串中有接受计算历史，则M接受w。,40,构造一个PDA D，因为可以使用定理3.12中的构造将D转换为一个CFG，这样做是因为设计一个PDA要比设计一个CFG容易。D以非确定的分支计算开始，猜测前面的三个条件是否满足。 检查输入串的开始部分是否为C1，如果不是，则接受。 检查输入串是否以一个包含接受状态qaccept的格局结束，如果不是，则接受。,6.1 利用计算历史的规约-23,41,如果某个Ci不恰好派生Ci+1，就接受。其工作方式如下：首先扫描输入

23、，直到它非确定性地确定它已到达Ci。第二步，它将Ci推进栈里，直至由符号#标记的结尾。第三步，D弹出栈与Ci+1比较。除了读写头附近位置外，它们应该相同。读写头附近位置的更改应由M转移函数决定。最后，如果发现不匹配或不适当的更改，D就接受。,6.1 利用计算历史的规约-24,42,这个思路的问题是当D将Ci弹出栈时，它处于相反的顺序，因而不适合与Ci+1比较。换一种方法来写接受计算历史，使得每隔一个格局就以相反的顺序出现。奇数位置保持以向前的顺序写，但偶数位置向后写。,6.1 利用计算历史的规约-25,43,6.2 一个简单的不可判定问题-1,波斯特对应问题（PCP）每个骨牌由两个串构成，一边

24、一个。单个骨牌看上去象 一簇骨牌看起来象 任务是将这些骨牌进行排列(允许重复)，使得在阅读顶部符号后得到的串与阅读底部符号后得到的串相同。这样的排列称为一个匹配。例如，下面的排列就是这个游戏的一个匹配。,44,可以将骨牌变形，使得顶部和底部对应符号整齐地排列，以此更容易表示匹配。 对某些骨牌簇，不可能找到这样的匹配。例如：簇,6.2 一个简单的不可判定问题-2,45,波斯特对应问题：确定一簇骨牌是否有一个匹配。这个问题在算法上是不可解的。骨牌簇 P是PCP的一个实例： 匹配是一个序列i1, i2, ik, 使得 问题是确定P是否有匹配。令 PCPP|P是波斯特对应问题的一个实例，且P 有匹配,

25、6.2 一个简单的不可判定问题-3,46,定理6.11 PCP是不可判定的。 证明思路 由ATM出发利用接受计算历史的归约。证明从任意的TM M和输入w都能构造一个实例P，使得匹配都是M在w上的接受计算历史。这样，如果能确定这个实例是否有个匹配，就能确定M是否接受w。 但是怎么构造P使得匹配都是M在w上的接受计算历史呢?,6.2 一个简单的不可判定问题-4,47,在P中选择骨牌，使得：每形成一个匹配，便模拟一次M。且匹配中，每个骨牌都将一个格局中的一个或多个位置与下一个格局中的相应位置连接起来。 在构造之前，先处理两个小的技术要点。 为了方便P的构造，假设M在w上从不试图将它的读写头移出带的左

26、端点。这要求首先改变M以防止这样的行为。,6.2 一个简单的不可判定问题-5,48,修改PCP，要求匹配都从第一个骨牌开始，即： 稍后将说明怎么去掉这个要求。称这个问题为修改后的波斯特对应问题，或MPCP。设 MPCPP|P是波斯特对应问题的一个实例， P有一个从第一个骨牌开始的匹配 现在进入证明细节，即设计P来模拟M在w上的动作。,6.2 一个简单的不可判定问题-6,49,显然，第一个骨牌一定包含起始格局串：#q0w1w2wn# 构造骨牌： 使得模拟一次M，即根据M的转移函数定义的规则，从一个格局转换到下一个格局时，就增加一个骨牌。这个骨牌将当前格局中的一个或多个位置与下一个格局中的相应位置

27、连接起来。此外，还需构造一些辅助性骨牌。,6.2 一个简单的不可判定问题-7,50,形成匹配：从第一个骨牌开始，模拟一次M，就在P中选择一个对应的骨牌，直至M到达停机状态。如果出现了接受状态。则选择其它辅助性骨牌最终形成匹配。 证明 假设TM M判定PCP。构造S来判定ATM，令 M(Q，q0，qaccept，qreject) 其中Q，分别是M的状态集、输入字母表、带字母表和转移函数。,6.2 一个简单的不可判定问题-8,51,S构造PCP的一个实例P，使得P有一个匹配当且仅当M接受w。为此，S首先构造MPCP的一个实例P。下面以七个部分来描述这个构造。每个部分完成在w上模拟M的一个特定方面。

28、 第1部分：构造以下列方式开始： 将 放入P作为第一张骨牌,6.2 一个简单的不可判定问题-9,52,P是MPCP的一个实例，故匹配必须以这张骨牌开始。底部串以M在w上接受计算历史中的第一个格局Clq0 w1 w2wn开始。如图6-5所示。 到目前为止，只得到一个部分匹配，其底部串由C1#q0 w1 w2wn#构成，顶部串只有# 。,6.2 一个简单的不可判定问题-10,53,为获得匹配，必须扩展顶部串来匹配底部串。用新骨牌来作这样的扩展。这些新的骨牌强迫模拟M的一次单步运行，使得M的下一个格局出现在底部串的扩展中。 第2、3和4部分在P中增加的骨牌在模拟中起主要作用。第2部分处理读写头向右运

29、动，第3部分处理读写头向左运动，第4部分处理不与读写头相邻的带方格。,6.2 一个简单的不可判定问题-11,54,第2部分：对于每一个a，b和q，r Q，其中qqreject ，如果(q，a)=(r，b，R)，则将 放入P中。 第3部分：对于每一个a，b，c和q，rQ，其中qqreject ，如果(q，a)=(r，b，L)，则将 放入P中。 第4部分：对于每一个a ，将 放入P中。,6.2 一个简单的不可判定问题-12,55,现补充一个虚拟的例子来说明到目前为止我们已经建造了什么。 设 =0，1，2，。假设w是串0100，M的起始状态是q0。在状态q0且读0时，假设转移函数指示M进入状态q7，

30、在带上写下2，并将它的读写头向右移动。换句话说，(q0，0)=(q7，2，R)。,6.2 一个简单的不可判定问题-13,56,第1部分将如下骨牌放入P中： 且匹配以如下方式开始： 另外，因为(q0，0)=(q7，2，R) ，第2部分放置如下骨牌：,6.2 一个简单的不可判定问题-14,57,因为0，1，2， 是的成员，故第4部分将下列骨牌放入P中： 这一步与第5部分一起使得匹配得到如下扩展：,6.2 一个简单的不可判定问题-15,58,这样，第2、3和4部分的骨牌，使得我们能够通过“在第一个格局之后增加第二个格局”的方法来扩展匹配。希望这个过程能够继续下去，即增加第三个格局，然后第四个格局，等

31、等。为此，需要增加一个新的骨牌来复制符号#。 第5部分：将 和 放入P中 第一个骨牌使我们能复制符号#，它是分隔格局的标记。第二个骨牌使我们能在格局的末端增加一个空白符，以此来模拟右边的无限多个空格，这些空格在写格局时被压缩了。,6.2 一个简单的不可判定问题-16,59,接着上面的例子假设在状态q7且读1时，M进入状态q5，在带上写下0，并将读写头向右移动。换句话说，(q7，1)(q5，0，R)。则在P中有骨牌 最后的那个匹配被扩展到,6.2 一个简单的不可判定问题-17,60,假设在状态q5且读0时，M进入状态q9，在带上写下2，并将读写头向左移动。换句话说，(q5，0)(q9，2，L)。

32、则在P中有骨牌 因为读写头左边的符号是0。前面的部分匹配就被扩展成,6.2 一个简单的不可判定问题-18,61,注意到，构造匹配就是在M上模拟w，这个过程要一直进行到M到达停机状态。如果出现了接受状态，希望这个部分匹配的顶部“赶上”底部，从而使得这个匹配得以完成。为此，再增加如下骨牌。 第6部分：对于每一个a，将 放入P中,6.2 一个简单的不可判定问题-19,62,这个步骤的效果是；在图灵机停机后增加一些“伪步骤”。这里，读写头“吃掉”一些邻近的符号直到没有符号剩下。 假设到机器以接受状态停机的地方的部分匹配是 刚才增加的骨牌允许匹配如下继续进行：,6.2 一个简单的不可判定问题-20,63

33、,第7部分：最后增加如下骨牌 来完成匹配,6.2 一个简单的不可判定问题-21,64,整个P的构造结束。注意P是MPCP的一个实例，而正是凭借MPCP，匹配才模拟了M在w上的计算。MPCP与PCP的不同之处在于：匹配需要以序列中的第一个骨牌开始。如果将P看作PCP的一个实例，而不是看作MPCP的一个实例则无论M在w上是否停机，显然它都有一个匹配。 现在说明怎么将P转化为PCP的实例P，使之仍然模拟M在w上的运行。思路是；“将以第一个骨牌开始”这个要求直接放入问题里，为此需要引入一些记号。,6.2 一个简单的不可判定问题-22,65,设uu1 u2 un是一个长度为n的串。定义如下： u*u1*

34、u2*u3*un uu1*u2*u3*un* u*u1*u2*u3*un* 这里，u是在u中的每个字母前增加符号*，u是在u中的每个字母后增加*，u是在u中每个字母的前和后都增加符号*。,6.2 一个简单的不可判定问题-23,66,如果P是如下的簇： 就令P是如下的簇 此时若再将P看作PCP的实例，就可以看到，可能形成匹配的唯一的骨牌是第一个骨牌,6.2 一个简单的不可判定问题-24,67,因为它是顶部和底部以相同符号*开始的唯一的骨牌。除了强迫匹配以第一个骨牌开始以外，*的使用并不影响可能的匹配，因为它们被原来的符号相互隔开，原来的符号现在出现在匹配的偶数位。 骨牌 是用来让顶部在匹配的最后

35、再增加一个*。,6.2 一个简单的不可判定问题-25,68,6.3 映射可规约性-1,使用可归约性技术可以证明各种各样问题的不可判定性。本节将可归约性这个概念形式化，这样就能更精确地使用。 将一个问题归约为另一个问题的概念可以用多个方式来形式定义，选择使用哪一个要根据应用情况。我们的选择是一种简单方式的可归约性，叫做映射可归约性（多一可归约性）。,69,6.3 映射可规约性-2,粗略地说， “用映射可归约性将问题A归约为问题B”指的是，存在一个可计算函数，它将问题A的实例转换成问题B的实例。如果有了这样一个转换函数(称为归约)，就能用B的解决方案来解A。原因是：A的任何一个实例可以这样来解：首

36、先用这个归约将A转换为B的一个实例然后应用B的解决方案。映射可归约性的一个精确定义随之而来。,70,6.3.1 可计算函数-1,图灵机计算函数的方式是：将函数的输入放在带子上，开始运行，并以停机后的带子作为函数的输出。 定义612 函数 f：*是一个可计算函数，如果有某个图灵机M，使得在每个输入w上，M停机，且此时只有f(w)出现在带上。 例613 整数上所有通常的算术运算都是可计算函数。例如，可以制造一个机器，它以m，n为输入且返回m与n的和mn。,71,6.3.1 可计算函数-2,例614 可计算函数可以是机器的描述之间的变换。 例如，如果wM是一个图灵机的编码，可以有一个可计算函数f，以

37、w为输入，且返回一个图灵机的描述M。M是一个与M识别相同语言的机器，但M从不试图将它的读写头移出它的带的左端点。函数f 通过在M的描述中加入一些状态来完成这个任务。如果w不是图灵机的合法编码，f 就返回。,72,6.3.2 映射可归约性的形式定义-1,定义6.15 语言A是映射可归约到语言B的，如果存在可计算函数 f：*使得对每个w， w A f(w) B 记做AmB。称函数 f 为A到B的归约。,73,6.3.2 映射可归约性的形式定义-2,A到B的映射归约提供了将A的成员测试问题转化为B的成员测试问题的方法。为了检查是否有wA ，可使用这个归约 f，将w映射到f(w)，然后检查是否f(w)

38、B 。术语映射归约来自于提供归约手段的函数或映射。 如果一个问题映射可归约到第二个问题，且第二个问题先前已被解决，就能得到原来问题的解。,74,6.3.2 映射可归约性的形式定义-3,定理6.16 如果AmB且B是可判定的，则A也是可判定的。 证明 设M是B的判定器，f 是从A到B的归约。A的判定器N如下： N“对于输入w： 计算f(w)。 在f(w)上运行M，输出M的输出。” 显然，如果wA ，则f(w)B，因为f是从A到B的归约。因此，只要wA ，则M接受f(w) 。故N的运行正如所求。,75,6.3.2 映射可归约性的形式定义-4,定理616的下列推论是证明不可判定性的主要工具。 推论6

39、17 如果AmB且A是不可判定的，则B也是不可判定的。 例618 从ATM到HALTTM的映射可归约性。 ATMM，w|M是一个TM，且接受w HALTTMM，w|M是一个TM，且对输入w停机 ,76,6.3.2 映射可归约性的形式定义-5,为此必须提供一个可计算函数f，它使用形如M，w的输入，返回形如M、w的输出、使得 M，wATM当且仅当M，w HALTTM 下面的机器F计算了归约f： F“对于输入M，w： 构造下列图灵机M：,77,6.3.2 映射可归约性的形式定义-6,M“对输入x： 在x上运行M。 如果M接受，则接受（停机）； 如果M拒绝，则进入循环（不停机）。” 输出M，w。”,78,6.3.2 映射可归约性的形式定义-7,例619 波斯特对应问题是不可判定的，其证明中包含了两个映射归约。 ATMmMPCP和MPCPmPCP。 对这两种情形，都能容易地得到实际的归约函数且能容易地证明它们是映射归约。映射可归约性是传递的，故这两个归约合起来蕴含了ATMmPCP。,79,6.3.2 映射可归约性的形式定义-8,例620 定理64的证明中，隐含了一个从ETM到EQTM的映射归约。此归约f 将输入M映射到输出M，M1，其中M1是拒绝所有输入的机器。 例621 定理6