第六章、可归约性.ppt

  1. 1、本文档共88页,可阅读全部内容。
  2. 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第六章、可归约性

计算理论导引 第二部分 可计算理论 第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的输

文档评论(0)

yan698698 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档