计算理论.ppt

1,计算理论,第5章 可归约性,2,前言,在第4章已经确定采用图灵机作为通用计算器机的模型，并介绍了几个在图灵机上可解的问题，还给出了一个计算机不可解的问题 ，即ATM。本章讨论另外几个不可解的问题 。在讨论过程 中，将介绍一个基本方法，可用来证明问题是计算上不可解的，这个方法称为可归约性。 归约旨在将一个问题转化为另一个问题，且使得可以用第二个问题的解来解第一个问题，在日常生活中，虽然不这样称呼，但时常会遇见可归约性问题。,3,前言,例如，在一个新城市中认路，如果有一张地图，事情就容易了。这样，就将在城市认路问题归约为得到地图问题。 可归约性总是涉及两个问题，称之为A和B。如果A可归约到B，就可用B的解来解A。在上述例子中，A是城市认路问题，B是得到地图问题。注意，可归约性说的不是怎样去解A或B，而是在知道B的解时怎么去解A。,4,主要内容,5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 5.3.1 可计算函数 5.3.2 映射可归约性的形式定义,5,语言理论中的不可判定问题,ATM是不可判定的，即确定个图灵机是否接受一个给定的输入问题是不可判定的。 下面考虑一个与之相关的问题：HALTTM，即确定一个图灵机对给定输入是否停机（通过接受或拒绝）问题。若将ATM归约到HALTTM，就可以利用ATM的不可判定性证明HALTTM的不可判定性。设: HALTTM=| M是一个TM, 且对输入w停机,6,语言理论中的不可判定问题,定理 5.1,HALTTM是不可判定的。,为得到矛盾，假设TM R判定HALTTM，由之可以构造TM S来判定 ATM, 其构造如下： S=“在输入上，此处是TM M和串w 的编码： 1) 在输入上运行TM R。 2)如果R拒绝，则拒绝。 3)如果R接受，则在w 上模拟M，直到它停机。 4)如果M已经接受，则接受；如果M已经拒绝，则拒绝。 显然，如果R判定HALTTM，则S判定ATM。因为ATM是不可判定的， 故HALTTM也必定是不可判定的。,反证法，假设可判定，证明ATM是可判定的。,7,语言理论中的不可判定问题,定理 5.2,ETM 是不可判定的。,先用标准术语来写在证明思路中描述的那上修改型机器M1. M1=“在输入x上： 1)如果xw，则拒绝。 2)如果x=w，则在x上运行M，当M接受时，就接受。” 这个机器以w作为它的描述的一部分。检查x=w是否成立的方法很 显然， 即扫描输入并用一个字符一个字符地将它与w进行比较，就可确定它们 是否相同。,反证法，假设可判定，证明ATM是可判定的。,除w外M1拒绝所有串,8,语言理论中的不可判定问题,再假设TM R判定ETM。如下构造判定ATM的TM S: S=“在输入上，此处是TM M和串w的编码： 1) 用M和w的描述来构造上述TM M1。 2)在输入上运行R。 3)如果R接受，则拒绝；如果R拒绝，则接受。”,不空，M接受w,说明L(M1)是空集，因此M1不接受w,9,语言理论中的不可判定问题,另一个与图灵机有关的计算问题也很有意思，该问题是： 给定一个图灵机和一个可由某个更简单的计算模型识别的 语言，测定此图灵机是否识别此语言。 例如：令REGULARTM是测定一个给定的图机是否有一个与 之等价的有穷自动机问题，则这个问题与测定一个给定的图 灵机是否识别一个与此正则语言的问题相同。设： REGULARTM=| M是一个TM，且L(M)是一个正则语言,10,语言理论中的不可判定问题,定理 5.3,REGULARTM是不可判定的。,设R是判定REGULARTM 的一个TM，下面构造判定ATM的TM S。 S的运行方式如下： S=“对于输入，其中M是TM，w是串： 1)构造下述TM M2： M2=“在输入x上： a) 如果x具有形式0n1n，则接受。 b)如果x不具有此形式，则在输入w上运行M。如果M接受w，则接受。” 2)在输入上运行R。 3) 如果R接受，则接受；如果R拒绝，则拒绝。”,11,语言理论中的不可判定问题,定理 5.4,EQTM是不可判定的。,设TM R判定EQTM。如下构造判定ETM 的TM S： S=“对于输入，其中M是TM： 1)在输入上运行R，其中M1是拒绝所有输入的图 灵机。 2)如果R接受，则接受；如果R拒绝，则拒绝。 如果R判定EQTM，则S判定ETM。但由定理5.2，ETM是不可 判定的，故EQTM也是不可判定的。,12,语言理论中的不可判定问题,定义 5.5,设M是一个图灵机，w是一个串。M在w上的一个 接受计算历史是一个格局序列C1，C2，,Cl， 其中C1是M在w上的起始格局，Cl是M的一个接受 格局，且每个Ci都是Ci-1的合法结果，即符合M的 规则。M在w上的一拒绝计算历史可类似定义，只是 Cl应是一个拒绝格局。,13,定义 5.6,线性界限自动机是一种受到限制的图灵机，它不允 许其读写头离开包含输入的带区域。如果此机器 试图将它的读写头移出输入的两个端点，则读写 头就保持在原地不动。这与普通图灵机的读写头 不会离开带子的左端点的方式一样。,语言理论中的不可判定问题,定义 5.6,14,定义 5.6,设M是有q个状态和g个带符号的LBA。对于长度为 n的带子，M恰有qngn个不同的格局。,语言理论中的不可判定问题,引理 5.7,M的格局就像计算中间的一快照。格局由控制状态、读写 头位置和带内容组成。这里，M有q个状态。它的带长度是 n，所以读写头可能处于n个位置之一，且gn多个带符号串 可能出现在带上。此三个量的乘积就是带长为n的M的格局 总数。,15,定义 5.6,ALBA是可判定的。,语言理论中的不可判定问题,定理 5.8,证明 判定ALBA的算法如下： L=“对于输入，其中M是LBA，w 是串： 1)在w 上模拟M qngn步，或者直到它停机。 2)如果M停机，则当它接受时接受，拒绝时拒绝。如果它还没 有停机，就拒绝。” 如果M在w 上运行qngn步还没有停机，根据引理5.7，它必定 在重复某个格局，即陷入了循环。这就是算法为什么在此情 形下拒绝的原因。,16,定义 5.6,ELBA是不可判定的。,语言理论中的不可判定问题,定理 5.9,现在构造从ATM到ELBA的归约。假设TM R判定ELBA。 如下构造判定ATM的TM S： S=“对于输入，其中M是TM，w 是串： 1) 如在证明思路中所描述的那样从M和w 构造LBA B。 2) 在输入上运行R。 3) 如果R拒绝，则接受；如果R接受，则拒绝。”,17,如果R接受，则L(B)= 。这样，M在w 上就没接受计算 历史，M也就不接受w. 因此，S也就拒绝。类似地， 如果R拒绝，则B的语言不空。B能够接受的唯一串是M在 w 上的接受计算历史。这样，M必定接受w 。相应地，S也就 接受。下图是检查这样一个TM计算历史的示意图。,语言理论中的不可判定问题,18,使用利用计算历史的归约技术，还能建立有关上下文无关文 法和下推自动机问题的不可判定性。加快一下，定理4.7介绍 了一个算法来判定一个上下文无关文法是否派生串，即判定 L(G)= 是否成立。与此相关，现在要证明问题“测定一个上 下文无关文法是否派生所有可能的串”是不可判定的。证明这 个问题不可判定是证明上下文无关文法等价性问题不可判定 的重要步骤。设: ALLCFG=| G是 一个CFG且L(G)= *,语言理论中的不可判定问题,19,定义 5.6,ALLCFG是不可判定的。,语言理论中的不可判定问题,定理 5.10,用反证法。为得到矛盾，假设ALLCFG是可判定的，用这个假设来证 明ATM是可判定的。其证明与定理5.9的证明类似，只是稍微复杂一些， 绕了一点点弯。这是一个从ATM出发利用计算历史的归约。 但由于技术 上的原因，对计算历史的表示做了些修改，后面将解释这样做的原因。 现在来描述怎样运用ALLCFG的判定过程来判定ATM。对于TM M和 输入串w，首先构造一个CFG G ，使得它派生所有串当且仅当M不接受w 。所以，如果M接受w，则存在一个特别的串，G不派生它。这个串应该 是M在w上的计算历史。即：设计G ，使之派生所有不是M在w上接受计算 历史的串。,20,语言理论中的不可判定问题,为了使得CFG G派生所有不是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将派生所有串，这正是所希望的。,21,语言理论中的不可判定问题,这个思路存在的问题是：当D将Ci弹出栈时，它处于相反的左右 为难，因而不适合与Ci+1比较。前面提到的绕弯就在此处。换一 种方法来写接受计算历史，使得每隔一个格局就以相反的顺序出 现。奇数位置保持以向前的顺序写，但偶数位置向后写。这种形 式的一个接受计算历史如下图所示：,22,主要内容,5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 5.3.1 可计算函数 5.3.2 映射可归约性的形式定义,23,本节将证明：不可判定性现象不仅能仅能局限于有限自动机的问题，我们将 给出一个关于串操作的不可判定问题，称为波斯特对应问题。 可以很容易地将这个问题描述成一种游戏，多米诺骨牌。每个骨牌由两个串 构成，一边一个，单个骨牌看上去像 一簇骨牌看起来像 任务是将这些骨牌进行排列(允许重复)，使得在总计顶部符号后得到的串 与总计询问符号后得到的串相同。这样的排列称为一个匹配。例如，下面 的排列就是这个游戏的一个匹配。,一个简单的不可判定问题,24,一个简单的不可判定问题,阅读顶部后得到的串abcaaabc，与总计询问后得到的本同。可以 将骨牌变形使得和询问对应符号整齐地排列，以此更容易表示匹 配。,25,一个简单的不可判定问题,对某些骨牌簇，不可能找到这样的匹配。例如，簇 不可能包含匹配，因为顶部的每个串都比询问对应 的串长。 波斯特对应问题是：确定一簇骨牌是否有一个匹配。这个问 题在算法上是不可解的。,26,一个简单的不可判定问题,在形式描述这个问题和给出它的证明之前，先来精确地描述这个 问题，然后表示成一个。骨牌簇P是pcp的一个实例： 匹配是一个序列i1，i2，il，使ti1ti2til=bi1bi2bil. 问题是确定P是否有匹配。 令PCP=| P是波斯特对应问题的一个实例，且P有匹配,27,定义 5.6,PCP是不可判定的。,一个简单的不可判定问题,定理 5.11,假设TM R判定 PCP。构造S来判定ATM。令 M=(Q, , , , q0, qaccept, qreject) 其中Q, , , 分别是M的状态集、输入字母表、带字母表和 转移函数。 S构造PCP的一个实例P，使得P有一个匹配当且仅当M接受w。 为此，S首先构造MPCP 的一个实例P。下面以七个部分来描述 这个构造。每个部分完成在w上模拟M的一个特定方面。在构造 过程中，为了解释我们正在做什么，用一个例子插在构造中。,28,一个简单的不可判定问题,第1部分：构造以下方式开始： 将 放入p作为第一张骨牌 因为P是MPCP的一个实例，故匹配必须以这张骨牌开始。底部串以M在w 上接受计算历史中的第一个格局C1= q0w1w2wn开始。 如图所示:,29,一个简单的不可判定问题,到目前为止，只得到一个部分匹配，其询问串由C1= q0w1w2wn构成，顶部串只有#。为获得匹配，盘面 扩展串来匹配询问串。用新骨牌来作这样的扩展。这些新的 骨牌强迫模拟M的一次单步运行，使得M的一下个格局出现 在询问串的扩展中。 第2、3、4部分在P中增加的骨牌在模拟中起主要作用。第2 部分处理读写向右运动，第3部分处理读写头向左运动，第4 部分处理不与读写关相邻的带方格。,30,一个简单的不可判定问题,第2部分 ：对于第一个a,b和q,r Q，其中qqreject，如果 (q,a)=(r,b,R),则将 放入P中。 第3部分 ：对于第一个a,b,c和q,r Q，其中qqreject，如果 (q,a)=(r,b,L)，则将 放入p中。 第4部分 ：对于每一个a ，将 放入p中。 这样，第2、3和4部分的骨牌，使得我们能够通过“在第一个格局 之后增加第二个格局”的方法来扩展匹配。希望这个过程能够继续 下去，即增加第三个格局，然后第四个格局，等等。为此，需要 增加一个新的骨牌来复制符号#。,31,一个简单的不可判定问题,第5部分 ：将 和 放入P中 接着上面的例子。假设在状态q7且读1时，M进入状q5，在带上 写下0，并将读写头向右移到。即(q7,1)=(q5,0,R)。则在P中有 骨牌 最后的那个匹配被扩展到,32,一个简单的不可判定问题,再假设在状态q5且读0时，M进入状态q9，在带上写下2，并将它 的读写头向左移动。故(q5,1)=(q9,2,L)。则有骨牌 第一个骨牌与本构造部分有关，因为读写头左边的符号是0。前 面的部分匹配就被扩展成,33,一个简单的不可判定问题,注意，构造匹配就是在w上模拟M，这个过程要一直进行到M到 达停机状态。如果出现了接受状态，希望这个部分匹配的顶部 “赶上”底部，从而使得这个匹配得以完成。为此，再增加加下骨 牌。 第6部分 ：对于第一个a ，将 和 放入P中 这个步骤的效果是：在图灵机停机后增加一些“伪步骤”。这里， 读写头“吃掉”一些邻近的符号直到没有符号剩下。再继续前面 的例子，假设到机器以接受状态停机的地方为止的部分匹配是,34,一个简单的不可判定问题,刚才增加的骨牌允许匹配如下继续进行：,35,一个简单的不可判定问题,第7部分： 最的增加如下骨牌 来完成匹配：,36,一个简单的不可判定问题,为将p转换为PCP的一个实例P，做下面的事情：如果P是如下 的簇:,设u=u1u2un是一个长串为n的串。定义如下三个串：,37,一个简单的不可判定问题,就令P是如下的簇,此时若再将P看PCP的实例，就可以看到，可能形成匹配的唯一的 骨牌是第一个骨牌,38,因为它是顶部和底部以相同符号，即*，开始的唯一的骨牌。除 了强迫匹配以第一个骨牌开始以外，*的使用并不影响可能的匹 配，因为它们被原来的符号相互隔开，原来的符号现在出现在匹 配的偶数们。骨牌 是用来让顶部在匹配的最后再增加一个*。,一个简单的不可判定问题,39,主要内容,5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 5.3.1 可计算函数 5.3.2 映射可归约性的形式定义,40,§5.3 映射可归约性,使用规约技术可以证明各种问题的不可判定性。本节将规约性概念形式化，这样就能更精确地使用它。 将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方式要根据具体应用情况。我们的选择是一种简单方式的可归约性，叫做映射可归约性。 粗略地说，“用映射可归约性将问题A归约为问题B”是指，存在一个可计算函数，它将问题A的实例转换成问题B的实例。 如果有了这样一个转换函数，就能用B的解决方案来解A 。原是，A 的任何一个实例可以这样来解：首先用这个归约将A转换为B的一个实例，然后应用B的解决方案。,41,例5.13 整数上所有通常的算术运算都是可计算函数。 例如，可以制造一个机器，它以为输入且返回 m与n的和m+m。,定义 5.6,函数f： * * 是一个可计算函数，如果有图灵机 M，使得在每个输入w上 停机，且此时只有f(w)出 现在带上。,定义 5.12,§5.3 映射可归约性,图灵机计算函数的方式是：将函数的输入放在带子上，开始运行，并以停机后的带子作为函数的输出。,42,例5.14可计算函数可以是机器的描述之间的变换。例如， 如果w=是图灵机的编码，可以有一个可计算函 数f，以w为输入，且返回一个图灵机的描述 。 M是一个与M识别相同语言的机器。函数f通过在M 的描述中加入一些状态来完成这个任务。如果 M不 是图灵机的合法编码，f就返回,§5.3 映射可归约性,43,定义 5.6,语言A是映射可归约到语言B的，如果存在可计算函 数 f： *使得对每个w， wA等价于f(w) B 记作AmB。称函数f为A到B的归约。,定义 5.15,§5.3 映射可归约性,A到B的映射规约提供了将A的成员测试问题转化为B的成员测试问题的方法。为了检查是否有w属于A，可使这个规约f，将w映射到f(w)，然后检查是否f(w)属于B。如果一个问题映射可规约到第二个问题，且第二个问题先前已被解决，那就能得到原来问题的解,44,定义 5.6,如果AmB且B是可判定的，则A也是可判定的。,定理 5.16,§5.3 映射可归约性,证明：设M是B的判定器，f是从A到B的归约。A的判定器N 的描述如下： N=“对于输入w： 1) 计算f(w)。 2) 在f(w)上运行M，输出M的输出。” 显然，如果wA，则f(w) B，因为f 是从A到B的归约。因此，只要wA，则M 接受f(w)。故N的运行正如所求。,45,定义 5.6,如果AmB且A是不可判定的，则B也是不可判定的。,推论 5.17,例5.18 定理5.1使用从ATM出发的一个规约，证明了HALTTM是不可判定的。这个归约说明了怎么用HALTTM的判定器给出ATM的判定器。以下展示从ATM到HALTTM的映射可归约性，为此必须提供一个可计算函数f，它使用形如的输入，返回形如的输出，使得 ATM当且仅当HALTTM,§5.3 映射可归约性,46,下面的机器F计算了归约f: F=“对于输入： 1) 构造下面图灵机M。 M=“对于输入x： a.在x上运行M。 b.如果M接受，则接受。 c.如果M拒绝，则进入循环。 2) 输出。”,§5.3 映射可归约性,47,例5.19 定理5.11中的波斯特对应问题是不可判定的，其证明中包含了两个映射归约。它首先证明了ATMmMPCP，然后又证明了MPCPm PCP。对于两种情形，都能容易地得到实际的归约函数，且能容易地证明它们是映射归约。,例5.20 在定理5.4的证明中，隐含了一个从ETM到EQTM的映射归约。此归约f将输入映射到输出,其中M1是拒绝所有输入的机器。,§5.3 映射可归约性,48,例5.21 本节定义了映射可归约性的形式概念，本章的前面部分所使用的可归约性都是非形式概念。定理5.2证明ETM是不可判定的，这个证明说明了映射可归约性的形式概念与非形式概念之间的差别。ETM的不可判定性是通过将ATM归约到它来证明的。现在来看看能否将这个归约转化为映射归约。,§5.3 映射可归约性,49,如果AmB，且B是可图灵可识别的，则A也是图灵 可识别的。,定理 5.22,如果AmB，且A不是图灵可识别的，则B也不是图 灵可识别的。,§5.3 映射可归约性,证明与5.16类似，只是将M和N改为识别器。,50,EQTM既不是图灵可识别的，也不是补图灵可识别的。,首先证明EQTM不是图灵可识别的。为此，只要证明ATM可归约到EQTM的补 即可。归约函数如下： F=“对于输入，其中M是TM，w 是串： 1) 构造下列两个机器M1和M2。 M1=“对于任何输入： a.拒绝。” M2=“对于任何输入： a.在w上运行M,如果它接受，就接受。” 2)输出。”,§5.3 映射可归约性,51,这里M1什么也没接受。如果M接受w，则M2接受每一个输入， 故两个机器不等价。相反，如果M不接受w，则M2什么也不接 受，故它们是等价的。这样f将ATM归约到EQTM的补，这正是我 们所希望的。 为了证明EQTM的补不是图灵可识别的，只要给出一个从ATM到 EQTM的归约。因此要证明ATMmEQTM。下面的TM G计算归 约函数g.,§5.3 映射可归约性,52,G=“对于输入，其中M是TM，w 是串： 1) 构造下列两个机器M1和M2. M1=“对于任何输入： a.接受。” M2=“对于任何输入： a.在w上运行M b.如果它接受，就接受。” 2) 输出。” f和g之间的唯一差别在机器M1上。在f中，机器M1总是拒绝.而在g中， 它总是接受。在f和g中。M接受w当且仅当M2接受所有串。在g中，M接受 w当且仅当M1和M2等价。这就是g是从ATM到EQTM的归约的原因。,§5.3 映射可归约性,53,作业,5.1、5.5、5.6、5.28、5.34,