第五章图灵机2014

1、2022-6-261第第5章章 图灵机图灵机 图灵机图灵机(Turing machine)是由图灵是由图灵(Alan MathisomTuring)在在1936年提出的，它是年提出的，它是一个通用的计算模型。一个通用的计算模型。 通过研究通过研究TM，来研究递归可枚举集，来研究递归可枚举集(recursively enumerable set)和部分递归和部分递归函数函数(partial recursive function)。 对算法和可计算性进行研究提供形式化描对算法和可计算性进行研究提供形式化描述工具。述工具。2022-6-262图灵机的基本模型图灵机的基本模型图灵机图灵机(Turing

2、 Machine ，简记为，简记为TM)的基本模型的基本模型是一个是一个确定的、单带的自动机确定的、单带的自动机。它有有限个状态，有一条单向无穷延伸的存储带，它有有限个状态，有一条单向无穷延伸的存储带，带上划分为无穷多个存储单元。带上划分为无穷多个存储单元。图灵机通过图灵机通过读读/写写头，可从单元读出符号，也可往头，可从单元读出符号，也可往单元上写某些符号。单元上写某些符号。图灵机的读图灵机的读/写头可在带上写头可在带上左、右移动左、右移动做读做读/写工作。写工作。2022-6-263定义定义 一个确定的、单带图灵机一个确定的、单带图灵机M是一个八元组：是一个八元组：M =（Q，B， S ，

3、F，R）其中：其中：o Q是有穷状态集；是有穷状态集；o 是有穷的输入字母表；是有穷的输入字母表；o 是有穷的带字母表（是有穷的带字母表（ ）；）；o : QQL,R，是转移函数；，是转移函数；o B-，是空白符号；，是空白符号；o SQ，是初始状态；，是初始状态；o FQ，是接受状态；，是接受状态；o RQ，是拒绝状态。，是拒绝状态。2022-6-264例例 给出语言给出语言L= 0n1n n1，构造一个，构造一个TM M，使，使L(M)=L。具体办法是，具体办法是， 当当TM的读的读/写头遇写头遇0时，将它改写为时，将它改写为X（或其它区别于（或其它区别于0的符号），然后到右边去找的符号）

4、，然后到右边去找1； 找到找到1之后，将之后，将1改写为改写为Y（或其它区别于（或其它区别于1的符号）。的符号）。 这样往返进行下去，直到左边的这样往返进行下去，直到左边的0全部改为全部改为X，右边，右边的的1全部改为全部改为Y为止，如果没有多余的为止，如果没有多余的0或或1，TM就进就进入接受状态表示接受。入接受状态表示接受。 除此之外的其它各种情况，除此之外的其它各种情况，TM都不应当接受。都不应当接受。图灵机的语言识别图灵机的语言识别2022-6-2650 0 1 1 BX 0 1 1 B(q0,0)=(q1,X,R) 将将0改写为改写为X (q1,0)=(q1,0,R) 在在q1的控制

5、下向右找的控制下向右找1X 0 1 1 BX 0 Y 1 B(q1,1)=(q2,Y,L) 将将1改写为改写为Y,返回返回X 0 Y 1 B(q2,0)=(q2,0,L) 在在q2的控制下向左找的控制下向左找X后面的后面的0。X 0 Y 1 B (q2,X)=(q0,X,R) 遇遇X右移右移,状态改为状态改为q0 X X Y 1 B(q0,0)=(q1,X,R)X X Y 1 B(q1,Y)=(q1,Y,R) 向右找向右找1X X Y Y B(q1,1)=(q2,Y,L)X X Y Y B(q2,Y)=(q2,Y, L)(q0,Y)=(q3,Y, R) 0都改为都改为X，q0将遇到将遇到Y，状

6、态改为，状态改为q3 (q3 ，Y)=(q3 ，Y, R) 在在q3 的控制下，向右找的控制下，向右找B。 (q3 ,B)=(q4,B, 0) 0和和1的个数相等，进入接受状态。的个数相等，进入接受状态。(q2,X)=(q0,X,R) 2022-6-266(1)(3)(5)(q3 ,1)=(q5 ,1, 0) 1的个数多于的个数多于0的个数，到达拒绝状态的个数，到达拒绝状态q5 ，停机。，停机。 (11)(8)图灵机图灵机M1不接收不接收011的过程的过程 (1)(q0,0)=(q1,X,R) (2)(q1,0)=(q1,0,R) (3)(q1,1)=(q2,Y,L)(4)(q2,0)=(q2

7、,0,L) (5)(q2,X)=(q0,X,R)(6)(q1,Y)=(q1,Y,R)(7)(q2,Y)=(q2,Y, L)(8)(q0,Y)=(q3,Y, R)(9)(q3,Y)=(q3 ，Y, R) (10)(q3 ,B)=(q4,B, 0)0 1 1 Bq0X 1 1 Bq1X Y 1 Bq2X Y 1 Bq0X Y 1 Bq32022-6-267图灵机图灵机M1不接收不接收001的过程：的过程：(1)(2) (3)( 4 ) (5)(1) (6)(q1,B)=(q5,B,0) 0的个数多于的个数多于1的个数，拒绝。的个数，拒绝。 (12)(1)(q0,0)=(q1,X,R) (2)(q1

8、,0)=(q1,0,R) (3)(q1,1)=(q2,Y,L)(4)(q2,0)=(q2,0,L) (5)(q2,X)=(q0,X,R)(6)(q1,Y)=(q1,Y,R)(7)(q2,Y)=(q2,Y, L)(8)(q0,Y)=(q3,Y, R)(9)(q3,Y)=(q3,Y, R) (10)(q3,B)=(q4,B, 0)(11)(q3 ,1)=(q5,1, 0)0 0 1 Bq0X 0 1 Bq1X 0 1 Bq1X 0 Y Bq2X 0 Y Bq2X 0 Y Bq0X X Y Bq1X X Y Bq12022-6-268图灵机图灵机M1不接收不接收010的过程：的过程：(1) (3)

9、(5)(q3,0)=(q5,0, 0) 1的后面还有的后面还有0，拒绝。，拒绝。 (13) (8)(1)(q0,0)=(q1,X,R) (3)(q1,1)=(q2,Y,L)(4)(q2,0)=(q2,0,L) (5)(q2,X)=(q0,X,R)(6)(q1,Y)=(q1,Y,R)(7)(q2,Y)=(q2,Y, L)(8)(q0,Y)=(q3,Y, R)(9)(q3,Y)=(q3,Y, R) (10)(q3,B)=(q4,B, 0)(11)(q3 ,1)=(q5,1, 0) (2)(q1,0)=(q1,0,R) (12)(q1,B)=(q5,B,0)0 1 0 Bq0X 1 0 Bq1X Y

10、 0 Bq2X Y 0 Bq0X Y 0 Bq32022-6-2692022-6-2610状态状态符号符号01XYBq0 (q1,X, R) (q3 ,Y, R) q1(q1,0, R)(q2,Y, L) (q1 ,Y, R) (q5 ,B, 0) q2(q2 ,0, L) (q0 ,X, R) (q2,Y, L)q3(q5 ,0, 0) (q5 ,1, 0) (q3 ,Y, R) (q4 ,B, 0) 2022-6-2611q00011Xq1011 X0q111 Xq20Y1 q2X0Y1 Xq00Y1 XXq1Y1XXYq11 XXq2YY Xq2XYY XXq0YYXXYq3YXXYYq

11、3BXXYYBq4B 2022-6-2612例例 给出语言给出语言L= anbn+1cn+2 n0，构造一个，构造一个TM M接接受受L。 对于这类问题对于这类问题TM可以通过左右反复扫描、修改符号可以通过左右反复扫描、修改符号的办法来实现对的办法来实现对a，b，c的计数。具体方法是：的计数。具体方法是：M的的读读/写头经过一次往返，将写头经过一次往返，将a改写为改写为X，将，将b改写为改写为Y，将将c改写为改写为Z，经过，经过n次往返后，带上符号就变为次往返后，带上符号就变为XXXYYYbZZZcc。然后，再处理多余的。然后，再处理多余的b和和c即可。即可。2022-6-2613对于对于L=

12、 anbn+1cn+2 n0，构造，构造TM M：M =(q0 ,q1 ,q2 ,q3 ,q4 ,q5 ,q6 ,q7 ,q8 ，q9 ,a，b，c,X，Y，Z，凵凵a，b，c，凵，凵，q0 ，q8 ，q9 )， q0aabbbcccc (1)(q0 ,a)=(q1 ,X, R) Xq1abbbcccc 将将a改写为改写为X (2)(q1 ,a)=(q1 ,a, R) Xaq1bbbcccc 在在q1的控制下向右找的控制下向右找b (3)(q1 ,b)=(q2 ,Y, R) XaYq2bbcccc 将将b改写为改写为Y (4)(q2 ,b)=(q2 ,b, R) XaYbbq2cccc 向右找

13、向右找c (5)(q2 ,c)=(q3 ,Z, L) XaYbq3bZccc 将将c改写为改写为Z，返回。，返回。 (6)(q3 ,b)=(q3 ,b, L) Xaq3YbbZccc (7)(q3 ,Y)=(q3 ,Y, L) Xq3aYbbZccc (8)(q3 ,a)=(q3 ,a, L) q3XaYbbZccc (9)(q3 ,X)=(q0 ,X, R) Xq0aYbbZccc 遇遇X后改为后改为q0 ，转（，转（1） XXq1YbbZccc(1)(q0 ,a)=(q1 ,X, R) 2022-6-2614 XXYbbZccc (10)(q1 ,Y)=(q1 ,Y, R) XXYq1bb

14、Zccc XXYYq2bZccc (3) (q1 ,b)=(q2 ,Y, R) XXYYbq2Zccc (4) (q2 ,b)=(q2 ,b, R) (11)(q2 ,Z)=(q2 ,Z, R) XXYYbZq2ccc XXYYbq3ZZcc (5) (q2 ,c)=(q3 ,Z, L) (12)(q3 ,Z)=(q3 ,Z, L) XXYYq3bZZcc XXYq3YbZZcc (6)(q3 ,b)=(q3 ,b, L) XXq3YYbZZcc (7)(q3 ,Y)=(q3 ,Y, L) Xq3XYYbZZcc (9)(q3 ,X)=(q0 ,X, R) (13)(q0 ,Y)=(q4 ,Y

15、, R) XXq0YYbZZcc 处理多余的处理多余的b，c (14)(q4 ,Y)=(q4 ,Y, R) XXYYq4bZZcc 处理多余的处理多余的b，c (15)(q4 ,b)=(q5 ,b, R) XXYYbq5ZZcc 遇到一个遇到一个b,正常情况正常情况,转转q5 。 (16)(q5 ,Z)=(q5 ,Z, R) XXYYbZZq5cc (17)(q5 ,c)=(q6 ,c, R) XXYYbZZcq6c (18)(q6 ,c)=(q7 ,c, R) XXYYbZZccq7 遇到两个遇到两个c后，转后，转q7 。 (19)(q7 ,B)=(q8 ,B, R) q8 为接受状态，接受

16、。为接受状态，接受。 (20)(q0 ,b)=(q5 ,b, R) 处理处理n=0的情况。的情况。2022-6-2615用矩阵形式表示以上的用矩阵形式表示以上的函数函数2022-6-2616图灵机不但与其它自动机一样有图灵机不但与其它自动机一样有“识别识别”的功能的功能 （当它辨认某串是（当它辨认某串是“合法合法” 就接受，否则就不接受），就接受，否则就不接受）， 而且有而且有“计算计算”的功能（在指定数表示法的情况下，的功能（在指定数表示法的情况下，实现整数函数的求值）。实现整数函数的求值）。为了简单，用为了简单，用“一进制一进制”表示整数：表示整数：n表示整数表示整数n。 如果要计算整数函

17、数如果要计算整数函数f(x,y),则可在则可在TM的带上放的带上放0 x10y( “1”是为了将是为了将x，y隔开，别的符号也可隔开，别的符号也可)， 然后通过然后通过TM的动作，将带上符号改为的动作，将带上符号改为0f（x，y）B，即表示出计算的结果。即表示出计算的结果。因为计算因为计算f(x,y)总是有结果的，没有接受与不接受的总是有结果的，没有接受与不接受的问题，但是还是用终结状态表示计算结束比较好。问题，但是还是用终结状态表示计算结束比较好。图灵机的计算功能图灵机的计算功能2022-6-2617例例 构造一个构造一个TM M，实现非负减法。设，实现非负减法。设m，n1，m- n的定义为

18、：的定义为： m-n = 设在开始时设在开始时M的带上为的带上为0m10nB，最终变为，最终变为Bn 0m-n B。思路是，思路是，1的左边消去一个的左边消去一个0，1的右边也消去一个的右边也消去一个0，表示一次减法，如此循环重复，直到右边的表示一次减法，如此循环重复，直到右边的0都消完为都消完为止；当止；当mn时，按定义做相应处理。时，按定义做相应处理。具体的消去方法，则可以多种多样。这里采取的办法是具体的消去方法，则可以多种多样。这里采取的办法是将左边的将左边的0变为变为B，右边的，右边的0变为变为1（右边的（右边的0不能变为不能变为B，以免和带子后面的大批空白符混淆），最后再处理那些以免

19、和带子后面的大批空白符混淆），最后再处理那些无用的无用的1。nm，0,nm,nm时当时当2022-6-2618M的构造如下：的构造如下： q00000100B(1)(q0，0)=(q1，B, R) Bq1000100B 将左边的将左边的0变为变为B(2)(q1，0)=(q1，0, R) B000q1100B 在在q1的控制下向右找的控制下向右找1(3)(q1，1)=(q2，1, R) B0001q200B 找到后变为找到后变为q2(4)(q2，0)=(q3，1, L) B000q3110B 将将1后面的第一个后面的第一个0变为变为1，返回，返回(5)(q3，1)=(q3，1, L) B00q3

20、0110B 在在q3的控制下往左找空白的控制下往左找空白B(6)(q3，0)=(q3，0, L) q3B000110B 在在q3的控制下往左找空白的控制下往左找空白B(7)(q3，B)=(q0，B, R) Bq0000110B 转转(1)， BBq100110B (1) , BB00q1110B (2) , BB001q210B (8)(q2，1)=(q2，1, R) BB0011q20B BB001q311B （4） BB0q30111B (5) Bq3B00111B (6), BBq000111B （7） BBBq10111B (1) BBB0q1111B (2) , BBB01q211B

21、 (3) BBB0111q2B (8)(9)(q2，B)=(q4，B, L) BBB011q41B q2遇到遇到B，表示，表示1的右面已没有的右面已没有0,表示运算表示运算q4已经进入尾声，要消去所有的已经进入尾声，要消去所有的1。(7)(q4，1)=(q4，B, L) BBBq40BBBB 在在q4的控制下，将的控制下，将1改写为改写为B。(8)(q4，0)=(q4，0, L) BBq4B0BBBB (9)(q4，B)=(q6，0, R) BB0q60BBBB 状态状态q6 表示减法结束表示减法结束2022-6-2619在在mn的情况，计算结果带上符号为的情况，计算结果带上符号为Bn 0m-

22、nB，0的个数已经符合要的个数已经符合要求。因为图灵机的任务是计算，只要输入串按规定存放，总能得出结求。因为图灵机的任务是计算，只要输入串按规定存放，总能得出结果，所以没有接受或拒绝的问题。果，所以没有接受或拒绝的问题。对于对于mn的情况，结果是的情况，结果是0，带上应当全是空白符，因此需要单独处，带上应当全是空白符，因此需要单独处理。理。 在上述反复消去在上述反复消去0的过程中，的过程中，1左边的左边的0先被消完先被消完: 0010000B BBq011100B当当q0与与1相遇时相遇时,相应的相应的函数为：函数为： (q0，1)=(q5,B, R) BBBq51100B (q5，1)=(q

23、5，B, R) BBBBBq500B (q5，0)=(q5，B, R) BBBBBBBq5B (q5，B)=(q6，B, R) BBBBBBBBq6 在在q5的控制下，将后面的的控制下，将后面的1和和0全部变为全部变为B，直到遇见，直到遇见B才以状态才以状态q6结束。此时带上全是空白符，表示结果为结束。此时带上全是空白符，表示结果为0 。2022-6-2620 例例 构造构造TM M，对于任意非负整数，对于任意非负整数n，m，M计算计算m+n。 分析：分析：M 的输入为的输入为0n10m，输出，输出0n+m的符号串。的符号串。n和和m为为0的的情况需要特殊考虑。情况需要特殊考虑。（1）当）当n

24、和和m都不为都不为0时，我们需要将符号时，我们需要将符号1改为改为0，并将最，并将最后一个后一个0改为改为B。 q0000100B(q0，0)=(q1，0，R) 0q100100B(q1，0)=(q1，0，R) 000q1100B(q1，1)=(q1，0，R) 0000q100B 000000q1B(q1，B)=(q2，B，L) 00000q20B(q2，0)=(q3，B，R) 00000Bq3BM=(q0, q1, q2, q3, 0,1, 0,1,B, , q0, B, q3)2022-6-2621（2）当）当n为为0时，只用将时，只用将1变成变成B就完成了计算，此时无需考就完成了计算，此

25、时无需考察察m是否为是否为0； q0100B(q0，1)=(q3，B，R) Bq300B（3）当）当m为为0时，需要扫描过表示时，需要扫描过表示n的符号的符号0，并将，并将1改为改为B。 q00001B(q0，0)=(q1，0，R) 0q1001B(q1，0)=(q1，0，R) 000q11B(q1，1)=(q3，B，R) 000Bq3B2022-6-2622图灵机的程序设计技术图灵机的程序设计技术在状态中存储符号在状态中存储符号多道技术多道技术子程序技术子程序技术2022-6-2623在状态中存储符号在状态中存储符号例例 构造一个构造一个TM M，它接受下述集合：，它接受下述集合：L=01，

26、2* 10，2*20，1*。在字母表在字母表0，1，2上，上，L包含且仅包含满足以下性质的串：包含且仅包含满足以下性质的串：串中第一个符号可以是串中第一个符号可以是0，1或或2，但串中其余符号不可以和，但串中其余符号不可以和串的第一个符号相同。串的第一个符号相同。构造构造M的思想是：将第一个符号的思想是：将第一个符号“吸收吸收”到状态上，构成一到状态上，构成一个复合状态（二元组）。个复合状态（二元组）。然后这个复合状态扫视其余符号，如果那些符号和复合状态然后这个复合状态扫视其余符号，如果那些符号和复合状态所带的符号均不相同，读所带的符号均不相同，读/写头就一直右移，直到遇空白符写头就一直右移，

27、直到遇空白符而表示接受；而表示接受；否则就因输入串不在否则就因输入串不在L中而拒绝。中而拒绝。M =（q1，q2，q3，q1，0,q1，1,q1，2,0，1，2,0，1，2，B,B, q1，q2，q3），其中），其中函数为函数为:2022-6-2624 0121B(1) (q1，0)=(q1，0, 0, R) 0121B 将输入串的第一个符号将输入串的第一个符号“吸收吸收”到状态上到状态上(2) (q1，0,1)=(q1，0, 1, R) 0121B 遇非遇非0符号通过符号通过 (q1，0,2)=(q1，0, 2, R) 0121B 遇非遇非0符号通过符号通过 0121B(3) (q1，0,B

28、)=(q2 , B, 0) 0121B 遇空白符接受（遇空白符接受（q2为接受状态）为接受状态） 10220B 20110B (q1，1)=(q1，1, 1, R) (q1，1,0)=(q1，1, 0, R) 遇非遇非1符号通过符号通过 (q1，1,2)=(q1，1, 2, R) (q1，1,B)=(q2 , B, 0) (q1，2)=(q1，2, 2, R) (q1，2,0)=(q1，2, 0, R) 遇非遇非2符号通过符号通过 (q1，2,1)=(q1，2, 1, R) (q1，2,B)=(q2 , B, 0)其他其他函数都是拒绝的情况。函数都是拒绝的情况。 例如，例如，(q1，0,0)表

29、示以表示以0开头的输入串后面又遇到开头的输入串后面又遇到0，此串应被拒绝，此串应被拒绝,所以应有所以应有(q1，0,0)=（q3，0，0）（）（q3为拒绝状态）。为拒绝状态）。2022-6-2625用新状态代替复合状态用新状态代替复合状态从上可以看出，复合状态实际上就是一种新的状态，从上可以看出，复合状态实际上就是一种新的状态，可将例中的不同复合状态用不同的新状态表示：可将例中的不同复合状态用不同的新状态表示：(q0，0)=(q1, 0, R) 输入串的第一个符号为输入串的第一个符号为0，变，变1状态状态(q1, 1)=(q1，1, R) 遇非遇非0符号通过符号通过(q1，2)=(q1，2,

30、R) 遇非遇非0符号通过符号通过(q1，B)=(q4 , B, 0) 遇空白符接受（遇空白符接受（q4为接受状态）为接受状态）(q0，1)=(q2, 1, R) 输入串的第一个符号为输入串的第一个符号为1，变，变2状态状态(q2，0)=( q2, 0, R) 遇非遇非1符号通过符号通过(q2, 2)=( q2 , 2, R) 遇非遇非1符号通过符号通过(q2, B)=(q4 , B, 0) 遇空白符接受遇空白符接受(q0，2)=(q3, 2, R) 输入串的第一个符号为输入串的第一个符号为2，变，变3状态状态(q3，0)=( q3, 0, R) 遇非遇非2符号通过符号通过(q3，1)=( q3

31、, 1, R) 遇非遇非2符号通过符号通过(q3，B)=(q4 , B, 0) 遇空白符接受遇空白符接受2022-6-2626例例 构造一个构造一个TM M,它将带上的非空白符号右移它将带上的非空白符号右移2个单元格。个单元格。即将即将a1a2anB变为变为BBa1a2anB（ai为非空白符号，为非空白符号，i=1，2，n）。）。构造构造M的基本思路是，在某个状态下首先将前两个符号的基本思路是，在某个状态下首先将前两个符号a1，a2吸收进来，构成一个三元组状态，再将前两个位置变为空吸收进来，构成一个三元组状态，再将前两个位置变为空白。然后在三元组状态的控制下，将白。然后在三元组状态的控制下，将

32、a1放在放在a3的位置，将的位置，将a3吸收进三元组代替吸收进三元组代替a1，依此类推。直到最后遇空白符时，再，依此类推。直到最后遇空白符时，再将三元组中携带的最后两个符号将三元组中携带的最后两个符号an-1和和an放入最后两个空格放入最后两个空格内，就完成了移动任务。内，就完成了移动任务。2022-6-2627M的的函数如下：函数如下： abcdeBB(1) (q1, a)=( q1,B,a,B, R) BbcdeBB 将第一个符号吸到状态上将第一个符号吸到状态上(2) (q1,B,a, b)=( q1, a, b,B, R) BBcdeBB 将第二个符号也吸到状态上将第二个符号也吸到状态上

33、(3) (q1, a,b, c)=( q1, b , c, a , R) BBadeBB 将将a放在放在c的位置的位置, c放在状态上放在状态上(3) (q1, b,c, d)=( q1, c , d, b , R) BBabeBB 将将b放在放在d的位置的位置, d放在状态上放在状态上(4) (q1, c,d, e)=( q1, d , e, c , R) BBabcBB 将将c放在放在e的位置的位置, e放在状态上放在状态上(5) (q1 , d,e, B)=(q1, B ,e , d, R) BBabcdB 在空白处放倒数第二个符号在空白处放倒数第二个符号d(6) (q1 , B ,e,

34、 B)=( q2 , e, R) BBabcde 在下个空白处放最后符号在下个空白处放最后符号e， 移动完成。移动完成。2022-6-2628多道技术多道技术为了能保存和处理更复杂的数据，可以把为了能保存和处理更复杂的数据，可以把TM的带的带水平地划分为若干道，在各道上可以存放不同的符水平地划分为若干道，在各道上可以存放不同的符号。这并没有改变号。这并没有改变TM的基本模型，只是将带符号的基本模型，只是将带符号看成向量的集合，其中每个符号为一个看成向量的集合，其中每个符号为一个k维向量（维向量（k元组），这里元组），这里k为在带上划分的道数。为在带上划分的道数。 2022-6-2629例例 构

35、造一个构造一个TM M，接受，接受L= wcw wa,b+ 。为了解决这个问题，使用具有两道的带，和将符号吸收到状为了解决这个问题，使用具有两道的带，和将符号吸收到状态上这两项技术。对态上这两项技术。对M的设计思想是：输入串放在的设计思想是：输入串放在M的上道，的上道，故故=d，B d = a，b，c。例如，开始时带上为以下形。例如，开始时带上为以下形式：式：M从初始状态从初始状态q0出发，见到输入串的第一个符号出发，见到输入串的第一个符号a，将它吸，将它吸收到状态上构成二元组收到状态上构成二元组q1，a，并将，并将a的下面（第二道）空的下面（第二道）空白符换成打钩符号白符换成打钩符号“”，表

36、示看过。，表示看过。然后复合状态然后复合状态q1，a带着这个带着这个a越过中间的越过中间的c查看对应位置，查看对应位置，若对应位置也是若对应位置也是a，则在它的下面也打个钩，表示通过。，则在它的下面也打个钩，表示通过。然后再到左边看第二个符号，依此类推。然后再到左边看第二个符号，依此类推。2022-6-2630待到所有的符号（待到所有的符号（c除外）下面都打上钩，说明输入串在除外）下面都打上钩，说明输入串在L中，中，从而接受。从而接受。M在工作过程中（前面的在工作过程中（前面的b已查完，正在找已查完，正在找c后面后面的的b）带上的情况如下图所示：）带上的情况如下图所示：根据以上思路，根据以上思

37、路，M的具体构造为：的具体构造为：Q=q0 ,q8 ,q9qi ，d i=1，2，3，7；d=a，b，B。=d，B d=a，b，c。=d，X d=a，b，c；X=，BB。q0为初始状态，为初始状态，q8为终结状态为终结状态,q9为拒绝状为拒绝状态。态。2022-6-2631函数定义为：函数定义为：(1)(q0 ,a，B)=(q1，a, a, R) abbacabbaB BBBBBBBBB(2)(q0 ,b，B)=(q1，b, b, R)(3)(q1，a ,b, B)=(q1，a, b, B, R ) abbacabbaB BBBBBBBBB(4)(q1，a ,a, B)=(q1，a, a, B

38、, R ) abbacabbaB BBBBBBBBB(5)(q1，b ,a, B)=(q1，b, a, B, R )(6)(q1，b ,b, B)=(q1，b, b, B, R )2022-6-2632(7)(q1，a ,c，B)=(q2，a, c,B, R) 找到中心找到中心c，状态改为，状态改为q2，a abbacabbaB BBBBBBBBB(8)(q1，b ,c，B)=(q2，b, c,B, R)(9)(q2，a ,a，B)=(q3，B, a, L) 找到找到c右边的对应符号，打钩表示查右边的对应符号，打钩表示查完，状态改为完，状态改为q3，B，向左查下一符号。，向左查下一符号。 ab

39、bacabbaB BBBBBBBB(9)(q2，b ,b，B)=(q3，B, b, L)2022-6-2633(10)(q3，B ,c，B)=(q4，B, c,B, L) 越过中心越过中心c后，状态改为后，状态改为q4，B。 abbacabbaB BBBBBBBB(11)(q4，B ,d，B)=(q5，B, d,B, L) 遇尚未标记的符号，状态改为遇尚未标记的符号，状态改为q5，B，继续向左。，继续向左。 abbacabbaB BBBBBBBB(12)(q5，B ,d，B)=(q5，B, d,B, L) 在在q5，B的控制下，继续向左。的控制下，继续向左。 abbacabbaB BBBBBB

40、BB(13)(q5，B ,d，)=(q0, d, R) 转（转（1），继续检查下一对符号。），继续检查下一对符号。 abbacabbaB BBBBBBBBd=a，b2022-6-2634 a bbacabbaB BBBBBBB(14)(q2，d ,e，)=(q2，d, e, R) 在中心在中心c后，继续找右边的对应符后，继续找右边的对应符号号d，B。 a bbacabbaB BBBBBBB a bbaca bbaB BBB BBB(15)(q3，B ,d，)=(q3，B, d, L) 由（由（4），在），在q3，B的控制下，的控制下，继续向左找下一个尚未查看的符号。继续向左找下一个尚未查看的符

41、号。 a bbaca bbaB BBBBBBe=a，b2022-6-2635 a bbac a bbaB BBBBBB a b b a c a b b a B (16)(q4，B ,d，)=(q6，B, d, R) c左边的符号都检查完。左边的符号都检查完。(17)(q6，B ,c，B)=(q7，B, c，B, R) 又改变一次状态，又改变一次状态，由由q7，B控制向右找空白。控制向右找空白。(18)(q7，B ,d，)=( q7，B, d, R)(19)(q7，B ,B)=（q8，B，0） 左、右匹配成功，到达终结状态。左、右匹配成功，到达终结状态。在这个例子中，非法输入情况比较多，这里没有

42、列出。在这个例子中，非法输入情况比较多，这里没有列出。2022-6-2636子程序技术子程序技术子程序技术是将图灵机中重复使用的某一部分划分出来，做子程序技术是将图灵机中重复使用的某一部分划分出来，做为一个为一个“子程序子程序”。它有一个指定的开始状态（不是整个图灵机的初始状态），它有一个指定的开始状态（不是整个图灵机的初始状态），一个指定的返回状态。一个指定的返回状态。当当“主程序主程序”到达到达“子程序子程序”的开始状态时，就相当于调用的开始状态时，就相当于调用这个子程序；当子程序到达它的返回状态时，就相当于返回这个子程序；当子程序到达它的返回状态时，就相当于返回到主程序，主程序可以从这个

43、状态开始再做其它工作。到主程序，主程序可以从这个状态开始再做其它工作。子程序中除开始状态和返回状态与主程序公用外，其它在运子程序中除开始状态和返回状态与主程序公用外，其它在运行中所使用的状态都是私有的，这些状态在主程序或其它子行中所使用的状态都是私有的，这些状态在主程序或其它子程序中都不能再用。程序中都不能再用。2022-6-2637例例 构造一个构造一个TM M，实现整数的乘法运算。，实现整数的乘法运算。用图灵机实现整数乘法用图灵机实现整数乘法m*n就是当带上放就是当带上放0m10n之后，经过之后，经过TM M的的一系列操作，最后带上符号变为一系列操作，最后带上符号变为0m n 。TM M处

44、理这个问题是用最笨的方法，其基本思想是：当从处理这个问题是用最笨的方法，其基本思想是：当从1的左边的左边消去一个消去一个0后，在带的后边复制后，在带的后边复制n个个0(应与原来的应与原来的0n分隔开分隔开)；当；当1左左边的边的m个个0全部消完之后，后面自然得到乘积全部消完之后，后面自然得到乘积0m n ，然后再消去带上，然后再消去带上多余的符号就行了。多余的符号就行了。这可以看出，复制这可以看出，复制n个个0的工作是重复性的，而且是相对独立的，因的工作是重复性的，而且是相对独立的，因此将这部分工作分离出来，编成子程序的形式比较合适。此将这部分工作分离出来，编成子程序的形式比较合适。2022-

45、6-2638复制子程序复制子程序 0001B 0001000B (1)(q1 ,0)=(q2 ,2 ,R) 2 将将0改写为改写为2,以做标记。以做标记。(2)(q2 ,0)=(q2 ,0 ,R) 00 向右边找空白向右边找空白B。(3)(q2 ,1)=(q2 ,1 ,R) 1(4)(q2 ,B)=(q3 ,0 ,L) 0 找到空白后放找到空白后放0，返回。，返回。(5)(q3 ,0)=(q3 ,0 ,L)(6)(q3 ,1)=(q3 ,1 ,L)(7)(q3 ,2)=(q1 ,2 ,R) 20010B 重复重复(1)，复制下一个，复制下一个0。 220100B 2221000B (8)(q1

46、 ,1)=(q4 ,1 ,L) 3个个0都已复制完。都已复制完。(9)(q4 ,2)=(q4 ,0 ,L) 0001000 将将2恢复为恢复为0。(10)(q4 ,1)=(q5 ,1 ,R) 子程序出口，读子程序出口，读/写头仍在入口时的位置。写头仍在入口时的位置。2022-6-2639主程序主程序首先应为反复调用子程序做好准备，先将带上的符号由首先应为反复调用子程序做好准备，先将带上的符号由0m10nB变为变为B0m-110n1B ，并将读，并将读/写头移至写头移至n个个0的第一个的第一个0处，状态处，状态变为变为q1 ，就可以调用子程序了。实现上述工作序要下面一组，就可以调用子程序了。实现

47、上述工作序要下面一组函数：函数：(1) (q0 ,0)=(q6 ，B, R) 先消去第一个先消去第一个0，准备复制一次，准备复制一次n个个0。(2) (q6 ,0)=(q6 ，0, R) (3) (q6 ,1)=(q7 ，1, R)(4) (q7 ,0)=(q7 ，0, R)(5) (q7 ,B)=(q8 ，1, L) 在最后放个在最后放个1返回。返回。此时带上为此时带上为B0m-110n1B (6) (q8 ,0)=(q8 ，0, L)(7) (q8 ,1)=(q1 ，1, R) 读读/写头移至指定位置，调用子程序写头移至指定位置，调用子程序(8) (q7 ,1)=(q8 ，1, L) 因为

48、后边的因为后边的1只放一次，以后只放一次，以后q7再遇再遇1时时直接变为直接变为q8 2022-6-2640当子程序返回主程序时，状态为当子程序返回主程序时，状态为q5 ，主程序应控制从左边再，主程序应控制从左边再消去一个消去一个0，才能再进入子程序，因此还需要下面的一组，才能再进入子程序，因此还需要下面的一组函函数：数：(9) (q5 ,0)=(q9 ，0, L) 一直向左找尚未消去的第一个一直向左找尚未消去的第一个0。(10)(q9 ,1)=(q10 ，1, L)(11)(q10 ,0)=(q11 ，0, L) (12)(q11 ,0)=(q11 ，0, L) (13)(q11 ,B)=(

49、q0，B, R) 尚有未消去的尚有未消去的0，大循环重新开始。，大循环重新开始。(14)(q10 ,B)=(q12 ，B, R) m个个0已消完，大循环结束已消完，大循环结束。2022-6-2641当状态为当状态为q12时，带上符号为时，带上符号为 Bm 10n 10m nB ，为了，为了得出结果，还需要消去得出结果，还需要消去10n1，这由以下几步来实现：，这由以下几步来实现：(15)(q12 ,1)=(q13 ，B, R) 消去第一个消去第一个1。(16)(q13 ,0)=(q13 ，B, R) 消去消去n个个0。(17)(q13 ,1)=(t ，B, 0) 消去最后一个消去最后一个1，计

50、算结束。，计算结束。到此为止，带上呈到此为止，带上呈 Bm+n+2 0m nB 形式，作为形式，作为m*n的的结果表示，已经足够了。若求美观，可以设法将结结果表示，已经足够了。若求美观，可以设法将结果左移，使其在带上呈果左移，使其在带上呈0m nB 形式。形式。2022-6-2642图灵机的变型图灵机的变型双向无限带图灵机双向无限带图灵机多带图灵机多带图灵机非确定的图灵机非确定的图灵机双栈机双栈机做为枚举器的图灵机做为枚举器的图灵机2022-6-2643双向无限带双向无限带图灵机图灵机对图灵机基本模型的第一个扩充是将带的单向无限延伸对图灵机基本模型的第一个扩充是将带的单向无限延伸扩大到双向无限延伸，即不论输入串放在带的什么位置，扩大到双向无限延伸，即不论输入串放在带的什么位置，图灵机的读图灵机的读/写头都可以随意向左、右移动。其余的记号写头都可以随意向左、右移动。其余的记号和功能都和单向无限带的图灵机相同。和功能都和单向无限带的图灵机相同。图灵机的这一扩充并没有增加图