基本图灵机及图灵机构造技术

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第五章 图灵机,A.Turing,在1936年介绍了这样一个通用的计算模型，该模型具有以下两个性质,该模型的每个过程都是有穷可描述的；,过程必须是由离散的、可以机械执行的步骤组成。,图灵机是计算机的一种简单数字模型，尽管简单，但它具有模拟通用计算机的计算能力。,TM,来研究递归可枚举集和部分递归函数,为算法和可计算性研究提供了形式化描述工具。,1,主要内容,TM,的基本定义,TM,的格局,TM,接受的语言,TM,的构造技术,TM,的变形；,重点:,TM,的定义、,TM,的构造。,难点:,TM,的构造。,2,Finite,control,X,1,B,B,.,X,2,X,n,X,i,带（,tape,）,单元格（,cell,）,带符（,tape symbol,）,读写头在每一时刻扫描带上的一个单元,带有一个最左单元，向右则是无限的。,带的每个单元可容纳一个带符号,开始时，最左边,n,个单元装着输入（,n,0,，,n,为有限数），它是一个字符串，符号都选自“带符号”的一个子集，即所谓的“输入符号集合”。余下的有穷个单元都存放空白符，它是一个特殊的带符号，但,不是,输入符号。,图灵机的基本模型,3,在一个图灵机的动作中，图灵机根据带头（读写头）所扫描的符号和有限控制器的状态可能作,改变状态,在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号.,将带头向左或者右移一个单元。,* 图灵机和双向有限自动机的区别：图灵机能改变它带上的符号。,图灵机的工作机制,4,图灵机的形式化描述,有限状态集,有限输入符号集,有限带符号集,转移函数,开始状态,特殊带符:空白符,终态集合,q,0,Q,T ,B, T,F,Q,转移函数, :,Q,Q,L,R,形式定义,一个图灵机,TM (Turing machine,),是一个七元组,M,= (,Q,T, q,0, B, F,),.,5,函数示例：,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,图灵机的格局,给定图灵机,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,图灵机接受的语言,L(M) = ,T,*,且,q,0,*,1,p ,2,pF, ,1,2,*,图灵机接受的语言是输入字母表中这样一些字符串的集合，初始时，这些字符串放在,M,的带上，,M,处于状态,q,0,，,且,M,的带头处在最左单元上，这些字符串将使,M,进入某个终止状态。,假定：,当输入被接受时，图灵机将停止，没有下一个动作。,8,任给图灵机,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,图灵机举例,例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,例,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,对于输入字符串,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,转移图与转移表,13,作为整数函数计算机的图灵机,预备知识：,图灵机除了作为语言接受器外，还可看作整数到整数的函数计算机。,传统方法把整数表示成一进制,整数,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,例,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,求真减法（续）,(2),M,左移找不到0，意味着,n,m，,形如,BBB 1 111 00,m,个,m,个,n-m,个,此时, 用,B,替换所有剩余的1 和0,16,例,4,：,L= 0,m, m=2,n, n 0,设计思路：对输入串,w,1. 从左到右扫描带，隔一个消一个0；,2若带上只剩唯一一个0,接受；,3若带上不止一个0,且个数为奇数，拒绝；,4,让读写头返回带的最左端；,5.,转第一步。,17,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,课堂练习,设计一个状态数不超过,3,的图灵机，它能够接受语言,L=a(a+b),*,，若假定,T=a,b,两个状态的图灵机能否接受该语言？,19,5.2,图灵机的构造技术,在设计图灵机的过程中，写出,函数很麻烦，为了构造复杂的图灵机，需探讨图灵机的若干构造技术，并引入一些新的概念和工具。,目的：设计时方便，但这些构造技术并未增加图灵机的功能。,20,5.2.1.,利用带存储区的状态,（,storage in the state,）,此类,图灵机,M,= (,Q, q,0, B, F,),中，状态中可以包含,一个具有有限个取值的存储单元，即状态集合为,Q = S,T = q,a,| q,S,a,T,，,其中,q,S,通常表示控制状态，而,a,T,通常表示数据元素,.,一般情况下，有限控制器内允许存储,n,个字符，即状态的第,2,个元素可存储,n,个字符。,21,例：设计一个图灵机，读写头将扫视第一个字符存入有限控制器内，然后扫视整个带，若找不到与第一个相同的字符，则,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),后面符号与第一个不等，继续右移,(q1,a,B)=( q1,B,B,L),(q1,b,B)=( q1,B,B,L),进入终态,q1,B,(q1,a,a)=,(q1,b,b)=,遇到相同符号，,无定义,M,停机，不接受,22,5.2.2,多道,（,multiple tracks,）图灵机,把图灵机的输入带分成两层或多层，这样，原来的每一单元变成了上下两个或多个单元。,对含有,n,层的输入带来说，读写头一次可同时读出并改写,n,个单元的字符，这样的图灵机称为,n,道机。,23,例： 多道,图灵机,例：用三道机，检查某个数,n,（,n2,）是否为素数。（书,p196,）,思路：将被检查的数,n,以二进制形式写在输入带的第一道上，数的两端分别用￥和,定界,允许的输入符号为,￥,B,B,0,B,B,1,B,B,B,B,分别代表,1,，,2,，,3,带上的内容。,检查方法：,在第二道上写下一个二进制数,2,把第一道上的数复制到第三道上,将第三道上的数减去第二道上的数，余数留在第三道上,若余数为,0,，被检查的数不是素数,若余数不为,0,，将第二道数加,1,，将第一道数复制到第三道，重复上述,1,，,2,，,3,，,4,过程,当一，二道数相等时，该数时素数。,24,5.2.3,核对符,当用图灵机识别语言时，如果语言中存在有重复性或可逆性等类型的句子时，为了判定某个字符串是否属于语句中的句子，可以使用一个核对符，以此增加图灵机的灵活性。,考虑用一个双道机，在第二道上使用核对符“,”，在第一道上放要被检查的字符串,当字符串中某个字符一旦被核对以后,可以在第二道上对应位置写上核对符“,”。,25,例：,核对符,例：设计一个图灵机,M,，能够识别语言,wtwwa,b*,思路：以,t,为分界符，一个一个比较。,解：构造,M=(Q,T, , ,q,0,，,B,F),其中,Q=q,i,c i=1,2,9,c=a,b,或,B,状态第二元素可存储一个字符。,T=c,，,B c=a,b,或,t,两道与一道不同的表示法,c,，,Y c=a,b,t,或,B,Y=B,或,q,0,=q,1,B, F=q,9,B,空白符,B,在二道机下表示为,B,，,B,26,例：,核对符,27,核对符例 ：,abtab,的分析过程,q1,Babtabaq2,abtababq2,atababtq3,aab, abq4,Btabaq5,Bbtabq6,Babtab,aq1,Bbtababq2,btababtq3,bab,abtaq3,bbabtq4,Babaq5,Bbtab,abq7,Btababtq8,Bababtaq8,Bb,28,5.2.4,移位,可以让图灵机具备移位的功能，即对输入带上的字符进行移位操作。当需要在输入带上留出一部分空间时，可将输入带上的非空白符右移若干单元。,假设需要输入带上的非空白字符右移,n,个单元，则可让控制器状态的第二个元素具有存储,n,单元的功能（,n,是有限数）,29,例：,构造图灵机,M,，要求它将带上非空白符向移动两个单元,原带为,a b c d B,， 移后为,z z a b c d B,设,M=(Q, T, , , q,0, B, F),；,Q=q, D,1, D,2, q=q,0,q,1,且,D,1,D,2,D,n,初始：,q,0, B, B,终态,q,1, B, B,定义：,(q,0, B, B, D,1,)=(q,0, B, D,1, Z, R),(q,0, B, D,1, D,2,)=(q,0, D,1, D,2, Z, R),(q,0, D,1, D,2, D3)=(q,0, D,2, D,3, D,1, R),(q,0, D,n-1, D,n, B)=(q,0, D,n, B, D,n-1, R),(q,0, D,n, B, B)=(q,1, B, B, Dn, L),对,D, B, Z:,(q,1, B, B,D)=(q,1, B, B, D, L),回到输入点,30,5.2.5,子程序,（,subroutines,）的设计,左上图的,图灵机表示子程序,copy,，右上图的,图灵机表示可以调用,copy,的主程序 ，完成两个正整数的乘法,.,初始,时，带上的符号串形如,0,m,10,n,1,，而结束时，带上的符号串,变为,0,mn,.,31,