计算理论.ppt
《计算理论.ppt》由会员分享,可在线阅读,更多相关《计算理论.ppt(53页珍藏版)》请在三一文库上搜索。
1、1,计算理论,第5章 可归约性,2,前言,在第4章已经确定采用图灵机作为通用计算器机的模型,并介绍了几个在图灵机上可解的问题,还给出了一个计算机不可解的问题 ,即ATM。本章讨论另外几个不可解的问题 。在讨论过程 中,将介绍一个基本方法,可用来证明问题是计算上不可解的,这个方法称为可归约性。 归约旨在将一个问题转化为另一个问题,且使得可以用第二个问题的解来解第一个问题,在日常生活中,虽然不这样称呼,但时常会遇见可归约性问题。,3,前言,例如,在一个新城市中认路,如果有一张地图,事情就容易了。这样,就将在城市认路问题归约为得到地图问题。 可归约性总是涉及两个问题,称之为A和B。如果A可归约到B,
2、就可用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的不可判定性。设:
3、 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,语言理论中的不可判定
4、问题,定理 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)在输
5、入上运行R。 3)如果R接受,则拒绝;如果R拒绝,则接受。”,不空,M接受w,说明L(M1)是空集,因此M1不接受w,9,语言理论中的不可判定问题,另一个与图灵机有关的计算问题也很有意思,该问题是: 给定一个图灵机和一个可由某个更简单的计算模型识别的 语言,测定此图灵机是否识别此语言。 例如:令REGULARTM是测定一个给定的图机是否有一个与 之等价的有穷自动机问题,则这个问题与测定一个给定的图 灵机是否识别一个与此正则语言的问题相同。设: REGULARTM=| M是一个TM,且L(M)是一个正则语言,10,语言理论中的不可判定问题,定理 5.3,REGULARTM是不可判定的。,设R是判
6、定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接受,则接受;如果
7、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,线性界限自动机是一种受到限制的图灵机,它不允 许其读写头离开包含输入的带区域。如果此机器 试图将它的读写头移出输入的两个端点,则读写 头就保持在原
8、地不动。这与普通图灵机的读写头 不会离开带子的左端点的方式一样。,语言理论中的不可判定问题,定义 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=“
9、对于输入,其中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) 在输入上运行
10、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)= 是否成立。与此相关,现在要证明问题“测定一个上 下文无关
11、文法是否派生所有可能的串”是不可判定的。证明这 个问题不可判定是证明上下文无关文法等价性问题不可判定 的重要步骤。设: ALLCFG=| G是 一个CFG且L(G)= *,语言理论中的不可判定问题,19,定义 5.6,ALLCFG是不可判定的。,语言理论中的不可判定问题,定理 5.10,用反证法。为得到矛盾,假设ALLCFG是可判定的,用这个假设来证 明ATM是可判定的。其证明与定理5.9的证明类似,只是稍微复杂一些, 绕了一点点弯。这是一个从ATM出发利用计算历史的归约。 但由于技术 上的原因,对计算历史的表示做了些修改,后面将解释这样做的原因。 现在来描述怎样运用ALLCFG的判定过程来判
12、定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) 在
13、M的规则下,某个Ci不恰好派生Ci+1。 如果M不接受w,就没有接受计算历史存在,故所有串都因为这样或那样的 问题而不能成为接受计算历史,因此G将派生所有串,这正是所希望的。,21,语言理论中的不可判定问题,这个思路存在的问题是:当D将Ci弹出栈时,它处于相反的左右 为难,因而不适合与Ci+1比较。前面提到的绕弯就在此处。换一 种方法来写接受计算历史,使得每隔一个格局就以相反的顺序出 现。奇数位置保持以向前的顺序写,但偶数位置向后写。这种形 式的一个接受计算历史如下图所示:,22,主要内容,5.1 语言理论中的不可判定问题 5.2 一个简单的不可判定问题 5.3 映射可归约性 5.3.1 可计
14、算函数 5.3.2 映射可归约性的形式定义,23,本节将证明:不可判定性现象不仅能仅能局限于有限自动机的问题,我们将 给出一个关于串操作的不可判定问题,称为波斯特对应问题。 可以很容易地将这个问题描述成一种游戏,多米诺骨牌。每个骨牌由两个串 构成,一边一个,单个骨牌看上去像 一簇骨牌看起来像 任务是将这些骨牌进行排列(允许重复),使得在总计顶部符号后得到的串 与总计询问符号后得到的串相同。这样的排列称为一个匹配。例如,下面 的排列就是这个游戏的一个匹配。,一个简单的不可判定问题,24,一个简单的不可判定问题,阅读顶部后得到的串abcaaabc,与总计询问后得到的本同。可以 将骨牌变形使得和询问
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 理论
链接地址:https://www.31doc.com/p-2654229.html