《形式语言与自动机》课件ch5.1-5.3.ppt

1、1School of Computer Science,BUPT第五章第五章 图灵机图灵机A.Turing在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质n该模型的每个过程都是有穷可描述的；n过程必须是由离散的、可以机械执行的步骤组成。图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。n通过研究TM来研究递归可枚举集和部分递归函数n为算法和可计算性研究提供了形式化描述工具。2School of Computer Science,BUPT主要内容主要内容nTM的基本定义nTM的格局nTM接受的语言nTM的构造技术nTM的变形；n重点:TM的定义、TM的

2、构造。n难点:TM的构造。3School of Computer Science,BUPTFinitecontrolX1BB.X2XnXi带（带（tape）单元格（单元格（cell）带符（带符（tape symbol）n 读写头在每一时刻扫描带上的一个单元读写头在每一时刻扫描带上的一个单元n 带有一个最左单元，向右则是无限的。带有一个最左单元，向右则是无限的。n 带的每个单元可容纳一个带符号带的每个单元可容纳一个带符号开始时，最左边开始时，最左边n个单元装着输入（个单元装着输入（n0，n为有限数），它是为有限数），它是一个字符串，符号都选自一个字符串，符号都选自“带符号带符号”的一个子集，即所

3、谓的的一个子集，即所谓的“输输入符号集合入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但的带符号，但不是不是输入符号。输入符号。图灵机的基本模型4School of Computer Science,BUPT在一个图灵机的动作中，图灵机根据带头（读写在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作头）所扫描的符号和有限控制器的状态可能作n改变状态n在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.n将带头向左或者右移一个单元。*图灵机和双向有限自动机的区别：图灵机能改变图灵机和双向有

4、限自动机的区别：图灵机能改变它带上的符号。它带上的符号。图灵机的工作机制5School of Computer Science,BUPT图灵机的形式化描述图灵机的形式化描述 有限状态集 有限输入符号集 有限带符号集 转移函数 开始状态 特殊带符:空白符 终态集合q0 Q T B T F Q转移函数转移函数 :Q Q L,R 形式定义形式定义 一个图灵机一个图灵机 TM(Turing machine)是一个七元组是一个七元组 M=(Q,T,q0,B,F).6School of Computer Science,BUPTn函数示例：函数示例：Q Q Q QL,RL,R(q,a(q,ai i)=(p

5、,b,L)q,p Q)=(p,b,L)q,p Q (q,a (q,ai i)=(p,b,R)a)=(p,b,R)ai i b b n格局格局用w1q w2描述图灵机的瞬间工作状态q为M的当前状态，w1w2*w1w2是当前时刻从开始端（因为可写）到右边空白符号为止的内容当读写头已达到带的右端，则w1w2为读写头以左的内容。约定：约定：w w1 1q wq w2 2表示读写头正扫描表示读写头正扫描w w2 2的最左字符的最左字符w w2 2 则表示读写头正扫描一个空白字符。则表示读写头正扫描一个空白字符。图灵机的函数与格局7School of Computer Science,BUPT图灵机的格局

6、图灵机的格局 给定图灵机给定图灵机 M=(Q,T,q0,B,F)，定义格局之间定义格局之间的推导关系的推导关系M 如下：如下：1.设设 (q,Xi)=(p,Y,L)，则有则有 X1X2Xi-1qXiXi+1Xn M X1X2Xi-2pXi-1YXn，但有如下两个例外但有如下两个例外：（1）i=1时，时，qX1X2Xn M qYX2Xn，和和 （2）i=n及及 Y=B 时，时，X1X2Xn-1qXn M X1X2Xn-2pXn-1 B.2.设设 (q,Xi)=(p,Y,R)，则有则有 X1X2Xi-1 q XiXi+1Xn M X1X2Xi-1Y p Xi+1Xn，但有如下两个例外但有如下两个例

7、外：（1）i=n时，时，X1X2Xn-1q Xn M X1X2Xn-1Y p B，和和 （2）i=1及及 Y=B 时，时，q X1X2XnM B p X2Xn-1Xn.8School of Computer Science,BUPT图灵机接受的语言图灵机接受的语言L(M)=TT*且且q q0 0*1 1 p p 2 2 ,pF,pF,1 12 2*图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在M的带上，M处于状态q0，且M的带头处在最左单元上，这些字符串将使M进入某个终止状态。假定：假定：当输入被接受时，图灵机将停止，没有下一个动作。9School of Compu

8、ter Science,BUPT图灵机举例图灵机举例例例1 1：设语言：设语言 L=aL=an n b bn nn=1n=1，设计图灵机接受设计图灵机接受L L。思路：最初带上为思路：最初带上为 a aa a a b ba b b b B B B b B B B n n个个a na n个个b b首先用首先用x x替换替换M M最左边的最左边的a a，再右移至最左边的再右移至最左边的b b用用y y替换之，左移替换之，左移寻找最右的寻找最右的x x，然后右移一单元到最左的然后右移一单元到最左的a a，重复循环。重复循环。如果如果（1 1）当在搜寻）当在搜寻b b时，时，M M找到了空白符找到了空

9、白符B B，则则M M停止，不接受该串。停止，不接受该串。（此时，（此时，a a的个数大于的个数大于b b的个数）的个数）（2 2）当将当将b b改为改为y y后，左边再也找不到后，左边再也找不到a a，此时此时,若右边再无若右边再无b b，接受；若仍有接受；若仍有b b，则则b b的个数大于的个数大于a a的个数，不接受。的个数，不接受。10School of Computer Science,BUPT 动作 写的符号 q0 q1 a/x a/a,y/y b/y y/y x/x a/a,y/y q3 y/y q2 B/B q4 R R R R L 例例1 L=an bnn=1(q0,a)=(

10、q1,x,R)(q0,y)=(q3,y,R)(q1,a)=(q1,a,R)(q1,y)=(q1,y,R)(q1,b)=(q2,y,L)(q2,a)=(q2,a,L)(q2,y)=(q2,y,L)(q2,x)=(q0,x,R)(q3,y)=(q3,y,R)(q3,B)=(q4,B,R)例：例：aabbaabb的接收格局序列的接收格局序列q q0 0aabb xqaabb xq1 1abb xaqabb xaq1 1bb xqbb xq2 2ayb qayb q2 2xaybxqxaybxq0 0aybxxqaybxxq1 1ybyb xxyq xxyq1 1bxxqbxxq2 2yyxqyyxq

11、2 2xyyxxqxyyxxq0 0yyxxyqyyxxyq3 3yxxyyqyxxyyq3 3BxxyyqBxxyyq4 4 11School of Computer Science,BUPTStartq6q1q00/Xq4Y/Y0/0Y/Y0/0X/XY/YB/BY/Yq31/Yq2Z/Z1/12/ZZ/Z1/1q5Z/ZZ/Z对于输入字符串对于输入字符串001122，该图灵机可以有如下推导该图灵机可以有如下推导步：步：q0001122MXq101122 MX0q11122MX0Yq2122MX0Y1q222MX0Yq31Z2*Mq3X0Y1Z2MXq00Y1Z2*MXXYYZq22MXX

12、YYq3ZZ*MXq3XYYZZMXXq0YYZZ*MXXYYq4ZZMXXYYZq5ZMXXYYZZq5BMXXYYZZBq6B例例2 L=0n1n2n n 1.12School of Computer Science,BUPT 转移图与转移表转移图与转移表Startq6q1q00/Xq4Y/Y0/0Y/Y0/0X/XY/YB/BY/Yq31/Yq2Z/Z1/12/ZZ/Z1/1q5Z/ZZ/ZStateq1q0q2q3q4(q1,X,R)(q1,0,R)(q2,Y,R)(q2,1,R)(q4,Y,R)(q1,Y,R)(q3,Y,L)Symbol01XYB(q2,Z,R)(q3,Z,L)Zq

13、5q6(q6,B,R)(q3,0,L)(q3,1,L)(q0,X,R)(q4,Y,R)(q5,Z,R)(q5,Z,R)2(q3,Z,L)13School of Computer Science,BUPT 作为整数函数计算机的图灵机作为整数函数计算机的图灵机n预备知识：预备知识：图灵机除了作为语言接受器外，还可看作整数到整数的函数计算机。n传统方法把整数表示成一进制传统方法把整数表示成一进制整数 i 0 用字符串 0i 表示n如果一个函数有k个自变量，i1,i2,ik，那么这些整数开始时被放在带上，并用1把他们分隔开。形如 0i1 1 0i2 1 0i3 1 0ikn如果图灵机停止(不论是否在一

14、个接受状态上)且带上为 0m，则 f(i1,i2,ik)=m f是被图灵机计算的k元函数n如果f（i1,i2,ik）对所有i1,i2,ik有定义,那么称f是一个全递归函数。全递归函数对应于递归语言，因为它总是被能停下来的图灵机所计算。n所有常用的整数算术函数都是全递归函数。14School of Computer Science,BUPT例例3 3：设计图灵机求真减法：设计图灵机求真减法n思路：思路：1.用空白符B代替带上的最左端的02右移至紧跟1后的0,将其改为13左移找到B，将B之后的0改为B4重复上述过程如果如果（1）右移找0时，遇到B，意味着mnBBB 0 m-(n+1)1 111 n

15、+1 n个将后面n+1个1变为B，将左侧最后一个B变0，形如BBB 0 0 m-(n+1)BBB n个 n+1个 这时，带上留下m-n个0，即结果为m-n 0 mn mnmnmnn 初始带 0m 10n15School of Computer Science,BUPT求真减法（续）求真减法（续）(2)M左移找不到0，意味着 n m，形如 BBB 1 111 00 m个 m个 n-m个 此时,用B替换所有剩余的1 和0 0/0,1/1 q3 B/B 0/1 1/1 q0 0/0 1/1 0/B q1 q2 1/B B/B q6 q5 q4 B/B B/0 0/B,1/B 0/0,1/B L R

16、R R R R L 16School of Computer Science,BUPT例例4 4：L=L=0 0 m m m=2 m=2n n,n,n 0 0 n设计思路：对输入串设计思路：对输入串w w 1.从左到右扫描带，隔一个消一个0；2若带上只剩唯一一个0,接受；3若带上不止一个0,且个数为奇数，拒绝；4让读写头返回带的最左端；5.转第一步。17School of Computer Science,BUPTStartq4q2q10/#,RqrejectX/X,RB/B,Rq3B/B,Racceptqq5#/#,RB/B,LX/X,L0/0,L0/X,RX/X,RX/X,R0/X,R0/

17、0,R识别识别 L=L=0 0 m m m=2 m=2n n,n,n 0 0 的的图灵机图灵机18School of Computer Science,BUPT 任给图灵机任给图灵机 M=(Q,T,q0,B,F)，以及输入字符串以及输入字符串w T*.试问：试问：对于对于w，M 是否停机是否停机？停机是指图灵机不存在下一个移动步（停机是指图灵机不存在下一个移动步（move）.结论结论 图灵机的停机问题是不可解的（即不可判定的）图灵机的停机问题是不可解的（即不可判定的）.利用反证法证明假定存在一个能够判定任意一台图灵机是否停机的万能图灵机 H(M),如果 M 最终停机,H 输出 halt;如果

18、M 不停机,H 输出 loop.我们把 H 当作子程序,构造如下程序 P:function P(M)if(H(M)=loop)return halt;else if(H(M)=halt)while(true);/loop forever 因为 P 本身也是一台图灵机,可以表示为一个字符串,所以我们可以把 P 输入给它自己,然后问 P(P)是否停机.按照程序 P 的流程,如果 P 不停机无限循环,那么它就停机,输出halt;如果 P 停机,那么它就无限循环,不停机;这样无论如何我们都将得到一个矛盾,所以假设前提不成立,即不存在这样的 H.或者说,图灵机停机问题是不可判定的(undecidable

19、).图灵机的停机问题图灵机的停机问题 19School of Computer Science,BUPTn结论结论 任给图灵机任给图灵机 M，很容易构造一个图灵机很容易构造一个图灵机 M，使得使得L(M)=L(M )，并满足：如果并满足：如果w L(M)，则对于则对于 w，M 接受接受w并一定停机并一定停机.n 如果没有特别指出，总是假定图灵机到达终态如果没有特别指出，总是假定图灵机到达终态（接受态）后一定停机（接受态）后一定停机.n 但是但是，对不能接受的字符串，图灵机可能永不对不能接受的字符串，图灵机可能永不停止停止.（只要（只要M还在某个输入上运行，我们无法知道还在某个输入上运行，我们无

20、法知道是因为运行的时间不够长而没有被接受，还是根本是因为运行的时间不够长而没有被接受，还是根本就不会停机）就不会停机）20School of Computer Science,BUPT5.2 图灵机的构造技术 在设计图灵机的过程中，写出函数很麻烦，为了构造复杂的图灵机，需探讨图灵机的若干构造技术，并引入一些新的概念和工具。目的：设计时方便，但这些构造技术并未增加图灵机的功能。21School of Computer Science,BUPT5.2.1.利用带存储区的状态利用带存储区的状态（storage in the state）此类此类图灵机图灵机 M=(Q,q0,B,F)中，状态中可以包含

21、中，状态中可以包含一个具有有限个取值的存储单元，即状态集合为一个具有有限个取值的存储单元，即状态集合为 Q=S T=q,a|q S a T，其中其中 q S 通常表示控制状态，而通常表示控制状态，而 a T 通常表示数据元素通常表示数据元素.一般情况下，有限控制器内允许存储一般情况下，有限控制器内允许存储n个字符，即状态的第个字符，即状态的第2个元素可存储个元素可存储n个字符。个字符。qabcStateStorageBX1BBB.X2XnXi22School of Computer Science,BUPT例：设计一个图灵机，读写头将扫视第一个字符存入有限控制器内，然后扫视例：设计一个图灵机，

22、读写头将扫视第一个字符存入有限控制器内，然后扫视整个带，若找不到与第一个相同的字符，则整个带，若找不到与第一个相同的字符，则M接受该字符串，否则不接受。接受该字符串，否则不接受。构造构造M=(Q,a,b,a,b,B,q0,B,F)其中其中Q=q0,q1a,b,B=q0,a,q0,b,q0,Bq1,aq1,bq1,B初态初态q0,B终态终态F=q1,B 函数：函数：(q0,B,a)=(q1,a,a,R)(q0,B,b)=(q1,b,b,R)存第一个字符存第一个字符(q1,a,b)=(q1,a,b,R)(q1,b,a)=(q1,b,a,R)后面符号与第一个不等，继续右移后面符号与第一个不等，继续右

23、移(q1,a,B)=(q1,B,B,L)(q1,b,B)=(q1,B,B,L)进入终态进入终态q1,B(q1,a,a)=(q1,b,b)=遇到相同符号，遇到相同符号，无定义无定义 M停机，不接受停机，不接受23School of Computer Science,BUPT5.2.2 多道多道（multiple tracks）图灵机）图灵机XYZTrack 1Track 2Track 3Finitecontrol把图灵机的输入带分成两层或多层，这样，原来的每一单把图灵机的输入带分成两层或多层，这样，原来的每一单元变成了上下两个或多个单元。元变成了上下两个或多个单元。对含有对含有n层的输入带来说，

24、读写头一次可同时读出并改写层的输入带来说，读写头一次可同时读出并改写n个单元的字符，这样的图灵机称为个单元的字符，这样的图灵机称为n道机。道机。24School of Computer Science,BUPT例：例：多道多道图灵机图灵机例：用三道机，检查某个数例：用三道机，检查某个数n（n2）是否为素数。）是否为素数。思路：将被检查的数思路：将被检查的数n以二进制形式写在输入带的第一道上，数的两端以二进制形式写在输入带的第一道上，数的两端分别用￥和分别用￥和定界定界允许的输入符号为允许的输入符号为￥,B,B,0,B,B,1,B,B,B,B分别代表分别代表1，2，3带上的内容。带上的内容。检查

25、方法：检查方法：在第二道上写下一个二进制数在第二道上写下一个二进制数2把第一道上的数复制到第三道上把第一道上的数复制到第三道上将第三道上的数减去第二道上的数，余数留在第三道上将第三道上的数减去第二道上的数，余数留在第三道上若余数为若余数为0，被检查的数不是素数，被检查的数不是素数若余数不为若余数不为0，将第二道数加，将第二道数加1，将第一道数复制到第三道，重复上述，将第一道数复制到第三道，重复上述1，2，3，4过程过程当一，二道数相等时，该数时素数。当一，二道数相等时，该数时素数。25School of Computer Science,BUPT 5.2.3 核对符核对符 当用图灵机识别语言时

26、，如果语言中存在有重复性或可当用图灵机识别语言时，如果语言中存在有重复性或可逆性等类型的句子时，为了判定某个字符串是否属于语句中逆性等类型的句子时，为了判定某个字符串是否属于语句中的句子，可以使用一个核对符，以此增加图灵机的灵活性。的句子，可以使用一个核对符，以此增加图灵机的灵活性。考虑用一个双道机，在第二道上使用核对符考虑用一个双道机，在第二道上使用核对符“”，在第，在第一道上放要被检查的字符串一道上放要被检查的字符串,当字符串中某个字符一旦被核当字符串中某个字符一旦被核对以后对以后,可以在第二道上对应位置写上核对符可以在第二道上对应位置写上核对符“”。26School of Compute

27、r Science,BUPT例：例：核对符核对符例：设计一个图灵机例：设计一个图灵机M M，能够识别语言，能够识别语言wtwwa,bwtwwa,b*思路：以思路：以t t为分界符，一个一个比较。为分界符，一个一个比较。解：构造解：构造M=(Q,T,qM=(Q,T,q0 0，B,F)B,F)其中其中Q=qQ=qi i,c i=1,2,c i=1,2,9,c=a,b,9,c=a,b或或BB状态第二元素可存储一个字符。状态第二元素可存储一个字符。T=cT=c，B c=a,bB c=a,b或或t t 两道与一道不同的表示法两道与一道不同的表示法cc，Y c=a,b,tY c=a,b,t或或B,Y=BB

28、,Y=B或或 q q0 0=q=q1 1,B,F=q,B,F=q9 9,B,B空白符空白符B B在二道机下表示为在二道机下表示为BB，BB27School of Computer Science,BUPT例：例：核对符核对符 eB/eB ev/ev cv/cv cB/cv tB/tB cB/cv q1,B q2,c q3,c q4,B cv/cv tB/tB cB/cB q6,B q5,B cv/cv cv cB tB BB/Bv q7,B q8,B q9,B R R R L L L R R L 28School of Computer Science,BUPT核对符例核对符例：abtab的分

29、析过程的分析过程q1,Babtabaq2,abtababq2,atababtq3,aab abq4,Btabaq5,Bbtabq6,Babtab aq1,Bbtababq2,btababtq3,bab abtaq3,bbabtq4,Babaq5,Bbtab abq7,Btababtq8,Bababtaq8,Bb 29School of Computer Science,BUPT 5.2.4 移位移位 可以让图灵机具备移位的功能，即对输入带上的可以让图灵机具备移位的功能，即对输入带上的字符进行移位操作。当需要在输入带上留出一部分空字符进行移位操作。当需要在输入带上留出一部分空间时，可将输入带上的

30、非空白符右移若干单元。间时，可将输入带上的非空白符右移若干单元。假设需要输入带上的非空白字符右移假设需要输入带上的非空白字符右移n n个单元，个单元，则可让控制器状态的第二个元素具有存储则可让控制器状态的第二个元素具有存储n n单元的功单元的功能（能（n n是有限数）是有限数）30School of Computer Science,BUPT例：例：构造图灵机构造图灵机M，要求它将带上非空白符向右移动两个单元，要求它将带上非空白符向右移动两个单元原带为原带为 a b c d B，移后为移后为 z z a b c d B设设M=(Q,T,q0,B,F)；Q=q,D1,D2 q=q0,q1,且且D

31、1,D2,Dn初始：初始：q0,B,B,终态终态q1,B,B定义：定义：(q0,B,B,D1)=(q0,B,D1,Z,R)(q0,B,D1,D2)=(q0,D1,D2,Z,R)(q0,D1,D2,D3)=(q0,D2,D3,D1,R)(q0,Dn-1,Dn,B)=(q0,Dn,B,Dn-1,R)(q0,Dn,B,B)=(q1,B,B,Dn,L)对对D B,Z:(q1,B,B,D)=(q1,B,B,D,L)回到输入点回到输入点31School of Computer Science,BUPT 5.2.5 子程序子程序（subroutines）的设计）的设计 左上图的左上图的图灵机表示子程序图灵机

32、表示子程序 copy，右上图的，右上图的图灵机表图灵机表示可以调用示可以调用copy 的主程序的主程序，完成两个正整数的乘法，完成两个正整数的乘法.初初始始时，带上的符号串形如时，带上的符号串形如 0m10n1，而结束时，带上的符号串，而结束时，带上的符号串变为变为0mn.q1q61/1q120/01/10/BB/BCopyq8q7q11q100/B1/B0/0q5Startq0q9B/B0/01/B0/032School of Computer Science,BUPT对基本图灵机的扩展 多带图灵机（多带图灵机（Multitape Turing Machines）双向无限带图灵机双向无限带图

33、灵机5.3 修改型图灵机 基本图灵机是计算的一种通用模型，对它进行某些修改，会得出更复杂的图灵机。从可计算性角度来讲，能够证明这些图灵机和基本图灵机是等价的。33School of Computer Science,BUPT具有双向无限带的图灵机具有双向无限带的图灵机FinitecontrolBX1BBB.X2XnXi带头（带头（tape head）带（带（tape）单元格（单元格（cell）空白（空白（blank）带符）带符带符（带符（tape symbol）34School of Computer Science,BUPT双向无穷带的图灵机与基本图灵机的等价双向无穷带的图灵机与基本图灵机的

34、等价 可以用一个双道的单向无穷带图灵机可以用一个双道的单向无穷带图灵机M1模拟具有双向模拟具有双向无穷带的基本图灵机无穷带的基本图灵机M.当M的读写头从初始位置右移时，M1用上道模拟M当M的读写头从初始位置左移时，M1用下道模拟MM1的初始单元：X0,￥,￥表示输入带最左单元。M1的形式构造：Q1=q,U,q,DqQq11=I,J,I,￥I,J,￥T1=Xi,B Xi TF1=q,U,q,D qFX1X-1X2X-2.X0*Finitecontrol￥35School of Computer Science,BUPT多带图灵机多带图灵机 多带图灵机由一个有限控制器，多带图灵机由一个有限控制器，

35、n个读写头和个读写头和n条双向无条双向无限带组成。限带组成。一次动作：一次动作：n控制器状态转变控制器状态转变n每个读写头在扫到的单元重写一个字符每个读写头在扫到的单元重写一个字符n各读写头各自向左各读写头各自向左/右移动一个单元（含不移动的情况）右移动一个单元（含不移动的情况）x.转移函数：转移函数：Qk QkL,R,Sk k是带的个数是带的个数形如形如(qi,a1,a2,ak)=(qj,b1,b2,bk,L,R,，L)36School of Computer Science,BUPT多带图灵机多带图灵机定理：每个多带图灵机都有一个与之等价的单带图灵机定理：每个多带图灵机都有一个与之等价的单

36、带图灵机.0 1 0 1 0 B a a a B M b a B S#0 1 0 1 0#a a a.#b a.#B n假设M有k条带，nS将k条带的信息都存在它的一条带上，用新的符号#作为定界符，以分开不同带的内容。n此外，S还要记录读写头的位置，这里用符号加“点”来标记，S把它想象为虚拟读写头。（也可用双道+识别符）37School of Computer Science,BUPT非确定图灵机非确定图灵机 下一个移动步有多种选择下一个移动步有多种选择 转移函数可以转移函数可以为为 :Q 2Q D，其中，其中 Q、和和 D 分分 别为有限状态集、带符号集和带头的移动方向别为有限状态集、带符号

37、集和带头的移动方向.即即 (q,X)为三元组的集合：为三元组的集合：(q1,Y1,D1),(q2,Y2,D2),(qk,Yk,Dk)非确定图灵机语言接受能力与（确定的）基本图灵机等非确定图灵机语言接受能力与（确定的）基本图灵机等价（证明略）价（证明略）38School of Computer Science,BUPT图灵机与计算机 以普通计算机模拟图灵机以普通计算机模拟图灵机 以多带图灵机模拟普通计算机以多带图灵机模拟普通计算机39School of Computer Science,BUPT以普通计算机模拟图灵机以普通计算机模拟图灵机 采用适当的数据结构（如转移表）不难编制普通的计采用适当的

38、数据结构（如转移表）不难编制普通的计 算机程序实现图灵机的有限状态控制机制算机程序实现图灵机的有限状态控制机制.存在问题的存在问题的 是如何模拟无限延伸的带，因为普通计算机的存储空是如何模拟无限延伸的带，因为普通计算机的存储空 间（包括各个级别的存储器）是有限的间（包括各个级别的存储器）是有限的.但是，可以假但是，可以假 想一种可以无限扩充存储量的存储系统想一种可以无限扩充存储量的存储系统.实际上，可装实际上，可装 卸的卸的 外存系统并不严格规定存储量的上限，而且并非外存系统并不严格规定存储量的上限，而且并非 所有信息都需要在线存储所有信息都需要在线存储.ProcessorTape tolef

39、t ofthe headTape toright ofthe head40School of Computer Science,BUPT以多带图灵机模拟普通计算机以多带图灵机模拟普通计算机 可以用多带图灵机模拟典型的存储程序式计算机，参可以用多带图灵机模拟典型的存储程序式计算机，参 见以下示意图见以下示意图.必要时，可增加更多的带必要时，可增加更多的带.FinitecontrolMemoryInstructioncounter$0*w0#1*w1#10*w2#11*w3#100*w4 .100111101110MemoryaddressComputersInput fileScratch41S

40、chool of Computer Science,BUPT图灵机的本质特征图灵机的本质特征 图灵机的本质特征：图灵机的本质特征：可以无限制的访问无限的存储器。可以无限制的访问无限的存储器。这一特征将它和有限自动机，下推自动机等某些较弱这一特征将它和有限自动机，下推自动机等某些较弱的模型区别开来。的模型区别开来。已经证明：所有有此特点的模型在能力上都是等价的已经证明：所有有此特点的模型在能力上都是等价的，只要它们满足一些合理的必要条件即可（如，只要它们满足一些合理的必要条件即可（如“在一步中只在一步中只能执行有限的工作量能执行有限的工作量”）语言中的例子：语言中的例子：LISPPASCAL 描述了相同语法类。描述了相同语法类。