chapter图灵机解析实用PPT课件

1、第九章、图灵机第九章、图灵机1932年-1935年，主要研究量子力学、概率论和逻辑学。1935年，年仅23岁的图灵，被选为剑桥大学国王学院院士。1936年他来到美国的普林斯顿大学攻读数学博士学位。1936年，图灵向伦敦权威的数学杂志投了一篇论文，题为“论数字计算在决断难题中的应用”。1939年，第二次世界大战爆发后，英国对德宣战，图灵随即应征入伍，正式到“政府编码与密码学院”服役。1946年，图灵获得“OBE”，即“不列颠帝国勋章”，那是英国皇室给予为国家和人民做出巨大贡献、立下大功的人士的荣誉。1947年-1948年，主要从事计算机程序理论的研究，并同时在神经网络和人工智能领域做出开创性的理

2、论研究。1945年到1948年，图灵在国家物理实验室，负责自动计算引擎(ACE)（Automatic Computing Engine，ACE）的工作 。1949年，他成为曼切斯特大学计算机实验室的副主任，负责最早的真正的计算机-曼切斯特一号的软件工作。 1949年，成为世界上第一位把计算机实际用于数学研究的科学家。1950年，写文章提出了著名的“图灵测试”1950年10月，图灵又发表了另一篇题为“机器能思考吗”的论文，成为划时代之作。也正是这篇文章，为图灵赢得了“人工智能之父”的桂冠。1951年，成为他家族中的第四位皇家学会会员。第1页/共34页第九章、图灵机第九章、图灵机一、丘奇一、丘奇图

3、灵论题图灵论题1、丘奇在1936.3从可计算函数的构造出发发表了论文，给出了演算系统，该论题给出了今天的递归函数理论，实际上也是一种计算模型，为程序设计语言奠定了重要的理论基础；2、图灵在1936年，从理想计算机出发，提出了无限存储计算模型，称为图灵机，它的简洁构造和运行原理，隐含了存储程序的原始思想，深刻揭示了线代通用电子数字计算机最核心的内容（论文题目 “On Computable Numbers”）。这2个模型殊途同归！实际上，还有，哥德尔，波斯特等等，都在研究中陆续提出了一批计算模型，只是，由于图灵机的特点和性质更接近于普通人计算的思想方法，而且，又因为其好用而被现代计算机的研究、开发

4、者所采纳。第2页/共34页第九章、图灵机第九章、图灵机3、10年后，一位数学家冯诺依曼给出了现代存储程序式电子数字计算机的基本结构与工作原理。回顾一下已经介绍的计算模型，我们发现它是一步步走向计算机的通用模型，有穷自动机对于小储量设备是较好的模型，下推自动机则是对无限存储设备是较好的，但却只能“后进先出”的栈方法。通俗些说，图灵用计算模型描述现代通用计算机的最核心内容，而丘奇的演算系统为程序设计语言奠定了重要的理论基础，故而，称为丘奇丘奇图灵论题图灵论题。第3页/共34页第九章、图灵机第九章、图灵机二、图灵机定义二、图灵机定义定义1、图灵机是一个 7 元组 (Q, , , , q0, qacc

5、ept, qreject) (1) Q 是状态集。 (2) 是输入字母表，不包括特殊空白符号。 (3) 是带字母表，其中 并且 。 (4) : Q Q L, R 是转移函数。 (5) q0 是起始状态。 (6) qaccept 是接受状态。 (7) qreject 是拒绝状态，qacceptqreject。例如 : (q, a) = (r, b, L)第4页/共34页第九章、图灵机第九章、图灵机开始时，M 以最左边的 n 个带方格接收输入w=w1w2wn *，带的其余部分保持空白(即填以空白符)，读写头从最左边的带方格开始运行，注意 不含空字符，故出现在带上的第一个空字符表示输入的结束。M 开

6、始运行后，计算根据转移函数所描述的规则进行，如果 M 试图将读写头从带的最左端再向左移出，即使转移函数指示的是 L，读写头也停在原地不动。计算一直持续到它进入接受状态或拒绝状态，此时停机，如果二者都不发生，则 M 将永远运行下去。w1w2wn状态控制器第5页/共34页第九章、图灵机第九章、图灵机它比栈强的地方，就是读写头可以左右移动到信息所在的地方，与栈相比，显然改进很大，还有事先设置了2种状态，接受或拒绝。接受和拒绝状态都是停机状态，否则，就继续运行，永不停机。w1w2wn状态控制器第6页/共34页第九章、图灵机第九章、图灵机图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，

7、称为图灵机的格局。对于状态 q 和带字母表 的两个字符串 u 和 v，以 uqv 表示如下格局：当前状态是 q，当前带上的内容是 uv，读写头的当前位置是 v 的第一个符号，带上 v 的字符最后字符以后的符号都是空白符。 例如，1011q7011111 0 1 1 0 1 1 1 1q7第7页/共34页第九章、图灵机第九章、图灵机如果图灵机能合法地从格局 C1 一步进入 C2，则称格局 C1产生格局 C2。设 a, b 和 c 是 中的符号，u 和 v 是 * 中字符串，qi 和 qj是状态，则 uaqibv 和 uqjacv 是两个格局。如果转移函数满足 (qi , b) = (qj , c

8、, L)，则说uaqibv 产生和 uqjacv 。M 在输入 w 上的起始格局是格局 q0w，表示机器处于起始状态 q0，并且读写头处于带子的最左端位置，在接受格局里，状态是 qaccept ，在拒绝格局里，状态是 qreject。接受和拒绝状态都是停机状态，它们都不再产生新的格局。由于图灵机只在接受或拒绝状态下才停机，可以等价地将状态转移函数简化 : Q Q L, R 其中 Q 是取消 qaccept 和qreject 的 Q。第8页/共34页第九章、图灵机第九章、图灵机图灵机 M 接受输入 w ，如果存在格局的序列 Cl, C2, , Ck使得： (1) Cl 是 M 在输入 w 上的起

9、始格局； (2) 每一个Ci 产生 Ci +1； (3) Ck 是接受格局。M 接受的字符串的集合称为 M 的语言，或被 M 识别的语言，记为 L(M)。第9页/共34页第九章、图灵机第九章、图灵机定义2、如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的 (Turning recognizable)。也称为递归可枚举语言。输入上运行一个TM时，可能出现三种结果：接受、拒绝、循环（仅仅指机器不停机）对于一个输入，TM有两种方式不接受它：一种拒绝状态一种进入循环问题：如何区别长计算 与 死循环？第10页/共34页第九章、图灵机第九章、图灵机三、可识别与可判定的差异三、可识别与可判定的差异定

10、义3、如果一个语言能被某一图灵机判定，则称该语言是图灵可判定的 (Turning decidable)。也称为递归语言。可识别与可判定的区别？1.可识别接受该语言；2.可判定可以不接受该语言。 事实上，识别与判定的关键差异，就是是否有循环。事实上，识别与判定的关键差异，就是是否有循环。第11页/共34页第九章、图灵机第九章、图灵机例1 描述 TM M2，它识别的语言是所有由 0 组成、长度为 2的方幂的字符串，即 A= | n 0 M2 = “对于输入字符串w： 1) 从左往右扫描整个带子，隔一个字符消去一个0。 2) 如果在第1步之后，带子上只剩下唯一的一个0，则接受。 3) 如果在第1步之

11、后，带子上包含不止一个0，并且0的个数是奇数，则拒绝。 4) 读写头返回至带子的最左端。 5) 转到第1步。”可以发现，用该算法，00000也被接受，故而说明描述的图灵机有误。如何修改？20n第12页/共34页第九章、图灵机第九章、图灵机修改： M 2=“对于输入字符串 : （1）从左往右扫描整个带子上的字符0，每隔一个0用字符X替换一个0。 （2）如果在第一步之后,带子上只剩下唯一的一个0，则接受。 （3）如果在第一步之后,带子上包含不止一个0，并且最后一个非空格字符不是X，则拒绝。 （4）如果在第一步之后，带子上包含不止一个0，且最后一个非空格字符是X,若字符0的个数为奇数个，则拒绝。 （

12、5）让读头返回至带子的最左端。 （6）转到第一步。” 这是2011级学生修改的，可以再研究一下是否有问题。第13页/共34页第九章、图灵机第九章、图灵机q1q3q4qrejectq2qacceptq50 , RRxRR0 x, RxRxRL0RxRR0 x, RxL0LR如同栈的底部符号$xR的意思是xx, R第14页/共34页第九章、图灵机第九章、图灵机每重复一次第 1 步，消去了一半个数的 0。由于在第 1 步中，机器扫描了整个带子，故它能够？知道它看到的 0 的个数是奇数还是偶数，如果是大于 1 的奇数，则输入中所含的 0 的个数不可能是 2 的方幂，此时机器就拒绝。但是，如果看到的 0

13、 的个数是 1，则输入中所含的 0 的个数肯定是 2 的方幂，此时机器就接受。 M2= (Q, , , , q1, qaccept, qreject)的形式化描述： Q=q1 , q2 , q3 , q4 , q5 , qaccept, qreject， =0， =0 , x , ，将描述成状态图如上， 开始、接受和拒绝状态分别是q1, qaccept, qreject第15页/共34页第九章、图灵机第九章、图灵机可以看一下具体运算，设M2在输入0000的运算情况： q10000,q2000, xq300, x0q40,x0 xq3, x0q5x , xq50 x, q5x0 x, q5x0

14、x, q2x0 x, xq20 x, xxq3x, xxxq3 , xxq5x, xq5xx, q5xxx, q5xxx, q2xxx, xq2xx, xxq2x, xxxq2, xxxqaccept。再输入000，00000000，大家给出计算格局。第16页/共34页第九章、图灵机第九章、图灵机例2 下面给出图灵机 M1 形式化描述 M1= (Q, , , , q1, qaccept, qreject)，它的判定语言是 B = w#w | w 0, 1* 。 Q = q1, q2, , q8 , qaccept, qreject ， = 0, 1, # 且 = 0, 1, #, x, 。用状

15、态图描述 。开始、接受和拒绝状态分别是 q1, qaccept, qreject。大家可以试一下100#100的运算。第17页/共34页第九章、图灵机第九章、图灵机q1q8q3q5q6q4q7qacceptq2#RxRR0,1R#RxR0,1,xL0,1L#LxR1x,L1x,R0 x,L#R0 x,R0,1RxR第一步由q1 到 q7 实现，第二步由其余状态实现。0,1R的意思是不改变符号和状态，只是向右移动。第18页/共34页第九章、图灵机第九章、图灵机例3 图灵机 M3 做一些初等算术，它判定的语言C = | i j = k，且 i, j, k 1M3=“对于输入字符串 w： 1) 从左

16、往右扫描输入，确认输入具有形式 a*b*c*，否则拒绝。 2) 读写头回到带子的左端点。 3) 消去一个 a，并向右扫描直到 b 出现。在 b 与 c 之间来回移动，成对地消去 b 和 c，直到把所有的 b 都消去。如果 c 全消除后还有 b，则拒绝。 4) 如果还有 a 未消去，则恢复所有已消去的 b，再重复第 3步。如果所有的 a 都已被消去，则检查所有的 c 是否都已被消去。如果是，则接受，否则拒绝。”算法是？注意，最有效的是：如果还有 a 未消去，则恢复所有已消去的 b。ijka b c第19页/共34页第九章、图灵机第九章、图灵机 四、图灵机的变形四、图灵机的变形从不同的方面对 TM

17、 进行扩充。1、双向无穷带 TM 允许 TM 的输入带是无穷的。2、多带 TM 允许 TM 有多于一条的输入带。此时每条带上将有一个读头。3、不确定的 TM 允许 TM 在某一状态下根据读入的符号选择地进行某一个动作：进入某个状态，在读头的当前位置印刷某个符号，将读头移向某个方向。4、多维 TM 相当于在双向 TM 的基础上进一步扩充，允许TM 的“输入带”向更多的方向延伸。5、枚举器允许图灵机带有打印机。它们与基本的 TM 等价。在形式变化中保持不变的性质称为稳健性。第20页/共34页第九章、图灵机第九章、图灵机1、多带图灵机 (multitape Turing Machine) 很像普通图

18、灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许多个带子同时进行读、写和移动读写头，其形式为： 此处 k 是带子的个数。表达式( qi , a1 , a2 , , ak ) = ( qj, b1, b2, , bk , L, R, , L) 指的是：若机器处于状态 qi ，读写头 1 到 k 所读的符号分别是 a1 到 ak ，则机器转移到状态 qj，各读写头分别写下符号 b1 到 bk，且按此式所指示的那样移动每个读写头。 , , kkkQQL R S 第21页/共34页第九章、图灵机第九章、图灵机定理2、每个多

19、带图灵机等价于某一个单带图灵机。将一 个多带 TM M 转换为一个与之等价的单带 TM S，关健是怎样用 S 来模拟 M。假设 M 有 k 个带子。 S 把此 k 个带子的信息都存储在它的唯一带子上，并以此来模拟 k 个带子的效果，它用一个新的符号 # 作为定界符，以分开不同带子的内容。除了带内容之外，S 还必须记录读写头的位置。为此，它在一个符号的顶上加个点，以此来标记读写头在其带上的位置。S 把它们想象为虚拟带子和虚拟读写头。像以前一样，加点的带符号应是已经加进带字母表的新符号。第22页/共34页第九章、图灵机第九章、图灵机01 0 1 0 Ma a a b a # 0 1 0 1 0 #

20、 a a a # b a # S第23页/共34页第九章、图灵机第九章、图灵机S = “对于输入 w=w1 wn： 1) S 在白己的带子上放入 #w1w2wn# # # #（上边没加点） 此格式表示了 M 的全部 k 个带子的内容。 2)为了模拟多带机的一步移动， S在其带子上从标记左端点的第一个 # 开始扫描，一直扫描到标记右端点的第 (k+1) 个 #。其目的是确定虚拟读写头下的符号。然后 S 进行第二次扫描，并根据 M 的转移函数指示的运行方式更新其带子。 3)任何时候，只要 S 将某个虚拟读写头向右移动到某个#上面，就意味着 M 已将自己相应的读写头移动到了其所在的带子中的空白区域上

21、，即以前没有读过的区域上。因此，S在这个带方格上写下空白符，并将这个带方格到最右端的带方格中的内容都向右移动一个格。然后再像以前一样继续模拟。” 第24页/共34页第九章、图灵机第九章、图灵机推论1、一个语言是图灵可识别的，当且仅当存在多带图灵机识别它。一个图灵可识别语言可由一个普通的(单带)图灵机识别，这个普通图灵机是多带图灵机的一个特例，这就证明了此推论的一个方向。另一个方向可由定理2得证。第25页/共34页第九章、图灵机第九章、图灵机2、非确定型图灵机、非确定型图灵机 非确定型图灵机的有如其名，在计算的过程中，机器可以在多种可能性动作中选择一种继续进行。它的转移函数具有如下形式：: Q

22、P(QL, R其计算是一棵树，不同分支对应着机器的不同可能性。定理3、每个非确定型图灵机都等价于某一个确定型图灵机。（ 1）、能用确定型 TM D 来模拟非确定型 TM N 的计算的证明思路是：让 D 试验 N 的非确定性计算的所有可能分支，若 D能在某个分支中到达接受状态，则接受；否则 D 的模拟将永不终止。（ 2）、将 N 在输入 w 的计算看作一棵树，树的每个分支代表非确定型的分支，结点是N的一个格局，根是起始格局。TM D在这个树上搜索接受格局。我们采用“宽度优先”策略搜索整棵树，这个策略是：在搜索一个深度内的所有分支之后，再去搜索下一个深度内的所有分支。此方法能保证 D可以访问树的所

23、有结点，直到它遇到接受格局。第26页/共34页第九章、图灵机第九章、图灵机（3）、用于模拟的确定型 TM D 有 3 个带子。根据定理 2，这等价于只有一个带子。机器 D 将这三个带子用于专门用途。第一个带子包含输入串，且不再改变；第二个带子存放N的带子中的内容，此内容对应N的非确定性计算的某个分支；第三个带子记录 D 在 N 的非确定性计算树中的位置。00 1 0 Dx x # 0 1 x 1 2 3 3 2 3 1 2 1 1 3 输入带模拟带第27页/共34页第九章、图灵机第九章、图灵机首先考虑第三个带子上表示的数据。N的每个格局确定一个集合，它是由此格局可能转移到的下一个格局组成，这些

24、下一个格局是由N的转移函数指定的。N的非确定性计算中的每个结点最多有b个子结点，其中：b是上述集合中最大的集合所含的元素个数。对树的每个结点，可以给其分配一个地址，它是字母表 b=1，2，b上的一个串。例如，把地址231分配给按以下方式到达的结点：从根出发走到它的第二个子结点，再由此走到第三个子结点，最后由此走到第一个子结点。此串中的数字告诉我们：在模拟N的非确定计算的一个分支时下一步应做什么。如果一个格局所能有的选择太少，则一个符号可能不对应任何选择。此种倩况下，地址将无效，不对应任何结点。第三个带子上包含b上的一个串，它代表N的计算树中如下分支：起点是根，终点是此串表示的地址所对应的结点，

25、除非这个地址是无效的。空串是树根的地址。第28页/共34页第九章、图灵机第九章、图灵机D的描述如下：（1）、开始时，第一个带子包含输入w，第二和第三个带子都是空的。（2）、把第一个带子复制到第二个带子上。（3）、用第二个带子去模拟N在输入w上的非确定性计算的某个分支。在N的每一步动作之前，查询第三个带子上的下一个数字，以决定在N的转移函数所允许的选择中作何选择。如果第三个带子上没有符号剩下，或这个非确定性的选择是无效的，则放弃这个分支，转到第4步。如果遇到拒绝格局也转到第4步。如果遇到接受格局，则接受这个输入。（4）、在第二个带子上，用字典顺序下的下一个串来替代原有的串。转到第2步，以模拟N的计算的下一个分支。第29页/共34页第九章、图灵机第九章、图灵机推论2、一个语言是图灵可识别的，当且仅当存在非确定型图灵机识别它