计算理论第4章-图灵机研究优秀PPT.ppt

《计算理论第4章-图灵机研究优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算理论第4章-图灵机研究优秀PPT.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第4章 图灵机许桂靖 杨 莹 2Overviewn图灵机（Turing Machine，TM），是计算机的一种简洁的数学模型。n历史上，冯诺曼计算机的产生就是由图灵机诱发的。n丘奇图灵论题：一切合理的计算模型都等同于图灵机.3类型类型 文文 法法 结结 构构 产产 生生 式式 形形 式式 限限 制制 条条 件件 0 短语结构文法短语结构文法 +,*Phrase Structure 上下文有关文法上下文有关文法 1A212|12|1A2|1 Context Sensitive 1，2*（CSG）A,+上下文无关文法上下文无关文法 A A,*2 Context Free （CFG）正正 右线性文

2、法右线性文法 AxB，Cy A,B,C 3 规规 文文 左线性文法左线性文法 ABx，Cy x,yT*法法4Overview 0型语言型语言 图灵机图灵机 1型语言型语言(CSL)线性界限自动机线性界限自动机 2型语言型语言(CFL)下推自动机下推自动机 3型语言型语言(正规集正规集)有限自动机有限自动机 5Overviewn图灵机所定义的语言类-递归可枚举集合n图灵机所计算的整数函数类-部分递归函数n以图灵机为模型,探讨问题的可计算性，即确定该问题是可计算的、部分可计算的，还是不行计算的。6Overview4.1 图灵机模型 4.2 图灵机的变更和组合 4.3 通用图灵机4.4图灵机可计算性

3、74.1 图灵机模型 84.1 图灵机模型图灵机模型定义定义4-1 图灵机M=(K,q0,B,F)，其中 K是有穷的状态集合；是所允许的带符号集合；B，是空白符；，B ，是输入字符集合；F K，是终止状态集合。，是终止状态集合。q0K,是初始状态；是初始状态；94.1 图灵机模型图灵机模型：KKL,R,S是图灵机的动作(状态转移)函数，这里L表示读头左移一格；R表示读头右移一格；S表示读头不动；(q,a)=(p,b,z)表示状态q下读头所读符号为a时，状态转移为p,读头符号变为b，同时读头变更为z.104.1 图灵机模型图灵机模型定义定义4-2 设当前带上字符串为x1x2 xn，当前状态为q，

4、读头正在读xi，图灵机的瞬时描述ID 为x1x2 xi-1 q xi xn114.1 图灵机模型图灵机模型n定义定义4-3 设当前的瞬时描述ID1=x1x2 xi-1 q xi xn若有(q,x i)=(p,y,L)，则图灵机瞬时描述变为ID2=x 1x 2 x i-2p x i-1 y x i+1 x n；若有 (q,x i)=(p,y,R)，则图灵机瞬时描述变为ID2=x1x2 xi-1 y pxi+1 xn。124.1 图灵机模型图灵机模型n定义定义4-3n瞬时描述瞬时描述ID1经过一步变为瞬时描述经过一步变为瞬时描述ID2，称，称ID1与与ID2具有一步变更关系，表示具有一步变更关系，

5、表示为为 nID1ID2 n若若ID1经过经过n步变为步变为ID2(n0)，即有，即有nID1ID ID2n称称ID1与与ID2具有多步变更关系，简记为具有多步变更关系，简记为n ID1*ID2134.1 图灵机模型图灵机模型n定义定义4-4 对于图灵机M=(K,q0,B,F)，定义图灵机接受的语言集 L(M)为L(M)=w|w*u0 u v q qf(u0*u*v*qKqf F q0w*u0qB*uqfv)144.1 图灵机模型图灵机模型n【例【例4-1】设计一个图灵机，使得】设计一个图灵机，使得 nL(M)=0 n1 n|n1。n设计思路设计思路:在带上每当将一个在带上每当将一个0变为变为

6、X，就，就把一个把一个1变为变为Y。当将全部的。当将全部的0变为变为X时，恰时，恰将全部的将全部的1变为变为Y，这个串就是合法的，最，这个串就是合法的，最终将终将X、Y分别还原为分别还原为0、1。154.1 图灵机模型图灵机模型164.1 图灵机模型图灵机模型【例【例4-2】设计一个图灵机，使之接受设计一个图灵机，使之接受 L(M)=wcw|w a,b*设计思路：在设计思路：在c左侧，从左至右逐一字符，用状态登左侧，从左至右逐一字符，用状态登记它并标记该符号为已处理符号，移至记它并标记该符号为已处理符号，移至c右侧对应右侧对应位置后，推断是否是相同符号。若相同，再返回位置后，推断是否是相同符号

7、。若相同，再返回c左侧循环，直至全部符号比较完毕。最终将标记左侧循环，直至全部符号比较完毕。最终将标记符号修改回原符号。在设计时，特殊留意用状态符号修改回原符号。在设计时，特殊留意用状态存贮符号的方法，这是图灵机设计的重要方法之存贮符号的方法，这是图灵机设计的重要方法之一。一。174.1 图灵机模型图灵机模型184.1 图灵机模型图灵机模型【例【例4-3】设计一个图灵机，计算自然数】设计一个图灵机，计算自然数n的的以以2为底的对数。为底的对数。用一进制表示输入和输出值。用一进制表示输入和输出值。an表示输入表示输入n,bm表示输出表示输出m.设计思路：从左到右扫描带，把所遇到的设计思路：从左到

8、右扫描带，把所遇到的a划划掉一个，留一个，并将计数器加掉一个，留一个，并将计数器加1。重复此。重复此过程，直至过程，直至a不复存在。这里，用字符不复存在。这里，用字符c表表示划掉的字符。示划掉的字符。194.1图图灵灵机机模模型型204.1 图灵机模型图灵机模型【例【例4-4】设计一个图灵机，计算二个自然数】设计一个图灵机，计算二个自然数m、n的减法：的减法：设计时，整数设计时，整数n用用0n表示。起先时，带上符号为表示。起先时，带上符号为 0m10n，结束时，带上符号为，结束时，带上符号为0。每当在。每当在1的左边的左边将一个将一个0变更为变更为B，就在，就在1的右边将一个的右边将一个0改为

9、改为1，若若1的右边无的右边无0时，再将左边改为时，再将左边改为B的的0复原回来。复原回来。m-n 若若mnmnmn=0 否则否则214.1 图灵机模型图灵机模型R224.1 图灵机模型图灵机模型【例【例4-5】设计图灵机实现数字从一进制表示到设计图灵机实现数字从一进制表示到二进制表示的转换。二进制表示的转换。这个图灵机的设计可以仿例这个图灵机的设计可以仿例4-3，不同在于每次循，不同在于每次循环时，要保留除以环时，要保留除以2的余数作为当前二进制位的值。的余数作为当前二进制位的值。留意这里首先计算出的是二进制的低位值，所以留意这里首先计算出的是二进制的低位值，所以要将结果不断右移以插入新生成

10、的位，生成的结要将结果不断右移以插入新生成的位，生成的结果是低位在右端。初始时，整数果是低位在右端。初始时，整数n用用an表示，结束表示，结束时，带上是时，带上是0、1构成的二进制数。构成的二进制数。234.1 图灵机模型图灵机模型R244.2 图灵机的变更和组合图灵机的变更和组合n4.2.1 双向无穷带图灵机n4.2.2 多带图灵机n4.2.3 非确定图灵机n4.2.4 多头图灵机n4.2.5 多维图灵机n4.2.6 离线图灵机 n4.2.7 图灵机的组合n4.2.8 枚举器25双向无穷带图灵机定理定理4-1 L被一个具有双向无穷带的图灵机识别，被一个具有双向无穷带的图灵机识别，当且仅当它被

11、一个单向无限带的图灵机识别。当且仅当它被一个单向无限带的图灵机识别。证明：单向无限证明：单向无限TM模拟双向无限模拟双向无限TM，接受多道技，接受多道技术。术。264.2.2 多带图灵机274.2.2 多带图灵机n【例例4-6】设计一个二带图灵机，使得 T(M)=|0,1*。n这个问题的关键是比较字符串前后两个部分，为此，首先要对带上字符串计数：每二元素计数加1，按计数值将字符串分为前后两个部分，并将它们分别存放于不同带上，然后进行比较。284.2.2 多带图灵机294.2.2 多带图灵机【例【例4-7】设计二带图灵机，实现二进制到一进设计二带图灵机，实现二进制到一进制的转换。制的转换。设这个

12、图灵机为设这个图灵机为M7，其第一带用作输入带，其次带，其第一带用作输入带，其次带用作输出带。设计思路是从左到右扫描输入带上用作输出带。设计思路是从左到右扫描输入带上的二进制字符，并运用公式的二进制字符，并运用公式r*2+b生成输出带上生成输出带上一进制数，其中一进制数，其中r是当前输出带上的一进制数，是当前输出带上的一进制数，b是当前输入带上扫描的字符，这里的是当前输入带上扫描的字符，这里的r*2就是将原就是将原输出带上的一进制数输出带上的一进制数r复制一遍。例如：复制一遍。例如：1001的的一进制数计算过程。一进制数计算过程。304.2.2 多带图灵机314.2.2 多带图灵机定理定理4-

13、2 假如一个语言假如一个语言L被一个多带图灵机被一个多带图灵机接受，它就能被一个单带图灵机接受。接受，它就能被一个单带图灵机接受。324.2.3 非确定图灵机【例【例4-8】下面的图】下面的图灵机就是不确定图灵机就是不确定图灵机。无向图灵机。无向图G中，中，从从a动身合法路径动身合法路径判定的不确定型图判定的不确定型图灵机。灵机。334.2.3 非确定图灵机n非确定图灵机由一个有穷限制器、一条带和一个读头组成。对于一个给定的状态和被读头扫描的带符号，机器的下一个动作将有有穷个选择。n设一个非确定图灵机 M1=(K,q0,B,F)，除转移函数外，其它同一般图灵机的定义。转移函数仍是从K到KL,R

14、,S上的映射，但它可能有多个映射的像,即存在qK,a,n(q,a)=(p1,b1,c1)n(q,a)=(p2,b2,c2)n n(q,a)=(pr,br,cr)344.2.3 非确定图灵机定理定理4-3 假如语言假如语言L被一个非确定图灵机被一个非确定图灵机M1接受，则接受，则L将被某个确定图灵机将被某个确定图灵机M2接受。接受。354.2.4 多头图灵机n一个k头图灵机有k个读头，一个限制器和一条带，读头由1到k编号，图灵机的一个动作由当前状态和被每个读头所扫描的符号。在一个动作中，每个读头独立地左移、右移或不动。n定理4-4 假如L被某个k个读头的图灵机接受，则它能被一个单头图灵机接受。3

15、64.2.5 多维图灵机多维图灵机具有通常的有限限制器，但带却多维图灵机具有通常的有限限制器，但带却由由k维单元阵列组成。这里，在全部维单元阵列组成。这里，在全部2k个方个方向上（向上（k个轴，每轴正、负两个方向），都个轴，每轴正、负两个方向），都是无限的，依据状态和扫视的符号，该装是无限的，依据状态和扫视的符号，该装置变更状态，打印一个新的符号，在置变更状态，打印一个新的符号，在2k个个方向上移动它的读头，起先时，输入沿着方向上移动它的读头，起先时，输入沿着一个轴排列，读头在输入的左端。一个轴排列，读头在输入的左端。374.2.6 离线图灵机定理定理4-5 假如假如L被一个二维图灵机被一个二

16、维图灵机M1接受，接受，那么那么L将被一个一维图灵机将被一个一维图灵机M2接受。接受。384.2.7 图灵机的组合394.2.7 图灵机的组合【例【例4-9】设计一个设计一个TM，完成乘法运算，完成乘法运算mn。起先时带上。起先时带上符号为：符号为：0m10n1，结束时带上符号为，结束时带上符号为0mn，用子程，用子程序调用的方式完成。序调用的方式完成。设计思想是：每当抹去左边一个，就在其次个后面拷贝设计思想是：每当抹去左边一个，就在其次个后面拷贝n个。当第一个的左边全变为个。当第一个的左边全变为B时，带上就为时，带上就为10n10mn，再抹去，再抹去10n1，带上就剩，带上就剩0mn，即为所

17、，即为所求。求。设计设计Copy子程序子程序 这个子程序完成在其次个拷贝这个子程序完成在其次个拷贝n个的个的操作。操作。第第1次被调用次被调用起先起先ID：Bm-11q10n1结束结束ID：Bm-11q50n10n第第i次被调用次被调用起先起先ID：Bim-i1q10n10(i-1)n结束结束ID：Bim-i1q50n10in在拷贝时，每当将一个变成，就在末尾写个。当在拷贝时，每当将一个变成，就在末尾写个。当0n变变为为2n时，就已在右边加了时，就已在右边加了0n。再将。再将2变为变为0n。404.2.7 图灵机的组合设计主 MM=q0,q6,q7,q8,q9,q10,q11,q12,q13,

18、0,1,0,1,2,B,q0,B,q13)起先ID为q00m10n1，进入Copy入口ID为B0m-11q10n1，为此，(q0,0)=(q6,B,R)(q6,0)=(q6,0,R)(q6,1)=(q1,1,R)从Copy结束时的ID，进入主TM的起先ID(B0m-11q50n10nBq00m-110n10n)(q5,0)=(q7,0,L)(q7,1)=(q8,1,L)(q8,0)=(q9,0,L)(q9,0)=(q9,0,L)(q9,B)=(q0,B,R)善后处理：Bm1q50n10mn414.2.8 枚举器424.2.8 枚举器定理定理4-6 一个语言是图灵可识别的，当且仅当有枚举器枚举它

19、。一个语言是图灵可识别的，当且仅当有枚举器枚举它。证明：首先证明假如有枚举器证明：首先证明假如有枚举器E枚举语言枚举语言L，则存在图灵机，则存在图灵机M识别识别L。构造构造M如下：如下：对于随意输入串对于随意输入串w，运行，运行E。每当。每当E输出一个串时，与输出一个串时，与w比较，若相比较，若相等，接受等，接受w，并停机。，并停机。明显，明显，M接受在接受在E输出序列中出现过的那些串。输出序列中出现过的那些串。现在证明若有图灵机现在证明若有图灵机M识别语言识别语言L，则有枚举器，则有枚举器E枚举枚举L。设设L=w1，w2，w3，构造，构造E如下：如下：对对i=1,2,3,执行如下步骤执行如下

20、步骤（1）对）对w1，w2，w3，,wi中的每一串，让中的每一串，让M以其作为输入运以其作为输入运行行i步。步。（2）若在这个计算中，）若在这个计算中，M接受接受wj，则打印，则打印wj，M接受接受w，它最终将出现在，它最终将出现在E的枚举打印中。事实上，它可能在的枚举打印中。事实上，它可能在E的的列表在出现无限多次，因为每一次重复运行，列表在出现无限多次，因为每一次重复运行，M在每一个串上在每一个串上都从头起先运行。都从头起先运行。434.3 通用图灵机通用图灵机()缓冲域带的最左面是标记符，的右边是|K|+|+2个单元构成的缓冲（|K|、|分别是状态集和字母集的元素数目）。()的描述字域缓

21、冲区域右边紧接的是的描述字dM，以为起先标记，以个结束。对于转移函数(q,a)=(q,a,d)，我们用五元组表示为(q,a,q,a,d)，将依次调整为(q,a,a,d,q)。dM就是由这样的五元组组成的序列。对于每个五元组中的状态和字符，我们用其序号的一进表示，其间用分隔，五元组间用个分隔。例如：若有(q,)=(q,)，表示成上面定义的五元组是(q,，,，q)，再用其序号表示为(2,0,2,0,3)，在U2的带上表示为()的输入描述域的描述字域的右边存放的是输入串的编码：用字母的序号表示该字母，并用分隔。该域以为起始标记。如输入为111，则该串表示为：110110110444.3 通用图灵机通

22、用图灵机UTM U2模拟具体步骤如下：模拟具体步骤如下：步步0 将读头置于描述字区域的起先符号上。此时缓冲区将读头置于描述字区域的起先符号上。此时缓冲区域是；域是；步步1U2复写标记或后面的状态到缓冲域的初始位置，复写标记或后面的状态到缓冲域的初始位置，然后在其后面加一个协助符号，读写头右移到符号；然后在其后面加一个协助符号，读写头右移到符号；步步2 U2复写后面的初始带模式到缓冲区部分，即在之复写后面的初始带模式到缓冲区部分，即在之后；后；步步3 U2将改为将改为0，现缓冲区中包含当前状态和扫描的字，现缓冲区中包含当前状态和扫描的字母；母；步步4对描述字域进行搜寻，查看前两项匹配的元组。若全

23、对描述字域进行搜寻，查看前两项匹配的元组。若全部的五元组都不匹配，则表明停机，部的五元组都不匹配，则表明停机，U2也停机。若找也停机。若找到一个匹配的五元组，标记、表示正在比较的状态或到一个匹配的五元组，标记、表示正在比较的状态或符号；符号；454.3 通用图灵机通用图灵机步步5(找到匹配的五元组找到匹配的五元组)删去缓冲区的内容，并把标记右删去缓冲区的内容，并把标记右移一个符号，使处于该五元组的新符号的前面；移一个符号，使处于该五元组的新符号的前面；步步6用新符号代替标记后面的符号用新符号代替标记后面的符号(可能需扩充或压缩原可能需扩充或压缩原输入描述域输入描述域)，U2将标记右移至五元组的

24、方向重量前；将标记右移至五元组的方向重量前；步步7 U2计数方向重量中的个数，然后按要求向左或向右计数方向重量中的个数，然后按要求向左或向右移动标记。若向左离开了输入串，则移动标记。若向左离开了输入串，则U2停机；若停机；若向右离开了输入串，向右离开了输入串，U2必需添加一个表示下一个方格的必需添加一个表示下一个方格的新的新的“”串。当前串。当前U2描述字域标记后面不是结束状描述字域标记后面不是结束状态，则转至步态，则转至步1；否则接受输入串并停机。；否则接受输入串并停机。464.3 通用图灵机通用图灵机474.3 通用图灵机通用图灵机n对于任何一个图灵机对于任何一个图灵机M，都有一个确定的描

25、，都有一个确定的描述字述字dM，如在例，如在例4-10中中dMn将它看作一个二进制数，实质上，它是一将它看作一个二进制数，实质上，它是一个整数，因此按这个整数，因此按这 种表示，任何一个图灵种表示，任何一个图灵机都和一个整数相对应，这个整数，称为机都和一个整数相对应，这个整数，称为图灵机的标记。图灵机的标记。484.4图灵可计算性图灵可计算性n4.4.1 图灵可计算性函数 n4.4.2 图灵机的枚举定理n4.4.3 图灵机的计算限界 494.4.1 图灵可计算性函数图灵可计算性函数 n定义定义4-5 函数函数f(x1,x2,xn)是部分图是部分图灵可计算的，若有一图灵程序灵可计算的，若有一图灵

26、程序P，使得，使得P(x1,x2,xn)=f(x1,x2,xn)n其中其中P(x1,x2,xn)是是P对应的函数，对应的函数，“=”表示若有定义，则值相等；否则，均表示若有定义，则值相等；否则，均无定义。无定义。504.4.1 图灵可计算性函数图灵可计算性函数定义定义4-6 函数f(x1,x2,xn)是全函数，若它对一切x1,x2,xn都有定义。定义定义4-7 函数f(x1,x2,xn)是图灵可计算函数，若它是部分图灵可计算的而且是全函数。514.4.1 图灵可计算性函数图灵可计算性函数524.4.1 图灵可计算性函数图灵可计算性函数定理定理4-7 设设g1,g2,gm是是n元图灵可计元图灵可

27、计算函数，算函数，h是是m元图灵可计算函数，则复合元图灵可计算函数，则复合函数函数f=h(g1,g2,gm)也是图灵可计算的。也是图灵可计算的。534.4.2 图灵机的枚举定理图灵机的枚举定理1图灵机的标记 2图灵可计算的重要定理定义定义4-8 若z是一个图灵机M的标记，并且M计算部分函数g(x1,x2,xn)，则定义函数(n)为(n)(z,x1,x2,xn)=g(x1,x2,xn)544.4.2 图灵机的枚举定理图灵机的枚举定理定理定理4-8 枚举定理枚举定理 对于每个自然数对于每个自然数z，部分函数，部分函数(n)(z,x1,x2,xn)是是(部分部分)图灵可计算函数。图灵可计算函数。证明

28、证明它能枚举全部部分可计算函数。具体说就是，它能枚举全部部分可计算函数。具体说就是，n+1元函数元函数(n)(z,x1,x2,xn)将枚举全部将枚举全部n元部分可元部分可计算函数。事实上，任给一个计算函数。事实上，任给一个n元图灵可计算函数元图灵可计算函数g(x1,x2,xn)，则必有一个图灵程序，则必有一个图灵程序M对应它。对应它。令令z是它的标记，我们有是它的标记，我们有(n)(z,x1,x2,xn)=g(x1,x2,xn)554.4.2 图灵机的枚举定理图灵机的枚举定理定理定理4-9 迭代定理迭代定理 对一切n，有图灵可计算函数，S(n)(z,x1,x2,xn)，使得对一切m，有(n+m

29、)(z,x1,x2,xn,y1,y2,ym)=(m)(S(n)(z,x1,x2,xn),y1,y2,ym)证明564.4.2 图灵机的枚举定理图灵机的枚举定理定义定义4-9 计步谓词计步谓词STP(n)定义如下：定义如下：STP(n)(z,x1,x2,xn,M)描述字为描述字为z的图灵的图灵机程序机程序T对于输入对于输入x1,x2,xn在在M步内停机。其步内停机。其中中“一步一步”定义为完成图灵机定义为完成图灵机T的状态转移函数的状态转移函数的一个变换。的一个变换。定理定理4-10计步定理计步定理 对随意对随意n，谓词，谓词STP(n)(z,x1,x2,xn,M)是图灵可计算的。是图灵可计算的

30、。证明证明574.4.3 图灵机的计算限界图灵机的计算限界584.4.3 图灵机的计算限界图灵机的计算限界1.域函数和停机函数594.4.3 图灵机的计算限界图灵机的计算限界604.4.3 图灵机的计算限界图灵机的计算限界614.4.3 图灵机的计算限界图灵机的计算限界624.4.3 图灵机的计算限界图灵机的计算限界定理定理4-11 对角线停机函数对角线停机函数h不是图灵可计算的。不是图灵可计算的。证明 定理定理4-12 空带停机函数空带停机函数h0不是图灵可计算的，其中不是图灵可计算的，其中证明证明634.4.3 图灵机的计算限界图灵机的计算限界644.4.3 图灵机的计算限界图灵机的计算限界2.完全性函数654.5 习题习题人有了学问，就会具备各种分析实力，明辨是非的实力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富学问，培育逻辑思维实力；通过阅读文学作品，我们能提高文学鉴赏水平，培育文学情趣；通过阅读报刊，我们能增长见识，扩大自己的学问面。有很多书籍还能培育我们的道德情操，给我们巨大的精神力气，鼓舞我们前进。