《形式语言与自动机第八章--图灵机课件.ppt》由会员分享，可在线阅读，更多相关《形式语言与自动机第八章--图灵机课件.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、形式语言与自动机形式语言与自动机Formal Languages and Automata Theory第八章第八章 图灵机图灵机第八章第八章 图灵机图灵机图灵机的提出图灵机的提出基本概念基本概念计算模型计算模型构造方法构造方法2世界上首台电子计算机世界上首台电子计算机-ENIACn于于1946年年2月月诞生于美国宾夕法尼亚大学诞生于美国宾夕法尼亚大学莫尔学院莫尔学院n安装在一排安装在一排2.75米高的金属柜里，占地面米高的金属柜里，占地面积为积为170平方米左右，总重量平方米左右，总重量30吨。耗电吨。耗电超过超过174千瓦；电子管平均每隔千瓦；电子管平均每隔7分钟被烧分钟被烧坏一只坏一只n
2、学术界公认电子计算机的理论和模型是由英国数学家图灵在学术界公认电子计算机的理论和模型是由英国数学家图灵在此前此前10年前即年前即1936年年发表的一篇论文发表的一篇论文“Oncomputablenumberswithanapplicationtotheentschedungsproblem”中奠定基础的中奠定基础的p是关于德国大数学家希尔伯特提出的问题：是否所有数学问题都是可是关于德国大数学家希尔伯特提出的问题：是否所有数学问题都是可解的解的p回答了这个问题：有些数学问题是不可解的，而自动计算机的理论模回答了这个问题：有些数学问题是不可解的，而自动计算机的理论模型则是在其论文的一个脚注中型则是
3、在其论文的一个脚注中“顺便顺便”提出来的提出来的n1966年年ACM纪念电子计算机诞生纪念电子计算机诞生20周年，设立了图灵奖周年，设立了图灵奖n20世纪初，数学家世纪初，数学家希尔伯特希尔伯特曾计划构造一个曾计划构造一个可以判可以判定所有数学命题真假的定所有数学命题真假的算法算法-“希尔伯特纲领希尔伯特纲领”p其其基础是基础是19世纪英国数学家乔治世纪英国数学家乔治.布尔创立的布尔创立的布尔代数布尔代数p从从构造判定所有的关于整数的一阶谓词演算公式的真、构造判定所有的关于整数的一阶谓词演算公式的真、假的假的算法入手算法入手p一一阶谓词演算足以表示阶谓词演算足以表示CFG产生的产生的*中的任何
4、句子，因中的任何句子，因此，这个问题相当于此，这个问题相当于“判定一个判定一个CFL的补是否为空？的补是否为空？”图灵机的提出图灵机的提出n1931年，奥地利年，奥地利25岁的数理逻辑学家岁的数理逻辑学家哥德尔哥德尔KGdel 提出的关于形式系统的提出的关于形式系统的“不完备性定理不完备性定理”中指中指出，这种形式系统是不存在的，从而宣告了著名的出，这种形式系统是不存在的，从而宣告了著名的“希尔伯特纲领希尔伯特纲领”的失败的失败v一个形式系统是不能穷尽所有的数学命题的一个形式系统是不能穷尽所有的数学命题的。哥德尔构造哥德尔构造了一个关于整数谓词演算公式，在这个逻辑系统中，既不了一个关于整数谓词
5、演算公式，在这个逻辑系统中，既不能否定它，也不能肯定他能否定它，也不能肯定他图灵机的提出图灵机的提出n提出目的提出目的p 对有效的计算过程，即算法，进行形式化的描述对有效的计算过程，即算法，进行形式化的描述p忽略模型的存储容量在内的一些枝节问题，只考虑算法忽略模型的存储容量在内的一些枝节问题，只考虑算法的基本特征的基本特征n形式模型的特征形式模型的特征p 具有有穷描述具有有穷描述p过程必须是由离散的、可以机械执行的步骤组成过程必须是由离散的、可以机械执行的步骤组成n可计算性图灵可计算性图灵可计算性可计算性p任一过程是能行的任一过程是能行的 能够具体表现在一个算法中能够具体表现在一个算法中，当且
6、仅，当且仅当它能够被一台图灵机当它能够被一台图灵机实现实现9.1基本概念基本概念n基本模型包括基本模型包括p一个有穷一个有穷控制器控制器p一条含有无穷多个带方格的输入一条含有无穷多个带方格的输入带带p一个读一个读头头n一个移动将完成以下三个一个移动将完成以下三个动作动作p改变有穷控制器的改变有穷控制器的状态状态p在当前所读符号所在的带方格中写下一个在当前所读符号所在的带方格中写下一个符号符号p将读头向右或者向左移一将读头向右或者向左移一格格读头读头输入带输入带9.1.1 基本图灵机基本图灵机n图灵机图灵机(Turing machine)/(Turing machine)/基本的图灵机基本的图灵
7、机TM M=(Q,qTM M=(Q,q0 0,B,F),B,F)，pQ Q：状态状态的有穷集合，的有穷集合，qQqQ，q q为为M M的一个的一个状态状态pq q0 0Q Q：M M的的开开始始状状态态，对对于于一一个个给给定定的的输输入入串串，M M从从状状态态q q0 0启动，读头正注视着输入带最左端的启动，读头正注视着输入带最左端的符号符号pF F Q Q：M M的终止状态集，的终止状态集，qFqF，q q为为M M的一个终止状态的一个终止状态与与FAFA和和PDAPDA不同，一般地，一旦不同，一般地，一旦M M进入终止状态，它就停进入终止状态，它就停止运行止运行 p为为带带符符号号表表
8、(tape(tape symbol)symbol)，XX，X X为为M M的的一一个个带带符符号号，表表示示在在M M的的运运行行过过程程中中，X X可可以以在在某某一一时时刻刻出出现现在在输输入带入带上上pBB：空空白白符符(blank(blank symbol)symbol)，含含有有空空白白符符的的带带方方格格被被认为是空认为是空的的p-B-B：输入：输入字母表，字母表，aa，a a为为M M的一个输入的一个输入符符号；号；除了除了空白符号空白符号B B之外，只有之外，只有中的符号才能在中的符号才能在M M启动启动时出现在输入带时出现在输入带上上 9.1.1 基本图灵机基本图灵机n例例9
9、-1设设M1=(q0,q1,q2,0,1,0,1,B,q0,B,q2)，其中，其中的定义如下，的定义如下，(q0,0)=(q0,0,R)(q0,1)=(q1,1,R)(q1,0)=(q1,0,R)(q1,B)=(q2,B,R)n对于此定义，也可以用下表表示对于此定义，也可以用下表表示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及时描述及时描述(instantaneousdescription,ID
10、)设设TM M=(Q,q0,B,F)，12*，qQ，1q2称为称为M的及的及时描述，其中时描述，其中pq为为M的当前状态。的当前状态。p1 2：当当M的读头注视的符号右边还有非空白符时，的读头注视的符号右边还有非空白符时，12为为M的输入带最左端到最右的非空白符号组成的符号串；的输入带最左端到最右的非空白符号组成的符号串；否则，否则，12是是M的输入带最左端到的输入带最左端到M的读头注视的带的读头注视的带方格中的符号组成的符号串方格中的符号组成的符号串pM正注视着正注视着2的最左符号。的最左符号。YqXXYXYB1=XXX2=YYYqXXXY B1=XXX2=Y(2)如果如果(q,Xi)=(p
11、,Y,L)则，当则，当i1时，时，M的下一个的下一个ID为为 X1X2Xi-2pXi-1YXi+1Xn记作记作 X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn,表示表示M在在ID X1X2Xi-1qXiXi+1Xn下，经过一次移动，下，经过一次移动，将将ID变成变成X1X2pXi-1YXi+1Xn；X6qX2X3X5X1X4BX6pX2X3X5X1YB设设X1X2Xi-1qXiXi+1Xn是是M的一个的一个IDn例例9-2例例 9-1所给的所给的M1在处理输入串的过程在处理输入串的过程中经历的中经历的ID变换序列。变换序列。（1）处理输入串）处理输入串000100的过程
12、中经历的的过程中经历的ID的的变换序列如下：变换序列如下：q0000100M 0q000100M 00q00100M 000q0100 M 0001q100M 00010q10M 000100 q1M 000100Bq2（2）处理输入串）处理输入串0001的过程中经历的的过程中经历的ID变换变换序列如下：序列如下：q00001M 0q0001M 00q001M 000q01M 0001q1M 0001Bq2（3）处理输入串）处理输入串000101的过程中经历的的过程中经历的ID变变换序列如下：换序列如下：q0000101M 0q000101M 00q00101M 000q0101M 0001q
13、101M 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)符号符号B不是输入符号，不是输入符号，输入串不含输入串不含B，但在，但在输入串后的就是输入串后的就是B不被不被M1接受接受9.1.
14、1 基本图灵机基本图灵机定义定义9.3 设设TM M=(Q,q0,B,F)，M接受的语言接受的语言 L(M)=x|x*,q0 xM*1 q2,qF,1、2*定义定义9.4 TM接受的语言叫做接受的语言叫做递归可枚举语言递归可枚举语言(recursivelyenumerablelanguage，r.e.)。如果存在。如果存在TM M=(Q,q0,B,F)，L=L(M)，并且对每一个输入串，并且对每一个输入串x，M都停机，则称都停机，则称L为为递归语言递归语言(recursivelylanguage)。递归语言是递归可递归语言是递归可枚举语言的子类枚举语言的子类n 首先分析首先分析M2的工作过程。
15、的工作过程。（1）处理输入串的过程中经历的）处理输入串的过程中经历的ID变换序列如下：变换序列如下：q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101 q201000101 0 q21 00010101q3nM2在在q0状态下，遇到状态下，遇到0时状态仍然保持为时状态仍然保持为q0，同时将读头，同时将读头向右移动一格而指向下一个符号；向右移动一格而指向下一个符号；n过程：过程：p在在q0状态下遇到第一个状态下遇到第一个1时状态改为时状态改为q1，并继续右移读头，以，并继续右移读头，以寻找下一个寻找下一
16、个1；p在遇到第二个在遇到第二个1时，动作类似，只是将状态改为时，动作类似，只是将状态改为q2；p当遇到第三个当遇到第三个1时，进入终止状态时，进入终止状态q3，此时它正好扫描完整个，此时它正好扫描完整个输入符号串，表示符号串被输入符号串，表示符号串被M2接受。接受。01Bq0(q0,0,R)(q1,1,R)q1(q1,0,R)(q2,1,R)q2(q2,0,R)(q3,1,R)q3（2）处理输入串）处理输入串10的过程中经历的的过程中经历的ID变换序列如下：变换序列如下：q010 1q10 10 q1 100q11100101100 1001 q210010110010011q3n过程：过程
17、：pM2遇到第三个遇到第三个1时，进入终止状态时，进入终止状态q3，输入串的后缀还没有被处理。，输入串的后缀还没有被处理。p由于由于M2已经进入终止状态，表示符号串已经进入终止状态，表示符号串10被被M2接受接受01Bq0(q0,0,R)(q1,1,R)q1(q1,0,R)(q2,1,R)q2(q2,0,R)(q3,1,R)q3（3）处理输入串）处理输入串000101000的过程中经历的的过程中经历的ID变换序列如下：变换序列如下：q0000101000 0q000101000 00q0 000q0101000 0001q101000 00010q11000 000101q2000 00010
18、10 q200 00010100 q20 000101000 q2Bn过程：过程：p当当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接受的语言是字母表接受的语言是字母表0，1上那些至少含有上那些至少含有3个个1的的0、1符号串符号串如何如何构造出接受字母表构造出接受字母表0，1上那些含且恰含有上那些含且恰含有3个个1的符号串的的符号串的TM?9.1.1 基本图灵机基本图
19、灵机n例例9-4构造构造TM M3，使，使L(M)=0n1n2n|n1。分析：分析：p最为原始的方法来比较它们的个数是否是相同的：最为原始的方法来比较它们的个数是否是相同的：消除消除一个一个0、然后消除一个、然后消除一个1，最后消除一个，最后消除一个2。p消除的消除的0的带方格上印刷一个的带方格上印刷一个X，在消除的，在消除的1的带方格上的带方格上印刷一个印刷一个Y，在消除的，在消除的2的带方格上印刷一个的带方格上印刷一个Z。p正常情况下，输入带上的符号串的一般形式为正常情况下，输入带上的符号串的一般形式为p 000011112222pTM启启动动后后，经经过过一一段段运运行行，输输入入带带上
20、上的的符符号号串串的的一一般般情况为情况为 XX00YY11ZZ22BBp需要给予边界情况密切的关注。需要给予边界情况密切的关注。XXXXYYYYZZ22BBXXXXYY11ZZ22BBXX00YYYYZZ22BBXX00YY11ZZZZBBXX00YYYYZZZZBB构造思路构造思路在q0,读入0改写为X,读头向右移动一位,到达状态q1,R在q1,M3遇到第一个未标记的1，将其标记为Y,读头向右移动一位，然后进入状态q2在q2,M3遇到第一个未标记的2时，将其标记为Z然后进入状态q3，读头向左移动一位在q3，M3将读头向左移到输入带中的最后一个X，并回到状态q0，将读头指向第一个待处理的0,
21、R,R,R,R,R,L,R,L,L,L,L,R,R,R,R9.2 图灵机作为非负整函数的计算模型图灵机作为非负整函数的计算模型 n给非负整数进行编码给非负整数进行编码1进制进制p用符号串用符号串0n表示非负整数表示非负整数n。n用符号串用符号串 表示表示k元元函数函数f(n1,n2,nk)的的输入，其中输入，其中1用于将用于将n1,n2,nk隔开隔开n如果如果f(n1,n2,nk)=m，则该，则该TM的输出为的输出为0m。定义定义9-5设有设有k元函数元函数f(n1,n2,nk)=m，nTM M=(Q,q0,B,F)接受输入串接受输入串 ，输，输出符号出符号0m;n当当f(n1,n2,nk)无
22、定义时，无定义时，TMM没有恰当的输出给出。没有恰当的输出给出。称称TMM计算计算k元函数元函数f(n1,n2,nk)或或f(n1,n2,nk)为为TMM计算的函数，也称计算的函数，也称f是是图灵可计算的（图灵可计算的（Turingcomputable）。定义定义9-6设有设有k元函数元函数f(n1,n2,nk)=m，n如果如果对于任意的对于任意的n1,n2,nk，f 均均有定义，也就是有定义，也就是计算计算 f的的TM总能给出确定的输出总能给出确定的输出，则称，则称f为为完全完全递归函数递归函数;n一般一般地，地，TM计算的函数称为计算的函数称为部分递归函数部分递归函数。例：例：整数的加、乘
23、、幂等运算都有确定的值，因次有限次使用整数的加、乘、幂等运算都有确定的值，因次有限次使用这些去处构造出来的函数都是可计算的；常用的算术去处函数这些去处构造出来的函数都是可计算的；常用的算术去处函数都是完全递归函数。都是完全递归函数。图灵机构造举例图灵机构造举例n例例9-5 构造构造TM M4，对于任意非负整数，对于任意非负整数n，m，M4计算计算n+m。分分析析：M4的的输输入入为为0n10m，且且M4停停机机时时输输入入带带上上应应该该出出现现形形如如0n+m的符号串。的符号串。下面针对下面针对n与与m的不同取值进行分析：的不同取值进行分析：p当当n为为0时时，只只用用将将1变变成成B就就完
24、完成成了了计计算算，此此时时无无需需考考察察m是否为是否为0；p当当m为为0时，需要扫描过表示时，需要扫描过表示n的符号的符号0，并将，并将1改为改为B；p当当n和和m都都不不为为0时时，我我们们需需要要将将符符号号1改改为为0，并并将将最最后后一个一个0改为改为B。000010100000000001例例9-6 构造构造TM M5，对于任意非负整数，对于任意非负整数n，m，M5计算如下计算如下函数函数：n基本思路基本思路p输入带上为：输入带上为：0n10mp逐个消除逐个消除0m中中0的过程中，对应地逐个消除前的过程中，对应地逐个消除前0n中的中的0p从左到右扫描，每消除前面的一个从左到右扫描
25、，每消除前面的一个0，就到后面消除一个，就到后面消除一个0p特殊标记符号特殊标记符号X：消除前面的：消除前面的0，填入，填入B；消除后面的；消除后面的0，填入，填入Xp一次循环之后一次循环之后如如果果1前面找不到前面找不到0，表示，表示nm；将带上；将带上X符号都改成符号都改成B，将，将1改成改成0B010000B01X000BB1X000BB1XX001前没有0，此时nm每次1之前的0改为B后，读头向右扫描，直到找到1后第一个0，改为X.每次1之后的0改为X后，读头向左扫描，直到找到1前的最后一个0，改为B在状态q0，遇到1之前，扫描到0，改为B，状态到达q1，读头向右扫描在状态q2,在遇到
26、0之前，读头向右扫描，状态不变，直到到0，改为X，状态到达q3在状态q1，遇到1之前，扫描到0，读头向右扫描，状态不变，直到遇到1，状态到达q2在状态q3，在遇到B之前，读头向左扫描，状态不变，直到遇到B，此时读头向右，到达初始状态q0,一次循环结束一次循环结束,R,R,R,R,R,L,L,R,R,R,R,L,R,L,L,L9.1.3图灵机的构造图灵机的构造1.状态的有穷存储功能的利用状态的有穷存储功能的利用例例 9-7 构造构造TM M6，使得，使得L(M6)=x|x0,1*&x中中至多含至多含3个个1。分析：分析：nM6只用记录已经读到的只用记录已经读到的1的个数。的个数。q0表示当前已经
27、读到表示当前已经读到0个个1；q1表示当前已经读到表示当前已经读到1个个1；q2表示当前已经读到表示当前已经读到2个个1；q3表示当前已经读到表示当前已经读到3个个1。n进入状态进入状态q3后检验在遇到后检验在遇到B之前是否还有别的之前是否还有别的1,如果没如果没有则进入终止状态有则进入终止状态q0q1q2 q31.状态的有穷存储功能状态的有穷存储功能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,
28、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)=()不定义不定义问题：构造的问题：构造的TM接受恰含接受恰含3个个1的的0，1串的图灵机串的图灵机1.状态的有穷存储功能状态的有穷存储功能TM是要是要接受且仅接受恰含接受且仅接受恰含3个个1的的0、1串串的的TM，对，对M6进行修进行修改，得到改，得到M7nL(M7)=x|x0,1*&x中含且仅含中含且仅含3个个1nM7=(q0,q1,q2,q3,qf,0,1,0,1,B,q0,B,qf)(q2,0)=(q2,0,R)(q2
29、,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,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个个1M8=(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)(q
30、3,1)=()不定义不定义(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)1.状态的有穷存储功能状态的有穷存储功能n例例9-8 构造构造TM M9它的输入字母表为它的输入字母表为0，1，现在要求，现在要求M9在在它的输入符号串的尾部添加子串它的输入符号串的尾部添加子串101。分析：分析：p首先找到符号串的首先找到符号串的尾部；尾部；p将给定将给定符号串（如：符号串（如：101）中）中的符号依次地印刷在输入的符号依次地印刷在输入带带上上 方法：方法：p将将待添加子串
31、待添加子串101存入有穷控制器存入有穷控制器q101 (qay,b)=(qay,b,R)(qay,B)=(qy,a,R)p每每印刷一个符号，就将它从有穷控制器的印刷一个符号，就将它从有穷控制器的“存储器存储器”中中删去，当该删去，当该“存储器存储器”空时，空时，TM就完成了工作就完成了工作。找到尾部B，把a写入B所在的位置还未找到尾部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
32、,1,R)未找到末尾未找到末尾找到末尾，依次把符号串找到末尾，依次把符号串101存到输入带存到输入带1.状态的有穷存储功能状态的有穷存储功能n例例9-9构造构造TM M10它的输入字母表为它的输入字母表为0，1，要求，要求M10在它在它的输入符号串的开始处添加子串的输入符号串的开始处添加子串101。分析：分析：p将将有穷控制器中的有穷控制器中的“存储器存储器”分成两部分分成两部分第一部分用来存放待添加的子串。第一部分用来存放待添加的子串。第二部分用来存储因添加符号串当前需要移动的输入第二部分用来存储因添加符号串当前需要移动的输入带上暂时无带方格存放的子串。带上暂时无带方格存放的子串。状态状态q
33、x,yx待添加子串待添加子串y当前需要移动的，输入带上暂时无带方格存放的子串当前需要移动的，输入带上暂时无带方格存放的子串把101加到222前面q101,2221q01,22210q1,222101q,222B1012q,22B10122q,2B101222q,B状态状态qx,yx待添加子串待添加子串y当前需要移动的，输入带上暂时无带方格存放的子串当前需要移动的，输入带上暂时无带方格存放的子串pqx,为开始为开始状态；状态；q,为终止状态。为终止状态。p设设a、b为输入符号为输入符号p(qax,y,b)=(qx,yb,a,R)表示在没有完成待插入子串的印刷之前，要将待插入表示在没有完成待插入子
34、串的印刷之前，要将待插入子串的首字符印刷在子串的首字符印刷在TM当前扫描的带方格上。当前扫描的带方格上。p(q,ay,b)=(q,yb,a,R)表示表示当完成待插入子串的插入工作之后，必须将插入当完成待插入子串的插入工作之后，必须将插入点之后的子串顺序地向后移动。点之后的子串顺序地向后移动。p(q,ay,B)=(q,y,a,R)表示读头当前所指的带方格为空白，现将表示读头当前所指的带方格为空白，现将“存储器存储器”的第二部分中的当前首符号的第二部分中的当前首符号a印刷在此带方格上，同时印刷在此带方格上，同时将这个符号从存储器中删除将这个符号从存储器中删除。一般形式为一般形式为qx,yx待添加子
35、串待添加子串y当前需要移动的，输入带上暂时无带方格存放的子串当前需要移动的，输入带上暂时无带方格存放的子串例例9-9构造构造TM M10它的输入字母表为它的输入字母表为0，1，要求，要求M10在它在它的输入符号串的开始处添加子串的输入符号串的开始处添加子串101。2.多道多道(multi-track)技术技术n例例9-10 构造构造M11，使，使L(M11)=xcy|x,y0,1+且且 xy。分析：分析：p以符号以符号c为分界线，逐个地将为分界线，逐个地将c前的符号与前的符号与c后的符号进行后的符号进行比较比较。p什么时候进入终止状态？什么时候进入终止状态？当发现对应符号不当发现对应符号不同时
36、同时当发现当发现x与与y的长度不的长度不相同相同p发现它们相同而停机发现它们相同而停机。例例9-10 构造构造M11，使，使L(M11)=xcy|x,y0,1+且且 xy。n方法：方法：输入带分成两个道：一个道存放被检查的符号串，另输入带分成两个道：一个道存放被检查的符号串，另一个存放标记符一个存放标记符p当对应的符号被检查过后，对应的另一道上印刷一个标记符，如当对应的符号被检查过后，对应的另一道上印刷一个标记符，如p当对应的符号还没有被检查时，则对应的另一道上的符号是空白符当对应的符号还没有被检查时，则对应的另一道上的符号是空白符B(B,b)(B,b)(B,d)(,a)(,a)（B,c)(B
37、,b)已经被检查已经被检查思想很简单：思想很简单：1.找到找到x中第一个标记为中第一个标记为B的空的空格，标记为格，标记为2.读头向左找到读头向左找到c，并找到，并找到y中中第一个标记为第一个标记为B的空格，标记的空格，标记为为3.判断以上两个空格的符号是判断以上两个空格的符号是否相等否相等4.若不相等，则进入终止状态；若不相等，则进入终止状态；否则重复以上过程，直到否则重复以上过程，直到x,y中符号都标记完，停机。中符号都标记完，停机。xy(,b)(,b)(B,d)(,a)(,a)（B,c)(B,b)找到找到x中第一个标记为中第一个标记为B的空格，且符号不是的空格，且符号不是c,标记为标记为
38、读头一直向右，直到读头一直向右，直到找到找到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或1nM11=(q,q0,q1,p0,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,
39、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)(pa,B,B)=(p,B,B,R)(s,b)=(s,b,R)(s,B,a)=(f,B,a,R)3.子程序子程序(subroutine)技术技术n将将TM的设计看成是一种特殊的程序设计，将子程的设计看成是一种特殊的程序设计，将子程序的概念引进来。序的概念引进来。p一个完
40、成某一个给定功能的一个完成某一个给定功能的TM M从一个状态从一个状态q开始，开始，到达某一个固定的状态到达某一个固定的状态f结束。结束。p将这两个状态作为另一个将这两个状态作为另一个TM M的两个一般的状态。的两个一般的状态。p当当M进入状态进入状态q时，相当于启动时，相当于启动M(调用调用M对应的子程序对应的子程序)；当；当M进入状态进入状态f时，相当于返回到时，相当于返回到M的状态的状态f。n例例9-11 构造构造M12完成正整数的乘法运算。完成正整数的乘法运算。分析分析:p设两个正整数分别设两个正整数分别为为n和和m输入串为输入串为0n10m。输出输出应该为应该为0n*m。p算法思想：
41、算法思想：每次每次将将0n中的一个中的一个0改成改成B，就在输入串的后，就在输入串的后面复写面复写m个个0。001000B01000000BB1000000000?001000B010001B010001q002103+Bq1011031B01q2031+B01q303103 B010001000q0q1Bq101031+B011q2031q2初始化：将第一个0变成B，并在最后一个0后写上1从状态q1开始，扫描过前n个0中剩余的0和第一个1，将读头指向后m个0的第一个，此时的状态为q2调用子程序，在最后一个1后面复写000，到达状态q3B01q303103+BBq1103103B BB1000
42、1000Bq3q1BB10001000000Bq4BBq1106B 当复写完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和第一个和第一个
43、1，将读头指向，将读头指向m个个0的第一个，此时的的第一个，此时的状态为状态为q2。其。其ID变化为变化为Bhq10n-h10m10m*(h-1)B+Bh0n-h1 q20m10m*(h-1)B ，然后调用子程序然后调用子程序p当子程序完成当子程序完成m个个0的复写后，回到的复写后，回到q3。这个状态相当于。这个状态相当于子程序的返回（终止）状态。然后在子程序的返回（终止）状态。然后在q3状态下，将读头状态下，将读头移回到前移回到前n个个0中剩余的中剩余的0中的第一个中的第一个0，并将这个，并将这个0改成改成B，进入，进入q1状态，准备进行下一次循环状态，准备进行下一次循环Bh0n-h1 q3
44、0m10m*hB+Bh+1q10n-h-110m10m*hBp当完成当完成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+1B9.2 图灵机的变形图灵机的变形 n从不同的方面对从不同的方面对TM进行
45、扩充。进行扩充。p双向无穷带双向无穷带TM。p多带多带TM。p不确定的不确定的TM。p多维多维TM等。等。n它们与基本的它们与基本的TM等价。等价。n好处：使相应的构造变得更容易好处：使相应的构造变得更容易9.2.1 双向无穷带图灵机双向无穷带图灵机n 双向无穷带双向无穷带(Turing machine with two-way infinite tape，TM)TM M=(Q,q0,B,F)pQ,q0,B,F的意义同定义的意义同定义9-1。p的即时描述的即时描述ID同定义同定义-2。p允许允许M的读头处在输入串的最左端时，仍然可以向左移动的读头处在输入串的最左端时，仍然可以向左移动。pM的当
46、前的当前ID X1X2Xi-1qXiXi+1Xn n如果如果(q,Xi)=(p,Y,R)p当当i1并且并且YB时，时，M的下一个的下一个ID为为X1X2Xi-1YpXi+1Xn记作记作X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn表示表示M在在ID X1X2Xi-1qXiXi+1Xn下，经过一次移动，下，经过一次移动，将将ID变成变成X1X2Xi-1YpXi+1Xn。p当当i=1并且并且Y=B时，时，M的下一个的下一个ID为为 pX2Xn记作记作 qX1X2XnM pX2Xn和和基本基本TM在读头右边全部是在读头右边全部是B时，这些时，这些B不在不在ID中出中出现一样，
47、当双向无穷带现一样，当双向无穷带TM的读头左边全部是的读头左边全部是B时，这时，这些些B也不在该也不在该TM的的ID中出现。中出现。n如果如果(q,Xi)=(p,Y,L)p当当i1时，时，M的下一个的下一个ID为为X1X2pXi-1YXi+1Xn记作记作X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn表示表示M在在ID X1X2Xi-1qXiXi+1n下，经过一次移动，下，经过一次移动，将将ID变成变成X1X2pXi-1YXi+1Xn。p当当i=1时，时，M的下一个的下一个ID为为pBYX2Xn记作记作 qX1X2XnM pBYX2Xn表示表示M在在ID qX1X2Xn下
48、，经过一次移动，将下，经过一次移动，将ID变成变成pBYX2Xn。9.4.1 双向无穷带图灵机双向无穷带图灵机定理定理9-1 对于任意一个双向无穷带对于任意一个双向无穷带TM M，存在一个等价的基，存在一个等价的基本本TM M。证明要点：证明要点：1.双向无穷存储的模拟双向无穷存储的模拟：用用一个具有一个具有2个道的基本个道的基本TM来模拟来模拟：一一个个道道存存放放M开开始始启启动动时时读读头头所所注注视视的的带带方方格格(A0所所在在的的方方格格)及其及其右边的所有带方格中存放的内容右边的所有带方格中存放的内容；另另一一个个道道按按照照相相反反的的顺顺序序存存放放M开开始始启启动动时时读读
49、头头所所注注视视的的带方格左边的所有带方格中存放的内容带方格左边的所有带方格中存放的内容。BA-nA-1A0A1AiAmBBA0A1AiBCA-1A-iB2.双向移动的模拟：双向移动的模拟：在第在第1道上，移动的方向与原来的移动方向一致，道上，移动的方向与原来的移动方向一致，在第在第2道上，移动的方向与原来的移动方向相反。道上，移动的方向与原来的移动方向相反。定理9-1 对于任意一个双向无穷带TM M，存在一个等价的基本TM M。证明要点（续）BA-nA-1A0A1AiAmBB9.4.2多带图灵机多带图灵机n多带多带TM(multi-tape turing machine)p允许允许TM有多个
50、双向无穷带，每个带上有一个相互独立的读头。有多个双向无穷带，每个带上有一个相互独立的读头。pk带带TM在一次移动中完成如下三个动作在一次移动中完成如下三个动作 改变当前状态；改变当前状态；各个读头在自己所注视的带方格上印刷一个希望的符号。各个读头在自己所注视的带方格上印刷一个希望的符号。各个读头向各自希望的方向移动一个带方格各个读头向各自希望的方向移动一个带方格。9.4.2多带图灵机多带图灵机定理定理9-2 多带多带TM与基本的与基本的TM等价。等价。分析分析：p基本基本TM机是多带机是多带TM的特例，因此只需证明对于做生意一个多带的特例，因此只需证明对于做生意一个多带TMM,都有一个与之等价