第二讲图灵机模型PPT讲稿.ppt

《第二讲图灵机模型PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第二讲图灵机模型PPT讲稿.ppt（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第二讲图灵机模型第二讲图灵机模型1第1页，共102页，编辑于2022年，星期二主要内容、重难点主要内容、重难点l主要内容主要内容图图灵灵机机作作为为一一个个计计算算模模型型，它它的的基基本本定定义义，即即时时描描述述，图图灵灵机机接接受受的的语语言言；图图灵灵机机的的构构造造技技术术；图图灵灵机机的的变变形形；Church-Turing论论题题；通通用用图图灵灵机机。可可计算语言、不可判定性、计算语言、不可判定性、P-NP问题问题)。l重点重点图灵机的定义、图灵机的定义、图灵机的构造。图灵机的构造。l难点难点图灵机的构造。图灵机的构造。2第2页，共102页，编辑于2022年，星期二2.1基本概

2、念基本概念 l图灵提出图灵机具有以下两个性质图灵提出图灵机具有以下两个性质具有有穷描述。具有有穷描述。过程必须是由离散的、可以机械执行的步骤组成。过程必须是由离散的、可以机械执行的步骤组成。l基本模型包括基本模型包括一个有穷控制器。一个有穷控制器。一条含有无穷多个带方格的输入带。一条含有无穷多个带方格的输入带。一个读头。一个读头。l一个移动将完成以下三个动作一个移动将完成以下三个动作改变有穷控制器的状态；改变有穷控制器的状态；在当前所读符号所在的带方格中印刷一个符号；在当前所读符号所在的带方格中印刷一个符号；将读头向右或者向左移一格。将读头向右或者向左移一格。3第3页，共102页，编辑于202

3、2年，星期二直观物理模型直观物理模型4第4页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机l图灵机（图灵机（Turingmachine）/基本的图灵机基本的图灵机M=(Q,q0,B,F)，lQ为为状状态态的的有有穷穷集集合合，qQ，q为为M的的一一个个状态；状态；lq0Q，是是M的的开开始始状状态态，对对于于一一个个给给定定的的输输入入串串，M从从状状态态q0启启动动，读读头头正正注注视视着着输输入入带带最左端的符号；最左端的符号；5第5页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机lF Q，是，是M的终止状态集，的终止状态集，qF，q为为M的的一

4、个终止状态。与一个终止状态。与FA和和PDA不同，一般地，不同，一般地，一旦一旦M进入终止状态，它就停止运行；进入终止状态，它就停止运行；l为为带带符符号号表表（tapesymbol），X，X为为M的的一一个个带带符符号号，表表示示在在M的的运运行行过过程程中中，X可以在某一时刻出现在输入带上；可以在某一时刻出现在输入带上；6第6页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机lB，被被称称为为空空白白符符（blanksymbol），含含有有空白符的带方格被认为是空的；空白符的带方格被认为是空的；l-B为输入字母表，为输入字母表，a，a为为M的一的一个输入符号。除了空白符

5、号个输入符号。除了空白符号B之外，只有之外，只有中中的符号才能在的符号才能在M启动时出现在输入带上；启动时出现在输入带上；7第7页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机l：QQR,L，为，为M的移动函数的移动函数（transactionfunction）。）。l(q,X)=(p,Y,R)表示表示M在状态在状态q读入符号读入符号X，将状态改为将状态改为p，并在这个，并在这个X所在的带方格中印所在的带方格中印刷符号刷符号Y，然后将读头向右移一格；，然后将读头向右移一格；l(q,X)=(p,Y,L)表示表示M在状态在状态q读入符号读入符号X，将状态改为将状态改为p，并在

6、这个，并在这个X所在的带方格中印所在的带方格中印刷符号刷符号Y，然后将读头向左移一格。，然后将读头向左移一格。8第8页，共102页，编辑于2022年，星期二例子例子2-1说明说明l例例2-1设设M1=(q0,q1,q2,0,1,0,1,B,q0,B,q2)，其中，其中的定义如下，对于此定义，也可的定义如下，对于此定义，也可以用表以用表2-1表示。表示。(q0,0)=(q0,0,R)(q0,1)=(q1,1,R)(q1,0)=(q1,0,R)(q1,B)=(q2,B,R)9第9页，共102页，编辑于2022年，星期二例子例子2-1说明说明01Bq0(q0,0,R)(q1,1,R)q1(q1,0,

7、R)(q2,B,R)q210第10页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机l即时描述即时描述(instantaneousdescription,ID)l12*，qQ，1q2称为称为M的的即时描述即时描述q为为M的当前状态。的当前状态。12为为M的输入带最左端到最右的非空白符号组成的输入带最左端到最右的非空白符号组成的符号串或者是的符号串或者是M的输入带最左端到的输入带最左端到M的读头注视的读头注视的带方格中的符号组成的符号串的带方格中的符号组成的符号串M正注视着正注视着2的最左符号。的最左符号。11第11页，共102页，编辑于2022年，星期二2.1.1基本图灵机

8、基本图灵机设设X1X2Xi-1qXiXi+1Xn是是M的一个的一个ID 如如果果(q,Xi)=(p,Y,R)，则则，M的的下下一一个个ID为为X1X2Xi-1YpXi+1Xn 记作记作X1X2Xi-1qXiXi+1XnMX1X2Xi-1YpXi+1Xn 表表示示M在在IDX1X2Xi-1qXiXi+1Xn下下，经经过过一一次次移移动，将动，将ID变成变成X1X2Xi-1YpXi+1Xn。12第12页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机l如果如果(q,Xi)=(p,Y,L)则，则，当当i1时，时，M的下一个的下一个ID为为X1X2pXi-1YXi+1Xnl记作记作

9、X1X2Xi-1qXiXi+1XnMX1X2pXi-1YXi+1Xn表示表示M在在IDX1X2Xi-1qXiXi+1Xn下，经过一次移下，经过一次移动，将动，将ID变成变成X1X2pXi-1YXi+1Xn；13第13页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机lM是是*Q*Q*上的一个二元关系上的一个二元关系 Mn表示表示M的的n次幂：次幂：Mn=(M)nM+表示表示M的正闭包：的正闭包：M+=(M)+M*表示表示M的克林闭包：的克林闭包：M*=(M)*l在意义明确时，分别用在意义明确时，分别用、n、+、*表示表示M、Mn、M+、M*。14第14页，共102页，编辑于

10、2022年，星期二2.1.1基本图灵机基本图灵机l例例2-2.例例2-1所给的所给的M1在处理输入串的过程中在处理输入串的过程中经历的经历的ID变换序列。变换序列。（1）处理输入串）处理输入串000100的过程中经历的的过程中经历的ID的变的变换序列如下：换序列如下：q0000100M0q000100M00q00100M000q0100M0001q100M00010q10M000100q1M000100Bq2 15第15页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机（2）处理输入串）处理输入串0001的过程中经历的的过程中经历的ID变换序变换序列如下：列如下：q0000

11、1M0q0001M00q001M000q01M0001q1M0001Bq2（3）处理输入串）处理输入串000101的过程中经历的的过程中经历的ID变换变换序列如下：序列如下：q0000101M0q000101M00q00101M000q0101M0001q101M00010q1116第16页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机（4）处理输入串）处理输入串1的过程中经历的的过程中经历的ID变换序列如变换序列如下：下：q01M1q1M1Bq2（5）处理输入串）处理输入串00000的过程中经历的的过程中经历的ID变换序变换序列如下：列如下：q000000M0q0000

12、0M00q0000M000q000M0000q00M00000q0B17第17页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机l图灵机接受的语言图灵机接受的语言L(M)=x|x*&q0 xM*1q2&qF&1、2*l图灵机接受的语言叫做递归可枚举语言图灵机接受的语言叫做递归可枚举语言(recursivelyenumerablelanguage，r.e.)。l如果存在图灵机如果存在图灵机M=(Q,q0,B,F)，L=L(M)，并且对每一个输入串，并且对每一个输入串x，M都停机，都停机，则称则称L为递归语言为递归语言(recursivelylanguage)。18第18页，共

13、102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机l例例2-3设有设有M2=(q0,q1,q2,q3,0,1,0,1,B,q0,B,q3)，其中，其中的定义如下：的定义如下：(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)19第19页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机01Bq0(q0,0,R)(q1,1,R)q1(q1,0,R)(q2,1,R)q2(q2,0,R)(q3,1,R)q320第20页，共102页，编辑于2

14、022年，星期二2.1.1基本图灵机基本图灵机l为了弄清楚为了弄清楚M2接受的语言，需要分析它的工作接受的语言，需要分析它的工作过程。过程。（1）处理输入串）处理输入串00010101的过程中经历的的过程中经历的ID变变换序列如下：换序列如下：q0000101010q0001010100q0010101000q0101010001q1010100010q1101000101q2010001010q2100010101q321第21页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机lM2在在q0状态下，遇到状态下，遇到0时状态仍然保持为时状态仍然保持为q0，同时将读头向右移动

15、一格而指向下一个符号；同时将读头向右移动一格而指向下一个符号；l在在q1状态下遇到第一个状态下遇到第一个1时状态改为时状态改为q1，并继，并继续右移读头，以寻找下一个续右移读头，以寻找下一个1；在遇到第二个；在遇到第二个1时，动作类似，只是将状态改为时，动作类似，只是将状态改为q2；当遇到第；当遇到第三个三个1时，进入终止状态时，进入终止状态q3，此时它正好扫描，此时它正好扫描完整个输入符号串，表示符号串被完整个输入符号串，表示符号串被M2接受。接受。22第22页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机（2）处理输入串）处理输入串1001100101100的过程中经

16、历的的过程中经历的ID变换序列如下：变换序列如下：q010011001011001q100110010110010q101100101100100q111001011001001q210010110010011q300101100lM2遇到第三个遇到第三个1时，进入终止状态时，进入终止状态q3，输入串，输入串的后缀的后缀00101100还没有被处理。但是，由于还没有被处理。但是，由于M2已经进入终止状态，表示符号串已经进入终止状态，表示符号串1001100101100被被M2接受。接受。23第23页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机（3）处理输入串）处理输入串

17、000101000的过程中经历的的过程中经历的ID变换变换序列如下：序列如下：q00001010000q00010100000q00101000000q01010000001q10100000010q11000000101q20000001010q20000010100q20000101000q2Bl当当M2的的ID变变为为000101000q2B时时，因因为为无无法法进进行行下下一个移动而停机一个移动而停机,不接受输入串不接受输入串000101000。24第24页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机lM2接受的语言是字母表接受的语言是字母表0，1上那些至少含有

18、上那些至少含有3个个1的的0、1符号串。请读者考虑，如何构造出符号串。请读者考虑，如何构造出接受字母表接受字母表0，1上那些含且恰含有上那些含且恰含有3个个1的符的符号串的号串的TM。25第25页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机l例例2-4构造构造TMM3，使，使L(M)=0n1n2n|n1。分析：分析：不能通过不能通过“数数”0、1、或者、或者2的个数来实现检查。的个数来实现检查。最为原始的方法来比较它们的个数是否是相同最为原始的方法来比较它们的个数是否是相同的：消除一个的：消除一个0、然后消除一个、然后消除一个1，最后消除一，最后消除一个个2。消除的消除

19、的0的带方格上印刷一个的带方格上印刷一个X，在消除的，在消除的1的带的带方格上印刷一个方格上印刷一个Y，在消除的，在消除的2的带方格上印刷一的带方格上印刷一个个Z。26第26页，共102页，编辑于2022年，星期二2.1.1基本图灵机基本图灵机正常情况下，输入带上的符号串的一般形式为正常情况下，输入带上的符号串的一般形式为000011112222TM启启动动后后，经经过过一一段段运运行行，输输入入带带上上的的符符号号串串的的一般情况为一般情况为XX00YY11ZZ22BB需要给予边界情况密切的关注。需要给予边界情况密切的关注。27第27页，共102页，编辑于2022年，星期二2.1.1基本图灵

20、机基本图灵机l边界情况边界情况XXXXYYYYZZ22BBXXXXYY11ZZ22BBXX00YYYYZZ22BBXX00YY11ZZZZBBXX00YYYYZZZZBB28第28页，共102页，编辑于2022年，星期二构造思路构造思路 29第29页，共102页，编辑于2022年，星期二移动函数移动函数012XYZBq0(q0,X,R)(q4,Y,R)q1(q1,0,R)(q2,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)q53

21、0第30页，共102页，编辑于2022年，星期二2.1.2图灵机作为非负整函数的计算模型图灵机作为非负整函数的计算模型 l非负整数进行编码非负整数进行编码 1进制进制 用符号串用符号串0n表示非负整数表示非负整数n。l用符号串用符号串表示表示k元函数元函数f(n1,n2,nk)的输入。如果的输入。如果f(n1,n2,nk)=m，则该，则该图灵机图灵机的输出为的输出为0m。31第31页，共102页，编辑于2022年，星期二2.1.2图灵机作为非负整函数的计算模型图灵机作为非负整函数的计算模型l图灵可计算的图灵可计算的(Turingcomputable)l设有设有k元函数元函数f(n1,n2,nk

22、)=m，TMM=(Q,q0,B,F)接受输入串接受输入串输出符号串输出符号串0m；当；当f(n1,n2,nk)无定义时，无定义时，TMM没有恰当的输出给出。称没有恰当的输出给出。称TMM计算计算k元函数元函数f(n1,n2,nk)，也称，也称f(n1,n2,nk)为为TMM计算的函数。计算的函数。也称也称f是是图灵可计算的。图灵可计算的。32第32页，共102页，编辑于2022年，星期二2.1.2图灵机作为非负整函数的计算模型图灵机作为非负整函数的计算模型l完全递归函数完全递归函数(totalrecursivefunction)设有设有k元函数元函数f(n1,n2,nk)，如果对于任意的，如果

23、对于任意的n1,n2,nk，f均有定义，也就是计算均有定义，也就是计算f的图灵的图灵机总能给出确定的输出，则称机总能给出确定的输出，则称f为完全递归函数。为完全递归函数。l部分递归函数部分递归函数(partialrecursivefunction)图灵机计算的函数称为部分递归函数。图灵机计算的函数称为部分递归函数。33第33页，共102页，编辑于2022年，星期二2.1.2图灵机作为非负整函数的计算模型图灵机作为非负整函数的计算模型l例例2-5构造构造TMM4，对于任意非负整数，对于任意非负整数n，m，M4计算计算m+n。分分析析：M4的的输输入入为为0n10m，输输出出0n+m的的符符号号串

24、串。n和和m为为0的情况需要特殊考虑。的情况需要特殊考虑。（1）当当n为为0时时，只只用用将将1变变成成B就就完完成成了了计计算算，此此时无需考察时无需考察m是否为是否为0；（2）当当m为为0时时，需需要要扫扫描描过过表表示示n的的符符号号0，并并将将1改为改为B。（3）当当n和和m都都不不为为0时时，我我们们需需要要将将符符号号1改改为为0，并将最后一个，并将最后一个0改为改为B。34第34页，共102页，编辑于2022年，星期二构造思路构造思路 35第35页，共102页，编辑于2022年，星期二M4M4=(q0,q1,q2,q3,0,1,0,1,B,q0,B,q1)(q0，1)=(q1，B

25、，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)36第36页，共102页，编辑于2022年，星期二2.1.2图灵机作为非负整函数的计算模型图灵机作为非负整函数的计算模型l例例2-6构造图灵机构造图灵机M5，对于任意非负整数，对于任意非负整数n，m，M5计算如下函数：计算如下函数：nmnm37第37页，共102页，编辑于2022年，星期二构造思路构造思路 38第38页，共102页，编辑于2022年，星期二M5 lM5=(q0,q1,q2,q3,q4,q5,q6,0,1,0,1,X,B,q0

26、,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,0,L)(q3,B)=(q0,B,R)39第39页，共102页，编辑于2022年，星期二M5(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)。40第40页，共102

27、页，编辑于2022年，星期二2.1.3图灵机的构造图灵机的构造 1.状态的有穷存储功能的利用状态的有穷存储功能的利用2.多道多道(multi-track)技术技术 3.子程序子程序(subroutine)技术技术 41第41页，共102页，编辑于2022年，星期二1.状态的有穷存储功能的利用状态的有穷存储功能的利用l例例2-7构造图灵机构造图灵机M6，使得，使得L(M6)=x|x0,1*&x中至多含中至多含3个个1。分析：分析：M6只用记录已经读到的只用记录已经读到的1的个数。的个数。q0表示当前已经读到表示当前已经读到0个个1；q1表示当前已经读到表示当前已经读到1个个1；q2表示当前已经读

28、到表示当前已经读到2个个1；q3表示当前已经读到表示当前已经读到3个个1。42第42页，共102页，编辑于2022年，星期二1.状态的有穷存储功能的利用状态的有穷存储功能的利用lM6=(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)43第43页，共1

29、02页，编辑于2022年，星期二1.状态的有穷存储功能的利用状态的有穷存储功能的利用l图灵机是要接受且仅接受恰含图灵机是要接受且仅接受恰含3个个1的的0、1串的串的图灵机，对图灵机，对M6进行修改，得到进行修改，得到M7lL(M7)=x|x0,1*&x中含且仅含中含且仅含3个个1lM7=(q0,q1,q2,q3,qf,0,1,0,1,B,q0,B,qf)44第44页，共102页，编辑于2022年，星期二L(M7)=x|x0,1*且且x中仅含中仅含3个个1(q0,0)=(q0,0,R)(q0,1)=(q1,1,R)(q1,0)=(q1,0,R)(q1,1)=(q2,1,R)(q2,0)=(q2)

30、,0,R)(q2,1)=(q3,1,R)(q3,0)=(q3,0,R)(q3,B)=(qf,B,R)45第45页，共102页，编辑于2022年，星期二L(M8)=x|x0,1*&x中至少含中至少含3个个1 M8=(q0,q1,q2,qf,0,1,0,1,B,q0,B,qf)(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)=(qf,1,R)46第46页，共102页，编辑于2022年，星期二1.状态的有穷存储功能的利用状态的有穷存储功能的利用l例例2-8构造图灵机构造图灵机M9它的输入

31、字母表为它的输入字母表为0，1，现在要求，现在要求M9在它的输入符号串的尾部添加在它的输入符号串的尾部添加子串子串101。分析：分析：将待添加子串将待添加子串101存入穷控制器。存入穷控制器。首先找到符号串的尾部。首先找到符号串的尾部。将给定符号串中的符号依次地印刷在输入带上将给定符号串中的符号依次地印刷在输入带上每印刷一个符号，就将它从有穷控制器的每印刷一个符号，就将它从有穷控制器的“存储器存储器”中删去，当该中删去，当该“存储器存储器”空时，图灵机就完成了空时，图灵机就完成了工作。工作。47第47页，共102页，编辑于2022年，星期二1.状态的有穷存储功能的利用状态的有穷存储功能的利用M

32、9=(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)48第48页，共102页，编辑于2022年，星期二1.状态的有穷存储功能的利用状态的有穷存储功能的利用l例例2-9构造图灵机构造图灵机M10它的输入字母表为它的输入字母表为0，1，要求，要求M10在它的输入符号串的开始处添加在它的输入符号串的开始处添加子串子串101。l将有穷控制器中的将有穷控制器中的“存储器存储器”分成两部分

33、分成两部分第一部分用来存放待添加的子串。第一部分用来存放待添加的子串。第二部分用来存储因添加符号串当前需要移动的输第二部分用来存储因添加符号串当前需要移动的输入带上暂时无带方格存放的子串。入带上暂时无带方格存放的子串。一般形式为一般形式为qx,ylx待添加子串待添加子串ly当前需要移动的输入带上暂时无带方格存放的子串。当前需要移动的输入带上暂时无带方格存放的子串。49第49页，共102页，编辑于2022年，星期二1.状态的有穷存储功能的利用状态的有穷存储功能的利用lqx,为开始状态；为开始状态；lq,为终止状态。为终止状态。l设设a、b为输入符号为输入符号l(qax,y,b)=(qx,yb,a

34、,R)表示在没有完成待插入子串的印刷之前，要将待插表示在没有完成待插入子串的印刷之前，要将待插入子串的首字符印刷在入子串的首字符印刷在TM当前扫描的带方格上。当前扫描的带方格上。50第50页，共102页，编辑于2022年，星期二1.状态的有穷存储功能的利用状态的有穷存储功能的利用l(q,ay,b)=(q,yb,a,R)表示表示当完成待插入子串的插入工作之后，必须将插当完成待插入子串的插入工作之后，必须将插入点之后的子串顺序地向后移动。入点之后的子串顺序地向后移动。l(q,ay,B)=(q,y,a,R)表示读头当前所指的带方格为空白，现将表示读头当前所指的带方格为空白，现将“存储器存储器”的第二

35、部分中的当前首符号的第二部分中的当前首符号a印刷在此带方格上，印刷在此带方格上，同时将这个符号从存储器中删除。同时将这个符号从存储器中删除。51第51页，共102页，编辑于2022年，星期二2.多道多道(multi-track)技术技术 l例例2-10构造构造M11，使，使L(M11)=xcy|x,y0,1+且且xy。分析：分析：以符号以符号c为分界线，逐个地将为分界线，逐个地将c前的符号与前的符号与c后的符后的符号进行比较。号进行比较。当发现对应符号不同时，就进入终止状态。当发现对应符号不同时，就进入终止状态。当发现当发现x与与y的长度不相同而进入终止状态。的长度不相同而进入终止状态。发现它

36、们相同而停机。发现它们相同而停机。一个道存放被检查的符号串，另一个存放标记符。一个道存放被检查的符号串，另一个存放标记符。52第52页，共102页，编辑于2022年，星期二构造思路构造思路 53第53页，共102页，编辑于2022年，星期二2.多道多道(multi-track)技术技术 lM11=(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,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

37、,B,a)=(p,a,L)54第54页，共102页，编辑于2022年，星期二2.多道多道(multi-track)技术技术(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)55第55页，共102页，编辑于2022年，星期二3.子程序子程序(subroutine)技术技术 l将图灵机的设计看成是一种特殊的程序设计，将图灵机的设计看成是一种特殊的程序设计，将子程序的概念引进来。将子程序的概念引进来。

38、l一个完成某一个给定功能的图灵机一个完成某一个给定功能的图灵机M从一个从一个状态状态q开始，到达某一个固定的状态开始，到达某一个固定的状态f结束。结束。l将这两个状态作为另一个图灵机将这两个状态作为另一个图灵机M的两个一般的两个一般的状态。的状态。l当当M进入状态进入状态q时，相当于启动时，相当于启动M(调用调用M对对应的子程序应的子程序)；当；当M进入状态进入状态f时，相当于返回时，相当于返回到到M的状态的状态f。56第56页，共102页，编辑于2022年，星期二3.子程序子程序(subroutine)技术技术 l例例2-11构造构造M12完成正整数的乘法运算。完成正整数的乘法运算。分析分析

39、:设两个正整数分别为设两个正整数分别为m和和n。输入串为输入串为0n10m。输出应该为输出应该为0n*m。算法思想：每次将算法思想：每次将n个个0中的中的1个个0改成改成B，就在输入，就在输入串的后面复写串的后面复写m个个0。在在M12的运行过程中，输入带的内容为的运行过程中，输入带的内容为Bh0n-h10m10m*hB 57第57页，共102页，编辑于2022年，星期二正整数的乘法运算正整数的乘法运算（1）初始化。完成将第一个）初始化。完成将第一个0变成变成B，并在最后，并在最后一个一个0后写上后写上1。我们用。我们用q0表示启动状态，用表示启动状态，用q1表示完成初始化后的状态。首先，消除

40、前表示完成初始化后的状态。首先，消除前n个个0中的第一个中的第一个0，q00n10m+Bq10n-110m1（2）主控系统。从状态）主控系统。从状态q1开始，扫描过前开始，扫描过前n个个0中剩余的中剩余的0和第一个和第一个1，将读头指向，将读头指向m个个0的第的第一个，此时的状态为一个，此时的状态为q2。其。其ID变化为变化为Bhq10n-h10m10m*(h-1)B+Bh0n-h1q20m10m*(h-1)B58第58页，共102页，编辑于2022年，星期二正整数的乘法运算正整数的乘法运算l当子程序完成当子程序完成m个个0的复写后，回到的复写后，回到q3。这个状。这个状态相当于子程序的返回（

41、终止）状态。然后在态相当于子程序的返回（终止）状态。然后在q3状态下，将读头移回到前状态下，将读头移回到前n个个0中剩余的中剩余的0中中的第一个的第一个0，并将这个，并将这个0改成改成B，进入，进入q1状态，状态，准备进行下一次循环准备进行下一次循环 Bh0n-h1q30m10m*hB+Bh+1q10n-h-110m10m*hB 59第59页，共102页，编辑于2022年，星期二正整数的乘法运算正整数的乘法运算l当完成当完成m*n个个0的复写之后，清除输入带上除的复写之后，清除输入带上除了这了这m*n个个0以外的其他非空白符号。以外的其他非空白符号。q4为终为终止状态止状态 Bnq110m10

42、m*nB+Bn+1+m+1q40m*nB（3）子子程程序序。完完成成将将m个个0复复写写到到后后面面的的任任务务。从从q2启动，到启动，到q3结束，返回到主控程序。结束，返回到主控程序。Bh+10n-h-11q20m10m*hB+Bh+10n-h-11q30m10m*h+1B 60第60页，共102页，编辑于2022年，星期二2.2图灵机的变形图灵机的变形 l从不同的方面对图灵机进行扩充。从不同的方面对图灵机进行扩充。双向无穷带图灵机。双向无穷带图灵机。多带图灵机。多带图灵机。不确定的图灵机。不确定的图灵机。多维图灵机等。多维图灵机等。l它们与基本的图灵机等价。它们与基本的图灵机等价。61第6

43、1页，共102页，编辑于2022年，星期二2.2.1双向无穷带图灵机双向无穷带图灵机物理模型物理模型 62第62页，共102页，编辑于2022年，星期二2.2.1双向无穷带图灵机双向无穷带图灵机l双向无穷带双向无穷带(Turingmachinewithtwo-wayinfinitetape)图灵机图灵机M=(Q,q0,B,F)lQ,q0,B,F的意义同定义的意义同定义9-1。l的即时描述的即时描述ID同定义同定义-2。l允许允许M的读头处在输入串的最左端时，仍然可的读头处在输入串的最左端时，仍然可以向左移动。以向左移动。63第63页，共102页，编辑于2022年，星期二2.2.1双向无穷带图灵

44、机双向无穷带图灵机lM的当前的当前IDX1X2Xi-1qXiXi+1Xnl如果如果(q,Xi)=(p,Y,R)当当i1并且并且YB时，时，M的下一个的下一个ID为为X1X2Xi-1YpXi+1Xn记作记作X1X2Xi-1qXiXi+1XnMX1X2Xi-1YpXi+1Xn表示表示M在在IDX1X2Xi-1qXiXi+1Xn下，经过一次移下，经过一次移动，将动，将ID变成变成X1X2Xi-1YpXi+1Xn。64第64页，共102页，编辑于2022年，星期二2.2.1双向无穷带图灵机双向无穷带图灵机当当i=1并且并且Y=B时，时，M的下一个的下一个ID为为pX2Xn记作记作qX1X2XnMpX2

45、Xn这就是说，和基本图灵机在读头右边全部是这就是说，和基本图灵机在读头右边全部是B时，时，这些这些B不在不在ID中出现一样，当双向无穷带图灵机的中出现一样，当双向无穷带图灵机的读头左边全部是读头左边全部是B时，这些时，这些B也不在该图灵机的也不在该图灵机的ID中出现。中出现。65第65页，共102页，编辑于2022年，星期二2.2.1双向无穷带图灵机双向无穷带图灵机l如果如果(q,Xi)=(p,Y,L)当当i1时，时，M的下一个的下一个ID为为X1X2pXi-1YXi+1Xn记作记作X1X2Xi-1qXiXi+1XnMX1X2pXi-1YXi+1Xn表示表示M在在IDX1X2Xi-1qXiXi

46、+1n下，经过一次移下，经过一次移动，将动，将ID变成变成X1X2pXi-1YXi+1Xn。66第66页，共102页，编辑于2022年，星期二2.2.1双向无穷带图灵机双向无穷带图灵机当当i=1时，时，M的下一个的下一个ID为为pBYX2Xn记作记作qX1X2XnMpBYX2Xn表示表示M在在IDqX1X2Xn下，经过一次移动，将下，经过一次移动，将ID变变成成pBYX2Xn。67第67页，共102页，编辑于2022年，星期二2.2.1双向无穷带图灵机双向无穷带图灵机定理定理2-1对于任意一个双向无穷带图灵机对于任意一个双向无穷带图灵机M，存，存在一个等价的基本图灵机在一个等价的基本图灵机M。

47、证明要点：证明要点：双双向向无无穷穷存存储储的的模模拟拟：用用一一个个具具有有2个个道道的的基基本本TM来来模模拟拟：一一个个道道存存放放M开开始始启启动动时时读读头头所所注注视视的的带带方方格格及及其其右右边边的的所所有有带带方方格格中中存存放放的的内内容容；另另一一个个道道按按照照相相反反的的顺顺序序存存放放开开始始启启动动时时读读头头所所注注视视的的带带方格左边的所有带方格中存放的内容。方格左边的所有带方格中存放的内容。双向移动的模拟：在第双向移动的模拟：在第1道上，移动的方向与原来道上，移动的方向与原来的移动方向一致，在第的移动方向一致，在第2道上，移动的方向与原来道上，移动的方向与原

48、来的移动方向相反。的移动方向相反。68第68页，共102页，编辑于2022年，星期二用单向无穷带模拟双向无穷带用单向无穷带模拟双向无穷带 69第69页，共102页，编辑于2022年，星期二2.2.2多带图灵机多带图灵机l多带图灵机多带图灵机(multi-tapeturingmachine)l允许图灵机有多个双向无穷带，每个带上有一允许图灵机有多个双向无穷带，每个带上有一个相互独立的读头。个相互独立的读头。lk带图灵机在一次移动中完成如下三个动作带图灵机在一次移动中完成如下三个动作 改变当前状态；改变当前状态；各个读头在自己所注视的带方格上印刷一个希望的符号。各个读头在自己所注视的带方格上印刷一

49、个希望的符号。各个读头向各自希望的方向移动一个带方格。各个读头向各自希望的方向移动一个带方格。70第70页，共102页，编辑于2022年，星期二2.2.2多带图灵机多带图灵机71第71页，共102页，编辑于2022年，星期二2.2.2多带图灵机多带图灵机定理定理2-2多带图灵机与基本的图灵机等价。多带图灵机与基本的图灵机等价。证明要点：证明要点：l对一个对一个k带图灵机，用一条具有带图灵机，用一条具有2k道的双向无穷道的双向无穷带图灵机带图灵机M，实现对这个，实现对这个k带图灵机带图灵机M的模拟。的模拟。l对应对应M的每一条带，的每一条带，M用两个道来实现模拟。用两个道来实现模拟。其中一条道用

50、来存放对应的带的内容，另一条其中一条道用来存放对应的带的内容，另一条道专门用来标记对应带上的读头所在的位置。道专门用来标记对应带上的读头所在的位置。72第72页，共102页，编辑于2022年，星期二2.2.3不确定的图灵机不确定的图灵机l不确定图灵机与基本图灵机的区别是对于任意不确定图灵机与基本图灵机的区别是对于任意的的(q，X)Q，(q，X)=(q1，Y1，D1)，(q2，Y2，D2)，(qk，Yk，Dk)lDj为读头的移动方向。即为读头的移动方向。即DjR，L。l表示表示M在状态在状态q，读到，读到X时，可以有选择地进入时，可以有选择地进入状态状态qj，印刷字符，印刷字符Yj，按，按Dj移