形式语言与自动机课件

计算理论第5章可归约性1计算理论第5章可归约性1前言

在第4章已经确定采用图灵机作为通用计算器机的模型，并介绍了几个在图灵机上可解的问题，还给出了一个计算机不可解的问题，即ATM。本章讨论另外几个不可解的问题。在讨论过程中，将介绍一个基本方法，可用来证明问题是计算上不可解的，这个方法称为可归约性。

归约旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题，在日常生活中，虽然不这样称呼，但时常会遇见可归约性问题。

2前言在第4章已经确定采用图灵机作为通用计算器机前言例如，在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。可归约性总是涉及两个问题，称之为A和B。如果A可归约到B，就可用B的解来解A。在上述例子中，A是城市认路问题，B是得到地图问题。注意，可归约性说的不是怎样去解A或B，而是在知道B的解时怎么去解A。3前言例如，在一个新城市中认路，如果有一张地图，事情就容易了。主要内容5.1语言理论中的不可判定问题5.2一个简单的不可判定问题5.3映射可归约性

5.3.1可计算函数 5.3.2映射可归约性的形式定义

4主要内容5.1语言理论中的不可判定问题4语言理论中的不可判定问题ATM是不可判定的，即确定个图灵机是否接受一个给定的输入问题是不可判定的。下面考虑一个与之相关的问题：HALTTM，即确定一个图灵机对给定输入是否停机（通过接受或拒绝）问题。若将ATM归约到HALTTM，就可以利用ATM的不可判定性证明HALTTM的不可判定性。设:

HALTTM={<M,w>|M是一个TM,且对输入w停机}5语言理论中的不可判定问题ATM是不可判定的，即确定个图灵机是语言理论中的不可判定问题定理5.1HALTTM是不可判定的。

为得到矛盾，假设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也必定是不可判定的。反证法，假设可判定，证明ATM是可判定的。6语言理论中的不可判定问题定理HALTTM是不可判定的。为得语言理论中的不可判定问题定理5.2ETM是不可判定的。

先用标准术语来写在证明思路中描述的那上修改型机器M1.M1=“在输入x上：1)如果x≠w，则拒绝。2)如果x=w，则在x上运行M，当M接受时，就接受。”这个机器以w作为它的描述的一部分。检查x=w是否成立的方法很显然，即扫描输入并用一个字符一个字符地将它与w进行比较，就可确定它们是否相同。

反证法，假设可判定，证明ATM是可判定的。除w外M1拒绝所有串7语言理论中的不可判定问题定理ETM是不可判定的。语言理论中的不可判定问题再假设TMR判定ETM。如下构造判定ATM的TMS:S=“在输入<M，w>上，此处<M，w>是TMM和串w的编码：1)用M和w的描述来构造上述TMM1。2)在输入<M1>上运行R。3)如果R接受，则拒绝；如果R拒绝，则接受。”不空，M接受w说明L(M1)是空集，因此M1不接受w8语言理论中的不可判定问题再假设TMR判定ETM。如下构造判语言理论中的不可判定问题另一个与图灵机有关的计算问题也很有意思，该问题是：给定一个图灵机和一个可由某个更简单的计算模型识别的语言，测定此图灵机是否识别此语言。例如：令REGULARTM是测定一个给定的图机是否有一个与之等价的有穷自动机问题，则这个问题与测定一个给定的图灵机是否识别一个与此正则语言的问题相同。设：

REGULARTM={<M>|M是一个TM，且L(M)是一个正则语言}9语言理论中的不可判定问题另一个与图灵机有关的计算问题也很有意语言理论中的不可判定问题定理5.3

REGULARTM是不可判定的。设R是判定REGULARTM的一个TM，下面构造判定ATM的TMS。S的运行方式如下：S=“对于输入<M，w>，其中M是TM，w是串：1)构造下述TMM2：M2=“在输入x上：a)如果x具有形式0n1n，则接受。b)如果x不具有此形式，则在输入w上运行M。如果M接受w，则接受。”2)在输入<M2>上运行R。3)如果R接受，则接受；如果R拒绝，则拒绝。”10语言理论中的不可判定问题定理REGULARTM是不可判定的语言理论中的不可判定问题定理5.4EQTM是不可判定的。

设TMR判定EQTM。如下构造判定ETM的TMS：S=“对于输入<M>，其中M是TM：1)在输入<M，M1>上运行R，其中M1是拒绝所有输入的图灵机。2)如果R接受，则接受；如果R拒绝，则拒绝。如果R判定EQTM，则S判定ETM。但由定理5.2，ETM是不可判定的，故EQTM也是不可判定的。11语言理论中的不可判定问题定理EQTM是不可判定的。设TM语言理论中的不可判定问题定义5.5

设M是一个图灵机，w是一个串。M在w上的一个

接受计算历史是一个格局序列C1，C2，．．．,Cl，其中C1是M在w上的起始格局，Cl是M的一个接受格局，且每个Ci都是Ci-1的合法结果，即符合M的规则。M在w上的一拒绝计算历史可类似定义，只是Cl应是一个拒绝格局。12语言理论中的不可判定问题定义设M是一个图灵机，定义5.6

线性界限自动机是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就保持在原地不动。这与普通图灵机的读写头不会离开带子的左端点的方式一样。语言理论中的不可判定问题定义5.6ababa控制器13定义线性界限自动机是一种受到限制的图灵机，它不允语言理论中定义5.6设M是有q个状态和g个带符号的LBA。对于长度为n的带子，M恰有qngn个不同的格局。语言理论中的不可判定问题引理5.7

M的格局就像计算中间的一快照。格局由控制状态、读写头位置和带内容组成。这里，M有q个状态。它的带长度是n，所以读写头可能处于n个位置之一，且gn多个带符号串可能出现在带上。此三个量的乘积就是带长为n的M的格局总数。

14定义设M是有q个状态和g个带符号的LBA。对于长度为语言理定义5.6ALBA是可判定的。

语言理论中的不可判定问题定理5.8证明判定ALBA的算法如下：L=“对于输入<M，w>，其中M是LBA，w是串：1)在w上模拟Mqngn步，或者直到它停机。2)如果M停机，则当它接受时接受，拒绝时拒绝。如果它还没有停机，就拒绝。”如果M在w上运行qngn步还没有停机，根据引理5.7，它必定在重复某个格局，即陷入了循环。这就是算法为什么在此情形下拒绝的原因。15定义ALBA是可判定的。语言理论中的不可判定问题定理证明定义5.6

ELBA是不可判定的。

语言理论中的不可判定问题定理5.9现在构造从ATM到ELBA的归约。假设TMR判定ELBA。如下构造判定ATM的TMS：S=“对于输入<M，w>，其中M是TM，w是串：1)如在证明思路中所描述的那样从M和w构造LBAB。2)在输入<B>上运行R。3)如果R拒绝，则接受；如果R接受，则拒绝。”

####…##C1C2C3Cl16定义ELBA是不可判定的。语言理论中的不可判定问题定理如果R接受<B>，则L(B)=

。这样，M在w上就没接受计算历史，M也就不接受w.因此，S也就拒绝<M，w>。类似地，如果R拒绝<B>，则B的语言不空。B能够接受的唯一串是M在w上的接受计算历史。这样，M必定接受w。相应地，S也就接受<M，w>。下图是检查这样一个TM计算历史的示意图。

语言理论中的不可判定问题q3ab#xxq5b#……#xBCiCi+117如果R接受<B>，则L(B)=。这样，M在w上就没接使用利用计算历史的归约技术，还能建立有关上下文无关文法和下推自动机问题的不可判定性。加快一下，定理4.7介绍了一个算法来判定一个上下文无关文法是否派生串，即判定L(G)=

是否成立。与此相关，现在要证明问题“测定一个上下文无关文法是否派生所有可能的串”是不可判定的。证明这个问题不可判定是证明上下文无关文法等价性问题不可判定的重要步骤。设:ALLCFG={<G>|G是一个CFG且L(G)=

*}语言理论中的不可判定问题18使用利用计算历史的归约技术，还能建立有关上下文无关文语言理论定义5.6ALLCFG是不可判定的。

语言理论中的不可判定问题定理5.10用反证法。为得到矛盾，假设ALLCFG是可判定的，用这个假设来证明ATM是可判定的。其证明与定理5.9的证明类似，只是稍微复杂一些，绕了一点点弯。这是一个从ATM出发利用计算历史的归约。但由于技术上的原因，对计算历史的表示做了些修改，后面将解释这样做的原因。现在来描述怎样运用ALLCFG的判定过程来判定ATM。对于TMM和输入串w，首先构造一个CFGG，使得它派生所有串当且仅当M不接受w。所以，如果M接受w，则存在一个特别的串，G不派生它。这个串应该是M在w上的计算历史。即：设计G，使之派生所有不是M在w上接受计算历史的串。

19定义ALLCFG是不可判定的。语言理论中的不可判定问题定语言理论中的不可判定问题为了使得CFGG派生所有不是M在w上接受计算历史的串，采用下的策略。一个串不能成为M在w上的接受计算历史的原因可能有多个。将M在w上的接受计算历史表示成#C1#C2#...#Cl#，其中Ci是M在w上计算的第i步的格局。然后G派生出满足下述条件的所有串：1)不以Cl开始。2)不以一个接受格局结束3)在M的规则下，某个Ci不恰好派生Ci+1。如果M不接受w，就没有接受计算历史存在，故所有串都因为这样或那样的问题而不能成为接受计算历史，因此G将派生所有串，这正是所希望的。20语言理论中的不可判定问题为了使得CFGG派生所有不是M在w语言理论中的不可判定问题这个思路存在的问题是：当D将Ci弹出栈时，它处于相反的左右为难，因而不适合与Ci+1比较。前面提到的绕弯就在此处。换一种方法来写接受计算历史，使得每隔一个格局就以相反的顺序出现。奇数位置保持以向前的顺序写，但偶数位置向后写。这种形式的一个接受计算历史如下图所示：

####…##C1C2RC3C4R#Cl21语言理论中的不可判定问题这个思路存在的问题是：当D将Ci弹出主要内容5.1语言理论中的不可判定问题5.2一个简单的不可判定问题5.3映射可归约性

5.3.1可计算函数 5.3.2映射可归约性的形式定义

22主要内容5.1语言理论中的不可判定问题22本节将证明：不可判定性现象不仅能仅能局限于有限自动机的问题，我们将给出一个关于串操作的不可判定问题，称为波斯特对应问题。可以很容易地将这个问题描述成一种游戏，多米诺骨牌。每个骨牌由两个串构成，一边一个，单个骨牌看上去像一簇骨牌看起来像任务是将这些骨牌进行排列(允许重复)，使得在总计顶部符号后得到的串与总计询问符号后得到的串相同。这样的排列称为一个匹配。例如，下面的排列就是这个游戏的一个匹配。一个简单的不可判定问题aabbcaaabcaaabcc,,,23本节将证明：不可判定性现象不仅能仅能局限于有限自动机的问题，一个简单的不可判定问题aabbcacaaaababcc阅读顶部后得到的串abcaaabc，与总计询问后得到的本同。可以将骨牌变形使得和询问对应符号整齐地排列，以此更容易表示匹配。aabbccaaaaaabbcc24一个简单的不可判定问题aabbcacaaaababcc阅读顶一个简单的不可判定问题

对某些骨牌簇，不可能找到这样的匹配。例如，簇

不可能包含匹配，因为顶部的每个串都比询问对应的串长。波斯特对应问题是：确定一簇骨牌是否有一个匹配。这个问题在算法上是不可解的。

abcabcacaccba,,25一个简单的不可判定问题对某些骨牌簇，不可能找到一个简单的不可判定问题在形式描述这个问题和给出它的证明之前，先来精确地描述这个问题，然后表示成一个。骨牌簇P是pcp的一个实例：

匹配是一个序列i1，i2，．．．，il，使ti1ti2．．．til=bi1bi2bil.问题是确定P是否有匹配。令PCP={<G>|P是波斯特对应问题的一个实例，且P有匹配}

t1b1t2b2tkbk,,P=,…26一个简单的不可判定问题在形式描述这个问题和给出它的证定义5.6

PCP是不可判定的。

一个简单的不可判定问题定理5.11假设TMR判定PCP。构造S来判定ATM。令M=(Q,

,

,

,q0,qaccept,qreject)其中Q,

,

,

分别是M的状态集、输入字母表、带字母表和转移函数。S构造PCP的一个实例P，使得P有一个匹配当且仅当M接受w。为此，S首先构造MPCP的一个实例P’。下面以七个部分来描述这个构造。每个部分完成在w上模拟M的一个特定方面。在构造过程中，为了解释我们正在做什么，用一个例子插在构造中。27定义PCP是不可判定的。一个简单的不可判定问题定理假设T一个简单的不可判定问题

第1部分：构造以下方式开始：

将放入p’作为第一张骨牌

因为P’是MPCP的一个实例，故匹配必须以这张骨牌开始。底部串以M在w上接受计算历史中的第一个格局C1=q0w1w2．．．wn开始。如图所示:##q0w1w2…wn#t1b1##…q0w1w2wn#28一个简单的不可判定问题第1部分：构造以下方式开始：一个简单的不可判定问题

到目前为止，只得到一个部分匹配，其询问串由C1=

＃q0w1w2．．．wn＃构成，顶部串只有#。为获得匹配，盘面扩展串来匹配询问串。用新骨牌来作这样的扩展。这些新的骨牌强迫模拟M的一次单步运行，使得M的一下个格局出现在询问串的扩展中。第2、3、4部分在P’中增加的骨牌在模拟中起主要作用。第2部分处理读写向右运动，第3部分处理读写头向左运动，第4部分处理不与读写关相邻的带方格。29一个简单的不可判定问题到目前为止，只得到一个部分匹配一个简单的不可判定问题第2部分：对于第一个a,b∈

和q,r∈Q，其中q≠qreject，如果

(q,a)=(r,b,R),则将放入P’中。第3部分：对于第一个a,b,c∈

和q,r∈Q，其中q≠qreject，如果

(q,a)=(r,b,L)，则将放入p’中。第4部分：对于每一个a∈，将放入p’中。这样，第2、3和4部分的骨牌，使得我们能够通过“在第一个格局之后增加第二个格局”的方法来扩展匹配。希望这个过程能够继续下去，即增加第三个格局，然后第四个格局，等等。为此，需要增加一个新的骨牌来复制符号#。qabrcqarcbaa30一个简单的不可判定问题第2部分：对于第一个a,b∈和q,一个简单的不可判定问题第5部分：将和放入P’中接着上面的例子。假设在状态q7且读1时，M进入状q5，在带上写下0，并将读写头向右移到。即

(q7,1)=(q5,0,R)。则在P’中有骨牌最后的那个匹配被扩展到#_###q710q520q500#q7##22q7110000##…31一个简单的不可判定问题第5部分：将一个简单的不可判定问题再假设在状态q5且读0时，M进入状态q9，在带上写下2，并将它的读写头向左移动。故

(q5,1)=(q9,2,L)。则有骨牌第一个骨牌与本构造部分有关，因为读写头左边的符号是0。前面的部分匹配就被扩展成

0q50q9021q50q9122q50q922_q50q9_2,,和2q9020#0##220q5q50000##…32一个简单的不可判定问题再假设在状态q5且读0时，M进入状态q一个简单的不可判定问题注意，构造匹配就是在w上模拟M，这个过程要一直进行到M到达停机状态。如果出现了接受状态，希望这个部分匹配的顶部“赶上”底部，从而使得这个匹配得以完成。为此，再增加加下骨牌。第6部分：对于第一个a∈，将和放入P’中这个步骤的效果是：在图灵机停机后增加一些“伪步骤”。这里，读写头“吃掉”一些邻近的符号直到没有符号剩下。再继续前面的例子，假设到机器以接受状态停机的地方为止的部分匹配是aqacceptqacceptqacceptaqaccept33一个简单的不可判定问题注意，构造匹配就是在w上模拟M，这个过一个简单的不可判定问题刚才增加的骨牌允许匹配如下继续进行：##…21qaccept2#021qaccept2###2211qacceptqaccept0022##…#……#qaccept#34一个简单的不可判定问题刚才增加的骨牌允许匹配如下继续进行：#一个简单的不可判定问题第7部分：最的增加如下骨牌来完成匹配：##q0w1w2…wn####qacceptqaccept…###35一个简单的不可判定问题第7部分：最的增加如下骨牌一个简单的不可判定问题★u★u★===**u1u1u1***u2u2u2***u3u3u3******………ununun**u★为将p’转换为PCP的一个实例P，做下面的事情：如果P’是如下的簇:t1b1t2b2tkbk,,,…t3b3,设u=u1u2…un是一个长串为n的串。定义如下三个串：36一个简单的不可判定问题★u★u★===**u1u1u1***一个简单的不可判定问题就令P是如下的簇★t1★b1★★t1b1★★t3b3★,,,…★t2b2★,,★tkbk★

,*

此时若再将P看PCP的实例，就可以看到，可能形成匹配的唯一的骨牌是第一个骨牌★t1★b1★37一个简单的不可判定问题就令P是如下的簇★t1★b1★★因为它是顶部和底部以相同符号，即*，开始的唯一的骨牌。除了强迫匹配以第一个骨牌开始以外，*的使用并不影响可能的匹配，因为它们被原来的符号相互隔开，原来的符号现在出现在匹配的偶数们。骨牌是用来让顶部在匹配的最后再增加一个*。一个简单的不可判定问题

*

38因为它是顶部和底部以相同符号，即*，开始的唯一的骨牌。除一个主要内容5.1语言理论中的不可判定问题5.2一个简单的不可判定问题5.3映射可归约性

5.3.1可计算函数 5.3.2映射可归约性的形式定义

39主要内容5.1语言理论中的不可判定问题39§5.3映射可归约性使用规约技术可以证明各种问题的不可判定性。本节将规约性概念形式化，这样就能更精确地使用它。将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方式要根据具体应用情况。我们的选择是一种简单方式的可归约性，叫做映射可归约性。粗略地说，“用映射可归约性将问题A归约为问题B”是指，存在一个可计算函数，它将问题A的实例转换成问题B的实例。如果有了这样一个转换函数，就能用B的解决方案来解A。原是，A的任何一个实例可以这样来解：首先用这个归约将A转换为B的一个实例，然后应用B的解决方案。40§5.3映射可归约性使用规约技术可以证明各种问题的不可判例5.13整数上所有通常的算术运算都是可计算函数。例如，可以制造一个机器，它以<m,n>为输入且返回m与n的和m+m。定义5.6函数f：

*

*是一个可计算函数，如果有图灵机M，使得在每个输入w上停机，且此时只有f(w)出现在带上。

定义5.12§5.3映射可归约性图灵机计算函数的方式是：将函数的输入放在带子上，开始运行，并以停机后的带子作为函数的输出。41例5.13整数上所有通常的算术运算都是可计算函数。定义函例5.14可计算函数可以是机器的描述之间的变换。例如，如果w=<M>是图灵机的编码，可以有一个可计算函数f，以w为输入，且返回一个图灵机的描述<M

>。M

是一个与M识别相同语言的机器。函数f通过在M的描述中加入一些状态来完成这个任务。如果M不是图灵机的合法编码，f就返回

§5.3映射可归约性42例5.14可计算函数可以是机器的描述之间的变换。例如，§5.定义5.6语言A是映射可归约到语言B的，如果存在可计算函数f：

*

*使得对每个w，w∈A等价于f(w)∈B记作A≤mB。称函数f为A到B的归约。定义5.15ABff§5.3映射可归约性A到B的映射规约提供了将A的成员测试问题转化为B的成员测试问题的方法。为了检查是否有w属于A，可使这个规约f，将w映射到f(w)，然后检查是否f(w)属于B。如果一个问题映射可规约到第二个问题，且第二个问题先前已被解决，那就能得到原来问题的解43定义语言A是映射可归约到语言B的，如果存在可计算函定义ABf定义5.6如果A≤mB且B是可判定的，则A也是可判定的。定理5.16§5.3映射可归约性证明：设M是B的判定器，f是从A到B的归约。A的判定器N的描述如下：N=“对于输入w：1)计算f(w)。2)在f(w)上运行M，输出M的输出。”显然，如果w∈A，则f(w)∈B，因为f是从A到B的归约。因此，只要w∈A，则M接受f(w)。故N的运行正如所求。44定义如果A≤mB且B是可判定的，则A也是可判定的。定理§5.定义5.6

如果A≤mB且A是不可判定的，则B也是不可判定的。

推论5.17例5.18定理5.1使用从ATM出发的一个规约，证明了HALTTM是不可判定的。这个归约说明了怎么用HALTTM的判定器给出ATM的判定器。以下展示从ATM到HALTTM的映射可归约性，为此必须提供一个可计算函数f，它使用形如<M，w>的输入，返回形如<M

，w

>的输出，使得<M，w>∈

ATM当且仅当<M

，w

>∈HALTTM

§5.3映射可归约性45定义如果A≤mB且A是不可判定的，则B也是不可判定的。推下面的机器F计算了归约f:F=“对于输入<M，w>：1)构造下面图灵机M’。M’=“对于输入x：a.在x上运行M。b.如果M接受，则接受。c.如果M拒绝，则进入循环。2)输出<M’，w’>。”§5.3映射可归约性46下面的机器F计算了归约f:§5.3映射可归约性46例5.19定理5.11中的波斯特对应问题是不可判定的，其证明中包含了两个映射归约。它首先证明了ATM≤mMPCP，然后又证明了MPCP≤mPCP。对于两种情形，都能容易地得到实际的归约函数，且能容易地证明它们是映射归约。例5.20在定理5.4的证明中，隐含了一个从ETM到EQTM的映射归约。此归约f将输入<M>映射到输出<M，M1>,其中M1是拒绝所有输入的机器。§5.3映射可归约性47例5.19定理5.11中的波斯特对应问题是不可判定的，例5.21本节定义了映射可归