单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 图灵机,A.Turing,在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质,该模型的每个过程都是有穷可描述的；,过程必须是由离散的、可以机械执行的步骤组成图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力通过研究,TM,来研究递归可枚举集和部分递归函数,为算法和可计算性研究提供了形式化描述工具1,School of Computer Science&Technology,BUPT,主要内容,TM,的基本定义,TM,的格局,TM,接受的语言,TM,的构造技术,TM,的变形；,重点:,TM,的定义、,TM,的构造难点:,TM,的构造2,School of Computer Science&Technology,BUPT,Finite,control,X,1,B,B,.,X,2,X,n,X,i,带（,tape,）,单元格（,cell,）,带符（,tape symbol,）,读写头在每一时刻扫描带上的一个单元,带有一个最左单元，向右则是无限的带的每个单元可容纳一个带符号,开始时，最左边,n,个单元装着输入（,n,0,，,n,为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输入符号集合”。
余下的有穷个单元都存放空白符，它是一个特殊的带符号，但,不是,输入符号图灵机的基本模型,3,School of Computer Science&Technology,BUPT,在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作,改变状态,在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.,将带头向左或者右移一个单元图灵机和双向有限自动机的区别：图灵机能改变它带上的符号图灵机的工作机制,4,School of Computer Science&Technology,BUPT,图灵机的形式化描述,有限状态集,有限输入符号集,有限带符号集,转移函数,开始状态,特殊带符:空白符,终态集合,q,0,Q,T,B,T,F,Q,转移函数,:,Q,Q,L,R,形式定义,一个图灵机,TM(Turing machine,),是一个七元组,M,=(,Q,T,q,0,B,F,),.,5,School of Computer Science&Technology,BUPT,函数示例：,Q QL,R,(q,a,i,)=(p,B,L)q,p Q,(q,a,i,)=(p,b,R)a,i,b,格局,用,w,1,q w,2,描述图灵机的瞬间工作状态,q,为,M,的当前状态，,w,1,w,2,*,w,1,w,2,是当前时刻从开始端（因为可写）到右边空白符号为止的内容,当读写头已达到带的右端，则,w,1,w,2,为读写头以左的内容。
约定：,w,1,q w,2,表示读写头正扫描,w,2,的最左字符,w,2,则表示读写头正扫描一个空白字符图灵机的函数与格局,6,School of Computer Science&Technology,BUPT,图灵机的格局,给定图灵机,M,=(,Q,T,q,0,B,F,)，,定义格局之间的推导关系,M,如下：,1.,设,(,q,X,i,),=,(p,Y,L),，,则有,X,1,X,2,X,i,-1,qX,i,X,i,+1,X,n,M,X,1,X,2,X,i,-2,pX,i,-1,Y,X,n,，,但有如下两个例外,：,（,1,）,i,=1,时，,qX,1,X,2,X,n,M,qYX,2,X,n,，,和,（,2,）,i,=n,及,Y,=,B,时，,X,1,X,2,X,n-1,qX,n,M,X,1,X,2,X,n-2,pX,n-1,B,.,2.,设,(,q,X,i,),=,(p,Y,R),，,则有,X,1,X,2,X,i,-1,q X,i,X,i,+1,X,n,M,X,1,X,2,X,i,-1,Y p X,i,+1,X,n,，,但有如下两个例外,：,（,1,）,i,=n,时，,X,1,X,2,X,n-1,q,X,n,M,X,1,X,2,X,n-1,Y p B,，,和,（,2,）,i,=1,及,Y,=,B,时，,q X,1,X,2,X,n,M,B,p X,2,X,n-1,X,n,.,7,School of Computer Science&Technology,BUPT,图灵机接受的语言,L(M)=,T,*,且,q,0,*,1,p,2,pF,1,2,*,图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在,M,的带上，,M,处于状态,q,0,，,且,M,的带头处在最左单元上，这些字符串将使,M,进入某个终止状态。
假定：,当输入被接受时，图灵机将停止，没有下一个动作8,School of Computer Science&Technology,BUPT,任给图灵机,M,=(,Q,T,q,0,B,F,)，,以及输入字符串,w,T*,.,试问：对于,w,，,M,是否停机,？,停机是指图灵机不存在下一个移动步（,move,）,.,结论,图灵机的停机问题是不可解的（即不可判定的）.,结论,任给图灵机,M,，,很容易构造一个图灵机,M,，,使得,L(M)=L(M,),，,并满足：如果,w,L(M),，,则对于,w,，,M,接受,w,并一定停机.,如果没有特别指出，总是假定图灵机到达终态（接受态）后一定停机.,但是,，,对不能接受的字符串，图灵机可能永不停止.（只要,M,还在某个输入上运行，我们无法知道是因为运行的时间不够长而没有被接受，还是根本就不会停机）,图灵机的停机问题,9,School of Computer Science&Technology,BUPT,图灵机举例,例1：设语言,L=a,n,b,n,n=1，,设计图灵机接受,L思路：最初带上为,a a,a b b b B B B,n,个,a n,个,b,首先用,x,替换,M,最左边的,a，,再右移至最左边的,b,用,y,替换之，左移寻找最右的,x，,然后右移一单元到最左的,a，,重复循环。
如果,（1）当在搜寻,b,时，,M,找到了空白符,B，,则,M,停止，不接受该串此时，,a,的个数大于,b,的个数）,（2）当将,b,改为,y,后，左边再也找不到,a，,此时,若右边再无,b，,接受；若仍有,b，,则,b,的个数大于,a,的个数，不接受10,School of Computer Science&Technology,BUPT,例,1,L=a,n,b,n,n=1,(q,0,a)=(q,1,x,R),(q,0,y)=(q,3,y,R),(q,1,a)=(q,1,a,R),(q,1,y)=(q,1,y,R),(q,1,b)=(q,2,y,L),(q,2,a)=(q,2,a,L),(q,2,y)=(q,2,y,L),(q,2,x)=(q,0,x,R),(q,3,y)=(q,3,y,R),(q,3,B)=(q,4,B,R),例：,aabb,的接收格局序列,q,0,aabb xq,1,abb xaq,1,bb xq,2,ayb q,2,xaybxq,0,aybxxq,1,yb,xxyq,1,bxxq,2,yyxq,2,xyyxxq,0,yyxxyq,3,yxxyyq,3,Bxxyyq,4,11,School of Computer Science&Technology,BUPT,对于输入字符串,001122,，该图灵机可以有如下推导步：,q,0,001122,M,Xq,1,01122,M,X0q,1,1122,M,X0Yq,2,122,M,X0Y1q,2,22,M,X0Yq,3,1Z2,*,M,q,3,X0Y1Z2,M,Xq,0,0Y1Z2,*,M,XXYYZq,2,2,M,XXYYq,3,ZZ,*,M,Xq,3,XYYZZ,M,XXq,0,YYZZ,*,M,XXYYq,4,ZZ,M,XXYYZq,5,Z,M,XXYYZZq,5,B,M,XXYYZZBq,6,B,例,2,L,=,0,n,1,n,2,n,n,1,.,12,School of Computer Science&Technology,BUPT,转移图与转移表,13,School of Computer Science&Technology,BUPT,作为整数函数计算机的图灵机,预备知识：,图灵机除了作为语言接受器外，还可看作整数到整数的函数计算机。
传统方法把整数表示成一进制,整数,i,0,用字符串 0,i,表示,如果一个函数有,k,个自变量，,i,1,i,2,i,k,，,那么这些整数开始时被放在带上，并用1把他们分隔开形如 0,i1,1 0,i2,1 0,i3,1 0,ik,如果图灵机停止(不论是否在一个接受状态上)且带上为,0,m,，,则,f(i,1,i,2,i,k,)=m f,是被图灵机计算的,k,元函数,如果,f,（i,1,i,2,i,k,）,对所有,i,1,i,2,i,k,有定义,那么称,f,是一个全递归函数全递归函数对应于递归语言，因为它总是被能停下来的图灵机所计算所有常用的整数算术函数都是全递归函数14,School of Computer Science&Technology,BUPT,例,3,：设计图灵机求真减法,思路：,1.用空白符,B,代替带上的最左端的0,2右移至紧跟1后的0,将其改为1,3左移找到,B，,将,B,之后的0改为,B,4,重复上述过程,如果,（1）右移找0时，遇到,B，,意味着,mn,BBB 0,m-(n+1),1 111,n+1 n,个,将后面,n+1,个1变为,B，,将左侧最后一个,B,变0，形如,BBB 0 0,m-(n+1),BBB,n,个,n+1,个,这时，带上留下,m-n,个0，即结果为,m-n,初始带,0,m,1,0,n,15,School of Computer Science&Technology,BUPT,求真减法（续）,(2),M,左移找不到0，意味着,n,m，,形如,BBB 1 111 00,m,个,m,个,n-m,个,此时,用,B,替换所有剩余的1 和0,16,School of Computer Science&Technology,BUPT,例,4,：,L=0,m,m=2,n,n 0,设计思路：对输入串,w,1.从左到右扫描带，隔一个消一个0；,2若带上只剩唯一一个0,接受；,3若带上不止一个0,且个数为奇数，拒绝；,4,让读写头返回带的最左端；,5.,转第一步。
17,School of Computer Science&Technology,BUPT,Start,q,4,q,2,q,1,0/#,R,q,reject,X/X,R,B/B,R,q,3,B/B,R,accept,q,q,5,#/#,R,B/B,L,X/X,L,0/0,L,0/X,R,X/X,R,X/X,R,0/X,R,0/0,R,识别,L=0,m,m=2,n,n 0,的,图灵机,18,School of Computer Science&Technology,BUPT,课堂练习,设计一个状态数不超过,3,的图灵机，它能够接受语言,L=a(a+b),*,，若假定,T=a,b,两个状态的图灵机能否接受该语言？,19,School of Computer Science&Technology,BUPT,5.2,图灵机的构造技术,在设计图灵机的过程中，写出,函数很麻烦，为了构造复杂的图灵机，需探讨图灵机的若干构造技术，并引入一些新的概念和工具目的：设计时方便，但这些构造技术并未增加图灵机的功能20,School of Computer Science&Technology,BUPT,5.2.1.,利用带存储区的状态,（,storage in the state,）,此类,图灵机,M,=(,Q,q,0,B,F,),中，状态。