形式语言与自动机：图灵机

1、形式语言与自动机Formal Languages and Automata Theory第八章 图灵机2第八章 图灵机图灵机的提出基本概念计算模型构造方法世界上首台电子计算机-ENIAC于1946年2月诞生于美国宾夕法尼亚大学莫尔学院安装在一排2.75米高的金属柜里，占地面积为170平方米左右，总重量30吨。耗电超过174千瓦；电子管平均每隔7分钟被烧坏一只学术界公认电子计算机的理论和模型是由英国数学家图灵在此前10年前即1936年发表的一篇论文“On computable numbers with an application to the entschedungs problem”中奠定基

2、础的是关于德国大数学家希尔伯特提出的问题：是否所有数学问题都是可解的回答了这个问题：有些数学问题是不可解的，而自动计算机的理论模型则是在其论文的一个脚注中“顺便”提出来的1966年ACM纪念电子计算机诞生20周年，设立了图灵奖20世纪初，数学家希尔伯特曾计划构造一个可以判定所有数学命题真假的算法-“希尔伯特纲领”其基础是19世纪英国数学家乔治.布尔创立的布尔代数从构造判定所有的关于整数的一阶谓词演算公式的真、假的算法入手一阶谓词演算足以表示CFG产生的*中的任何句子，因此，这个问题相当于“判定一个CFL的补是否为空？”图灵机的提出1931年，奥地利25岁的数理逻辑学家哥德尔KGdel提出的关于

3、形式系统的“不完备性定理”中指出，这种形式系统是不存在的，从而宣告了著名的“希尔伯特纲领”的失败一个形式系统是不能穷尽所有的数学命题的。哥德尔构造了一个关于整数谓词演算公式，在这个逻辑系统中，既不能否定它，也不能肯定他图灵机的提出图灵的手稿早在哥德尔研究成果的影响下，图灵从计算一个数的一般过程入手对计算的本质进行了研究所谓计算就是计算者人或机器对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。用形式化方法成功表述可计算这一过程的本质。图灵机的提出提出目的 对有效的计算过程，即算法，进行形式化的描述忽略模型的

4、存储容量在内的一些枝节问题，只考虑算法的基本特征形式模型的特征 具有有穷描述过程必须是由离散的、可以机械执行的步骤组成可计算性图灵可计算性任一过程是能行的能够具体表现在一个算法中，当且仅当它能够被一台图灵机实现9.1 基本概念基本模型包括一个有穷控制器一条含有无穷多个带方格的输入带一个读头 一个移动将完成以下三个动作改变有穷控制器的状态在当前所读符号所在的带方格中写下一个符号将读头向右或者向左移一格读头输入带9.1.1 基本图灵机图灵机(Turing machine)/基本的图灵机TM M=(Q, , , , q0 , B , F) ，Q：状态的有穷集合，qQ，q为M的一个状态q0Q：M的开始

5、状态，对于一个给定的输入串，M从状态q0启动，读头正注视着输入带最左端的符号FQ：M的终止状态集，qF，q为M的一个终止状态与FA和PDA不同，一般地，一旦M进入终止状态，它就停止运行 为带符号表(tape symbol)，X，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上B：空白符(blank symbol)，含有空白符的带方格被认为是空的-B：输入字母表，a，a为M的一个输入符号；除了空白符号B之外，只有中的符号才能在M启动时出现在输入带上 图灵机(Turing machine)/基本的图灵机（续）TM M=(Q, , , , q0 , B , F) ，：QQR,

6、 L，为M的移动函数(transaction function)。 (q , X)=(p , Y, R)：M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中写下符号Y，然后将读头向右移一格；(q , X)=(p , Y , L)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中写下符号Y，然后将读头向左移一格。 q Xp Y X X Xq Xp X X Y X X X9.1.1 基本图灵机例 9-1 设M1=(q0, q1, q2, 0, 1, 0, 1, B, , q0 , B ,q2)，其中的定义如下，(q0, 0)= (q0, 0, R)(q0, 1)= (q1,

7、 1, R)(q1, 0)= (q1, 0, R)(q1, B)= (q2, B, R) 对于此定义，也可以用下表表示01Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, B, R)q2在状态q0,一旦遇上符号1，进入状态q1，遇上符号B，则进入终止状态含且只含一个1的0，1串才能将M1引导到终止状态9.1.1 基本图灵机定义9.2 及时描述 (instantaneous description, ID) 设TM M=(Q, , , , q0 , B , F) ， 12*，qQ， 1q2称为M的及时描述，其中q为M的当前状态。1 2： 当M的读头注视的符号右边还有

8、非空白符时，12为M的输入带最左端到最右的非空白符号组成的符号串； 否则， 12是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串M正注视着2的最左符号。 Yq X X Y X Y B1=XXX2=YYYq X X X Y B1=XXX2=Y设X1X2Xi-1qXiXi+1Xn是M的一个ID (1) 如果(q, Xi)=(p, Y, R)，则，M的下一个ID为X1X2Xi-1YpXi+1Xn 记作 X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，经过一次移动，将ID变成X1X2Xi-1YpXi+1Xn 。 X

9、6q X2 X3 X5 X1 X4 B X6p X2 X3 X5 X1 Y B(2) 如果(q, Xi)=(p, Y, L)则，当i1时，M的下一个ID为 X1X2Xi-2pXi-1YXi+1Xn记作 X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn,表示M在ID X1X2Xi-1qXiXi+1Xn下，经过一次移动，将ID变成X1X2pXi-1YXi+1Xn； X6q X2 X3 X5 X1 X4 B X6p X2 X3 X5 X1 Y B设X1X2Xi-1qXiXi+1Xn是M的一个ID 设X1X2Xi-1qXiXi+1Xn是M的一个ID M是*Q*Q*上的一个二元关系

10、 Mn表示M的n次幂：Mn =(M)nM+表示M的正闭包：M+ =(M)+M*表示M的克林闭包：M* =(M)*在意义明确时，分别用、n 、+、*表示M 、Mn、M+、M*。例 9-2 例 9-1所给的M1在处理输入串的过程中经历的ID变换序列。 （1）处理输入串000100的过程中经历的ID的变换序列如下：q0000100M 0q000100M 00q00100M 000q0100 M 0001q100M 00010q10M 000100 q1M 000100Bq2 （2）处理输入串0001的过程中经历的ID变换序列如下：q00001M 0q0001M 00q001M 000q01M 000

11、1q1M 0001Bq2（3）处理输入串000101的过程中经历的ID变换序列如下：q0000101M 0q000101M 00q00101M 000q0101M 0001q101M 00010q11（4）处理输入串1的过程中经历的ID变换序列如下：q01M 1q1M 1Bq2（5）处理输入串00000的过程中经历的ID变换序列如下：q000000M 0q00000M 00q0000M 000q000M 0000 q00M 00000q0B(q0, 0)= (q0, 0, R)(q0, 1)= (q1, 1, R)(q1, 0)= (q1, 0, R)(q1, B)= (q2, B, R) 符

12、号B不是输入符号，输入串不含B，但在输入串后的就是B不被M1接受9.1.1 基本图灵机定义9.3 设TM M=(Q, , , , q0 , B , F)， M接受的语言 L(M)=x | x* , q0 xM* 1 q2 , qF , 1、2* 定义9.4 TM接受的语言叫做递归可枚举语言(recursively enumerable language，r.e.)。如果存在TM M=(Q, , , , q0 , B , F)，L=L(M)，并且对每一个输入串x，M都停机，则称L为递归语言(recursively language)。 递归语言是递归可枚举语言的子类例 9-3 设有M2=(q0,

13、 q1, q2, q3,0, 1,0, 1, B,q0 , B ,q3)，其中的定义如下所示，试分析M2接受的语言 (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, 1)= (q2, 1, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q3, 1, R)9.1.1 基本图灵机01Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, 1, R)q2(q2, 0, R)(q3, 1, R)q3 首先分析M2的工作过程。（1）处理输入串00010101的过程中经历的ID变换序

14、列如下： q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101 q201000101 0 q21 00010101q3M2在q0状态下，遇到0时状态仍然保持为q0，同时将读头向右移动一格而指向下一个符号；过程：在q0状态下遇到第一个1时状态改为q1，并继续右移读头，以寻找下一个1；在遇到第二个1时，动作类似，只是将状态改为q2；当遇到第三个1时，进入终止状态q3，此时它正好扫描完整个输入符号串，表示符号串被M2接受。 01Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, 1

15、, R)q2(q2, 0, R)(q3, 1, R)q3（2）处理输入串1001100101100的过程中经历的ID变换序列如下： q01001100101100 1q1001100101100 10 q101100101100 100q11100101100 1001 q210010110010011q300101100过程：M2遇到第三个1时，进入终止状态q3，输入串的后缀00101100还没有被处理。由于M2已经进入终止状态，表示符号串1001100101100被M2接受 01Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, 1, R)q2(q2, 0, R

16、)(q3, 1, R)q3（3）处理输入串000101000的过程中经历的ID变换序列如下： q0000101000 0q000101000 00q00101000 000q0101000 0001q101000 00010q11000 000101q2000 0001010 q200 00010100 q20 000101000 q2B过程：当M2的ID变为000101000q2B时，因为无法进行下一个移动而停机,不接受输入串00010100001Bq0(q0, 0, R)(q1, 1, R)q1(q1, 0, R)(q2, 1, R)q2(q2, 0, R)(q3, 1, R)q3M2接受

17、的语言是字母表0，1上那些至少含有3个1的0、1符号串如何构造出接受字母表0，1上那些含且恰含有3个1的符号串的TM?9.1.1 基本图灵机例 9-4 构造TM M3，使L(M)=0n1n2n | n1。 分析：最为原始的方法来比较它们的个数是否是相同的：消除一个0、然后消除一个1，最后消除一个2。消除的0的带方格上印刷一个X，在消除的1的带方格上印刷一个Y，在消除的2的带方格上印刷一个Z。正常情况下，输入带上的符号串的一般形式为 000011112222TM启动后，经过一段运行，输入带上的符号串的一般情况为 XX00YY11ZZ22BB需要给予边界情况密切的关注。XXXXYYYYZZ22BB

18、XXXXYY11ZZ22BBXX00YYYYZZ22BBXX00YY11ZZZZBBXX00YYYYZZZZBB构造思路在q0, 读入0改写为X, 读头向右移动一位,到达状态q1,R在q1, M3遇到第一个未标记的1，将其标记为Y, 读头向右移动一位，然后进入状态q2在q2, M3遇到第一个未标记的2时，将其标记为Z然后进入状态q3，读头向左移动一位在q3，M3将读头向左移到输入带中的最后一个X，并回到状态q0，将读头指向第一个待处理的0,R,R,R,R,R, L, R, L, L, L, L,R,R,R,R移动函数012XYZBq0(q1,X,R)(q4,Y,R)q1(q1,0,R)(q2,

19、Y,R)(q1,Y,R)q2(q2,1,R)(q3,Z,L)(q2,Z,R)q3(q3,0,L)(q3,1,L)(q0,X,R)(q3,Y,L)(q3,Z,L)q4(q4,Y,R)(q4,Z,R)(q5,B,R)q59.2 图灵机作为非负整函数的计算模型 给非负整数进行编码 1进制 用符号串0n表示非负整数n。用符号串 表示k元函数 f(n1, n2, nk)的输入，其中1用于将n1, n2, nk隔开如果f(n1, n2, nk)=m，则该TM的输出为0m 。定义9-5 设有k元函数f(n1, n2, nk)=m，TM M=(Q, , , ,q0 , B , F)接受输入串 ，输出符号0m;

20、当f(n1, n2, nk)无定义时，TM M没有恰当的输出给出。称TM M计算k元函数 f(n1, n2, nk)或 f(n1, n2, nk)为TM M计算的函数，也称f是图灵可计算的（Turing computable）。定义9-6 设有k元函数f(n1, n2, nk)=m，如果对于任意的n1, n2, nk ，f 均有定义，也就是计算 f的TM总能给出确定的输出，则称f为完全递归函数;一般地，TM计算的函数称为部分递归函数。例：整数的加、乘、幂等运算都有确定的值，因次有限次使用这些去处构造出来的函数都是可计算的；常用的算术去处函数都是完全递归函数。图灵机构造举例例 9-5 构造TM

21、M4，对于任意非负整数n，m，M4计算n+m。 分析：M4的输入为0n10m，且M4停机时输入带上应该出现形如0n+m的符号串。 下面针对n与m的不同取值进行分析：当n为0时，只用将1变成B就完成了计算，此时无需考察m是否为0；当m为0时，需要扫描过表示n的符号0，并将1改为B；当n和m都不为0时，我们需要将符号1改为0，并将最后一个0改为B。 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1当n为0时，输入串为10m在状态q2向右扫描，直到遇到1，将其改为0，然后接着向右扫描，直到碰到B, 转向状态q3，读头向左把最后一个0改为B，使得一共只有m+n个0M4=(q0,

22、q1, q2, q3, 0,1, 0,1,B, , q0, B, q1)，其中 (q0，1)=(q1，B，R) (q0，0)=(q2，0，R) (q2，0)=(q2，0，R) (q2，1)=(q2，0，R) (q2，B)=(q3，B，L) (q3，0)=(q1，B，R),R,R,R,L,R,R例 9-6 构造TM M5，对于任意非负整数n，m，M5计算如下函数： 基本思路输入带上为：0n10m逐个消除0m中0的过程中，对应地逐个消除前0n中的0从左到右扫描，每消除前面的一个0，就到后面消除一个0特殊标记符号X：消除前面的0，填入B；消除后面的0，填入X一次循环之后如果1前面找不到0，表示nm；

23、将带上X符号都改成B，将1改成00010000B010000B01X000BB1X000BB1XX001前没有0，此时nm每次1之前的0改为B后，读头向右扫描，直到找到1后第一个0，改为X.每次1之后的0改为X后，读头向左扫描，直到找到1前的最后一个0，改为B在状态q0，遇到1之前，扫描到0，改为B，状态到达q1，读头向右扫描在状态q2, 在遇到0之前，读头向右扫描，状态不变，直到到0，改为X，状态到达q3在状态q1，遇到1之前，扫描到0，读头向右扫描，状态不变，直到遇到1，状态到达q2在状态q3，在遇到B之前，读头向左扫描，状态不变，直到遇到B，此时读头向右，到达初始状态q0, 一次循环结束

24、,R,R,R,R,R,L,L,R,R,R,R,L,R,L,L,LM5=(q0, q1, q2, q3, q4, q5, q6, 0,1, 0, 1, X, B, , q0, B, q6), 其中(q0, 0 )=(q1, B, R)(q0, 1 )=(q5, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q1, 1, R)(q1, X )=(q2, X, R)(q2, X )=(q2, X, R)(q2, 0 )=(q3, X, L)(q2, B )=(q4, B, L)(q3, X )=(q3, X, L)(q3, 1 )=(q3, 1, L)(q3, 0 )=(q3,

25、 0, L)(q3, B )=(q0, B, R)(q4, X )=(q4, B, L)(q4, 1 )=(q6, 0, R)(q5, X )=(q5, B, R)(q5, 0 )=(q5, B, R)(q5, B )=(q6, B, R)。9.1.3 图灵机的构造 1. 状态的有穷存储功能的利用 例 9-7 构造TM M6，使得L(M6)=x | x0,1*& x中至多含3个1。 分析：M6只用记录已经读到的1的个数。q0表示当前已经读到0个1；q1表示当前已经读到1个1；q2表示当前已经读到2个1；q3表示当前已经读到3个1。进入状态q3后检验在遇到B之前是否还有别的1,如果没有则进入终止

26、状态 q0q1q2q31. 状态的有穷存储功能M6=(q0, q1, q2, q3, qf, 0,1, 0,1,B, , q0, B, qf)(q0, 0 )=(q0, 0, R)(q0, 1 )=(q1, 1, R)(q0, B )=(qf, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q2, 1, R)(q1, B )=(qf, B, R)(q2, 0 )=(q2, 0, R)(q2, 1 )=(q3, 1, R)(q2, B )=(qf, B, R)(q3, 0 )=(q3, 0, R)(q3, B )=(qf, B, R)(q3, 1 )=() 不定义问题：构造

27、的TM接受恰含3个1的0，1串的图灵机1. 状态的有穷存储功能TM是要接受且仅接受恰含3个1的0、1串的TM，对M6进行修改，得到M7 L(M7) =x | x0,1*& x中含且仅含3个1 M7=(q0, q1, q2, q3, qf, 0, 1, 0, 1, B, , q0, B, qf) (q2, 0 )=(q2, 0, R)(q2, 1 )=(q3, 1, R)(q2, B )=(qf, B, R)(q3, 0 )=(q3, 0, R)(q3, B )=(qf, B, R)(q3, 1 )=() 不定义(q0, 0 )=(q0, 0, R)(q0, 1 )=(q1, 1, R)(q0,

28、 B )=(qf, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q2, 1, R)(q1, B )=(qf, B, R)L(M8)=x | x0,1*& x中至少含3个1 M8=(q0, q1, q2, qf, 0, 1, 0, 1, B, , q0, B, qf)(q2, 0 )=(q2, 0, R)(q2, 1 )=(qf, 1, R)(q2, B )=(qf, B, R)(q3, 0 )=(q3, 0, R)(q3, B )=(qf, B, R)(q3, 1 )=() 不定义(q0, 0 )=(q0, 0, R)(q0, 1 )=(q1, 1, R)(q0, B

29、)=(qf, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q2, 1, R)(q1, B )=(qf, B, R)1. 状态的有穷存储功能例9-8 构造TM M9它的输入字母表为0，1，现在要求M9在它的输入符号串的尾部添加子串101。 分析：首先找到符号串的尾部；将给定符号串（如：101）中的符号依次地印刷在输入带上 方法：将待添加子串101存入有穷控制器q101 (qay, b)=(qay, b, R) (qay, B)=(qy, a, R)每印刷一个符号，就将它从有穷控制器的“存储器”中删去，当该“存储器”空时，TM就完成了工作。找到尾部B，把a写入B所在的位置还

30、未找到尾部M9=(q101, q01, q1, q, 0, 1, 0, 1, B, , q101, B, q)其中的定义为：(q101, 0 )=(q101, 0, R)(q101, 1 )=(q101, 1, R)(q101, B )=(q01, 1, R)(q01, B )=(q1, 0, R)(q1, B )=(q, 1, R)未找到末尾找到末尾，依次把符号串101存到输入带1. 状态的有穷存储功能例 9-9 构造TM M10它的输入字母表为0，1，要求M10在它的输入符号串的开始处添加子串101。 分析：将有穷控制器中的“存储器”分成两部分第一部分用来存放待添加的子串。第二部分用来存储

31、因添加符号串当前需要移动的输入带上暂时无带方格存放的子串。 状态qx, yx待添加子串y当前需要移动的，输入带上暂时无带方格存放的子串 把101加到222前面q101, 222 1q01,2 22 10q1,22 2 101q,222B 1012q,22B 10122q,2B 101222q, B 状态qx, yx待添加子串y当前需要移动的，输入带上暂时无带方格存放的子串 qx, 为开始状态；q, 为终止状态。设a、b为输入符号(qax, y, b) = (qx, yb, a, R)表示在没有完成待插入子串的印刷之前，要将待插入子串的首字符印刷在TM当前扫描的带方格上。 (q, ay, b)

32、= (q, yb, a, R) 表示当完成待插入子串的插入工作之后，必须将插入点之后的子串顺序地向后移动。 (q,ay, B) = (q, y, a, R) 表示读头当前所指的带方格为空白，现将“存储器”的第二部分中的当前首符号a印刷在此带方格上，同时将这个符号从存储器中删除。一般形式为qx, yx待添加子串y当前需要移动的，输入带上暂时无带方格存放的子串 例 9-9 构造TM M10它的输入字母表为0，1，要求M10在它的输入符号串的开始处添加子串101。 2. 多道(multi-track)技术 例9-10 构造M11，使L(M11)=xcy | x,y0,1+ 且 xy。 分析：以符号c

33、为分界线，逐个地将c前的符号与c后的符号进行比较。什么时候进入终止状态？当发现对应符号不同时当发现x与y的长度不相同发现它们相同而停机。例9-10 构造M11，使L(M11)=xcy | x,y0,1+ 且 xy。方法：输入带分成两个道：一个道存放被检查的符号串，另一个存放标记符当对应的符号被检查过后，对应的另一道上印刷一个标记符，如当对应的符号还没有被检查时，则对应的另一道上的符号是空白符B (B, b) (B, b) (B, d) (,a)(,a)（B,c) (B, b)已经被检查已经被检查思想很简单：找到x中第一个标记为B的空格，标记为读头向左找到c，并找到y中第一个标记为B的空格，标记

34、为判断以上两个空格的符号是否相等 若不相等，则进入终止状态；否则重复以上过程，直到x,y中符号都标记完，停机。xy (, b) (, b) (B, d) (,a)(,a)（B,c) (B, b)找到x中第一个标记为B的空格，且符号不是c, 标记为读头一直向右，直到找到c，表示x结束找到y中第一个标记为B的空格，判断两个空格的符号是否相等相等读头向左，找到c读头继续向左，直到找到x中第一个标记为B的空格,L,R,L,L,R,R,R,R,R,R,R,L,R,RA, b, d, a1, a2, a3, a4, b1, b2, b3, b4都用来表示符号 0或1 M11=(q, q0, q1, p0,

35、 p1 , q, p, s, f, B,0, B,1, B,c, B,0, B,1, B,c, ,0, ,1, B,B, , q, B,B, f) (q, B,0 )=(q0, ,0, R) (q, B,1)=(q1, ,1, R)(qa, B,d)=(qa, B,d, R)(qa, B,c)=(pa, B,c, R)(pa, ,b)=(pa, ,b, R) (pa, B,a)=(p, ,a, L)(p, ,b)=(p, ,b, L) (p, B,c)=(q, B,c, L)(q, B,a)=(q, B,a, L)(q, ,a)=(q, ,a, R)(pa, B,b)=(f, B,b,R) (

36、pa, B,B)=(p, B,B, R)(s, ,b)=(s, ,b, R)(s, B,a)=(f, B,a, R)3. 子程序(subroutine)技术 将TM的设计看成是一种特殊的程序设计，将子程序的概念引进来。一个完成某一个给定功能的TM M从一个状态q开始，到达某一个固定的状态f结束。将这两个状态作为另一个TM M的两个一般的状态。当M进入状态q时，相当于启动M(调用M对应的子程序)；当M进入状态f时，相当于返回到M的状态f。例9-11 构造M12完成正整数的乘法运算。 分析:设两个正整数分别为n和m输入串为0n10m 。输出应该为0n*m 。算法思想：每次将0n中的一个0改成B，就

37、在输入串的后面复写m个0。001000B01000000BB1000000000?001000B010001B010001q002103 + Bq1011031B01q2031+ B01q303103 B010001000q0q1Bq101031+B011q2031q2初始化：将第一个0变成B，并在最后一个0后写上1从状态q1开始，扫描过前n个0中剩余的0和第一个1，将读头指向后m个0的第一个，此时的状态为q2调用子程序，在最后一个1后面复写000，到达状态q3B01q303103 + BBq1103103B BB10001000Bq3q1BB10001000000Bq4BBq1106B 当复

38、写完2*3=6个0后，清除输入带上除这6个0外的其他非空白符号 ，进入终止状态q4正整数的乘法运算（1）初始化。完成将第一个0变成B，并在最后一个0后写上1。我们用q0表示启动状态，用q1表示完成初始化后的状态。首先，消除前n个0中的第一个0，q00n10m + Bq10n-110m1（2）主控系统。从状态q1开始，扫描过前n个0中剩余的0和第一个1，将读头指向m个0的第一个，此时的状态为q2。其ID变化为Bhq10n-h10m10m*(h-1)B + Bh0n-h1 q20m10m*(h-1)B ，然后调用子程序当子程序完成m个0的复写后，回到q3。这个状态相当于子程序的返回（终止）状态。然

39、后在q3状态下，将读头移回到前n个0中剩余的0中的第一个0，并将这个0改成B，进入q1状态，准备进行下一次循环 Bh0n-h1 q30m10m*hB + Bh+1q10n-h-110m10m*hB 当完成m*n个0的复写之后，清除输入带上除了这m*n个0以外的其他非空白符号。q4为终止状态 Bnq110m10m*nB + Bn+1+m+1 q4 0m*nB（3）子程序。完成将m个0复写到后面的任务。从q2启动，到q3结束，返回到主控程序。Bh+10n-h-11 q20m10m*hB + Bh+10n-h-11 q30m10m*h+1B 9.2 图灵机的变形 从不同的方面对TM进行扩充。双向无穷

40、带TM。多带TM。不确定的TM。多维TM等。它们与基本的TM等价。好处：使相应的构造变得更容易 9.2.1 双向无穷带图灵机 双向无穷带 (Turing machine with two-way infinite tape，TM) TM M=(Q, , , ,q0 , B , F)Q, , , ,q0 , B , F的意义同定义9-1。的即时描述ID同定义-2。允许M的读头处在输入串的最左端时，仍然可以向左移动。 M的当前ID X1X2Xi-1qXiXi+1Xn 如果(q, Xi)=(p, Y, R)当i1并且YB时，M的下一个ID为X1X2Xi-1YpXi+1Xn记作X1X2Xi-1qXiX

41、i+1XnM X1X2Xi-1YpXi+1Xn表示M在ID X1X2Xi-1qXiXi+1Xn下，经过一次移动，将ID变成X1X2Xi-1YpXi+1Xn 。当i=1并且Y=B时，M的下一个ID为 pX2Xn记作 qX1X2XnM pX2Xn和基本TM在读头右边全部是B时，这些B不在ID中出现一样，当双向无穷带TM的读头左边全部是B时，这些B也不在该TM的ID中出现。 如果(q, Xi)=(p, Y, L)当i1时，M的下一个ID为X1X2pXi-1YXi+1Xn记作X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn表示M在ID X1X2Xi-1qXiXi+1n下，经过一次

42、移动，将ID变成X1X2pXi-1YXi+1Xn 。 当i=1时，M的下一个ID为pBYX2Xn记作 qX1X2XnM pBYX2Xn表示M在ID qX1X2Xn下，经过一次移动，将ID变成pBYX2Xn。9.4.1 双向无穷带图灵机定理9-1 对于任意一个双向无穷带TM M，存在一个等价的基本TM M。 证明要点： 双向无穷存储的模拟：用一个具有2个道的基本TM来模拟：一个道存放M开始启动时读头所注视的带方格(A0所在的方格)及其右边的所有带方格中存放的内容；另一个道按照相反的顺序存放M开始启动时读头所注视的带方格左边的所有带方格中存放的内容。BA-nA-1A0A1Ai AmBBA0A1Ai

43、BCA-1A-iB2. 双向移动的模拟：在第1道上，移动的方向与原来的移动方向一致，在第2道上，移动的方向与原来的移动方向相反。 定理9-1 对于任意一个双向无穷带TM M，存在一个等价的基本TM M。 证明要点（续）BA-nA-1A0A1Ai AmBB9.4.2 多带图灵机多带TM(multi-tape turing machine) 允许TM有多个双向无穷带，每个带上有一个相互独立的读头。 k带TM在一次移动中完成如下三个动作 改变当前状态； 各个读头在自己所注视的带方格上印刷一个希望的符号。 各个读头向各自希望的方向移动一个带方格。9.4.2 多带图灵机定理 9-2 多带TM与基本的TM等价。分析 ：基本TM机是多带TM的特例，因此只需证明对于做生意一个多带TM M, 都有一个与之等价的基本TM M因为单带单向无穷带的基本TM可以实现对单带双向图灵机的模拟，因此假设k个带都是单向无穷的证明要点： 对一个k带TM，用一条具有2k道的双向无穷带TM M，实现对这个k带TMM的模拟。对应M的每一条带，M用两个道来实现模拟。一条道用来存放对应的带的内容，另一条道专门用来标记对应带上的读头所在的位置。 带1的内容A0A1A10An An+1AmB读头1的位置带2的内容