计算模型图灵机.ppt

第5周、第6周内容介绍,理论计算机科学基础,1,理论计算机科学基础,2,第2部分可计算性理论,第5周图灵机第4章丘奇-图灵论题第7章可计算性理论的高级专题(递归定理)第6周(不)可计算问题第5章可判定性第6章可归约性,理论计算机科学基础,3,第4章丘奇-图灵论题,图灵机(TM)多带图灵机非确定型图灵机(NTM)枚举器图灵可识别,图灵可判定丘奇-图灵论题算法、希尔伯特第10问题图灵机的描述形式描述;实现描述;高层描述编码:,理论计算机科学基础第9讲,4,第7章可计算性高级专题,递归定理自引用应用递归定理的术语可以在M的定义中使用应用图灵机接受性问题图灵机极小性问题通用机,理论计算机科学基础第7讲,5,第5章可判定性,可判定语言关于正则语言的可判定问题关于上下文无关语言的可判定问题停机问题对角化方法停机问题是不可判定的非图灵可识别语言,理论计算机科学基础第8讲,6,第6章可归约性,语言理论中的不可判定问题利用计算历史的归约线性界限自动机波斯特对应问题映射归约(多一归约,m归约),单带图灵机的例子,理论计算机科学基础,7,理论计算机科学基础,8,单带图灵机的示意图,双向读写头无穷带停机状态,理论计算机科学基础,9,识别w#w的单带图灵机M1,B=w#w|w0,1*M1=“对于输入字符串x:1)扫描输入,确认只含一个#.否则拒绝.2)在#两边对应位置来回移动,检查是否含相同符号.若不是,则拒绝.消去已检查过符号.3)当消去#左边所有符号时,检查#右边是否还有符号,若是,则拒绝.否则接受.”,理论计算机科学基础,10,M1对011000#011000计算,011000#011000,理论计算机科学基础,11,M1对011000#011000计算,X11000#0110000,理论计算机科学基础,12,M1对011000#011000计算,X11000#0110000,理论计算机科学基础,13,M1对011000#011000计算,X11000#0110000,#,理论计算机科学基础,14,M1对011000#011000计算,X11000#X11000,理论计算机科学基础,15,M1对011000#011000计算,X11000#X11000,#,理论计算机科学基础,16,M1对011000#011000计算,X11000#X11000,#,理论计算机科学基础,17,M1对011000#011000计算,X11000#X11000,理论计算机科学基础,18,M1对011000#011000计算,XX1000#X110001,理论计算机科学基础,19,M1对011000#011000计算,XX1000#X110001,理论计算机科学基础,20,M1对011000#011000计算,XX1000#X110001,理论计算机科学基础,21,M1对011000#011000计算,XX1000#X110001,#,理论计算机科学基础,22,M1对011000#011000计算,XX1000#X110001,#,理论计算机科学基础,23,M1对011000#011000计算,XX1000#XX1000,理论计算机科学基础,24,M1对011000#011000计算,XX1000#XX1000,#,理论计算机科学基础,25,M1对011000#011000计算,XX1000#XX1000,#,理论计算机科学基础,26,M1对011000#011000计算,XX1000#XX1000,理论计算机科学基础,27,M1对011000#011000计算,XXX000#XX10001,理论计算机科学基础,28,M1对011000#011000计算,XXX000#XX10001,#,理论计算机科学基础,29,M1对011000#011000计算,XXX000#XX10001,#,理论计算机科学基础,30,M1对011000#011000计算,XXX000#XXX000,理论计算机科学基础,31,M1对011000#011000计算,XXXXX0#XXXXX0,理论计算机科学基础,32,M1对011000#011000计算,XXXXXX#XXXXX00,理论计算机科学基础,33,M1对011000#011000计算,XXXXXX#XXXXX00,#,理论计算机科学基础,34,M1对011000#011000计算,XXXXXX#XXXXXX,理论计算机科学基础,35,M1对011000#011000计算,XXXXXX#XXXXXX,#,理论计算机科学基础,36,M1对011000#011000计算,XXXXXX#XXXXXX,理论计算机科学基础,37,M1对011000#011000计算,XXXXXX#XXXXXXB,理论计算机科学基础,38,M1对011000#011000计算,XXXXXX#XXXXXXB,理论计算机科学基础,39,M1对011000#011000计算,XXXXXX#XXXXXXaccept,单带图灵机的定义,理论计算机科学基础,40,理论计算机科学基础,41,单带图灵机的定义,定义4.1:TMM=(Q,q0,qacc,qrej)1)Q是有穷状态集2)是输入字母表,空格符B3)是带字母表,B,4):QQL,R是转移函数5)q0Q是初始状态6)qaccQ是停机接受状态7)qrejQ是停机拒绝状态,qaccqrej,理论计算机科学基础,42,单带图灵机的格局,格局:uqav,当前状态:q,当前带内容:uav,当前扫描符号:a初始格局:q0w,w是输入串接受格局:uqaccav,拒绝格局:uqrejav,停机格局:uqaccav,uqrejav,理论计算机科学基础,43,单带图灵机格局的例子,1011q701111,理论计算机科学基础,44,单带图灵机格局的产生,C1产生C2:如果(qi,b)=(qj,c,L),则uaqibv产生uqjacvqibv产生qjcv(在带左端不能向左移)如果(qi,b)=(qj,c,R),则uaqibv产生uacqjv,理论计算机科学基础,45,单带图灵机M接受输入w,M接受输入w:存在格局序列C1,C2,Ck,使得1)C1=q0w是初始格局2)每个Ci产生Ci+1(i=1,k-1)3)Ck是接受格局M(识别,接受)的语言:L(M)=x|M接受x,理论计算机科学基础,46,图灵机的计算结果,停机接受停机拒绝不停机,理论计算机科学基础,47,图灵可识别,图灵可判定,图灵可识别:A=L(M).xA时,M在x上停机接受xA时,M在x上停机拒绝或不停机图灵可判定:A=L(M)xA时,M在x上停机接受xA时,M在x上停机拒绝(处处停机),理论计算机科学基础,48,一些等价术语,图灵可识别=递归可枚举=计算可枚举=半可判定图灵可判定=递归=可判定=可解=能行下一章证明:图灵可识别图灵可判定,图灵机判定语言的例子,理论计算机科学基础,49,理论计算机科学基础,50,例4.4,M2=“对输入串w：1)从左向右扫描带子,隔一个消去一个0.2)若第一步之后,带子上只剩下1个0,则接受.3)若第一步之后,带子上剩下1个以上奇数个0,则拒绝.4)让读写头返回到带子最左端.5)转到第一步.”,理论计算机科学基础,51,例4.4,M2=(Q,q1,qacc,qrej)Q=q1,q2,q3,q4,q5,qacc,qrej,=0=0,X,B如下页图示用空白符B作为左端点定界符,理论计算机科学基础,52,例4.4M2的状态转移图,理论计算机科学基础,53,例4.4M2在0000上的计算,q10000,Bq2000,BXq300,BX0q40,BX0Xq3B,BX0q5XB,BXq50XB,Bq5X0XB,q5BX0XB,Bq2X0XB,BXq20XB,BXXq3XB,BXXXq3B,BXXq5XB,BXq5XXB,Bq5XXXB,q5BXXXB,Bq2XXXB,BXq2XXB,BXXq2XB,BXXXq2B,BXXXBqacc,理论计算机科学基础,54,例4.5B=w#w|w0,1*,M1=“对于输入字符串w:1)扫描输入,确认只含一个#.否则拒绝.2)在#两边对应位置来回移动,检查是否含相同符号.若不是,则拒绝.消去已检查过符号.3)当消去#左边所有符号时,检查#右边是否还有符号,若是,则拒绝.否则接受.”,理论计算机科学基础,55,例4.5,M1=(Q,q1,qacc,qrej)Q=q1,q2,q8,qacc,qrej,=0,1,#=0,1,#,X,B如下页图示省略到拒绝状态的转移,理论计算机科学基础,56,例4.5M1的状态转移图,q1,q2,q3,0,1R,1x,R,0x,R,0,1R,q4,xR,q5,xR,#R,#R,q7,0,1L,q6,0,1,xL,qaccept,q8,BR,xR,0x,R,#R,xR,#L,1x,R,理论计算机科学基础,57,例4.6C=aibjck|ij=k,M3=“对输入串w:1)从左向右扫描输入,确认输入具有形式a*b*c*,否则拒绝.2)让读写头回到带子左端.3)消去1个a,向右扫描直到b出现.在b和c之间来回移动,成对消去b和c,直到消去所有b.4)若还有a未消去,则恢复所有已消去的b,重复第三步.若所有a已消去,则检查是否消去所有c,若是则接受,否则拒绝.”,理论计算机科学基础,58,例4.6发现带左端的技巧,如何发现带左端当前位置上写下某个特殊符号,在控制中记住所取代的符号,让带头向左移动若带头还在特殊符号上,则已经到带子左端否则,恢复右边的符号,再向左移,理论计算机科学基础,59,例4.7E=#x1#x2#xk|xi0,1*,ij,xixj,M4=“对输入w:1)在最左端带符号顶上做记号.若此符号是空白符,则接受,若此符号是#,则进行下一步.否则拒绝.2)向右扫描下一个#,在其顶上做第二个记号.若在遇到空白符之前没有遇到#,则只有x1,因此接受.3)来回移动比较做记号#右边两个串,若相等,则拒绝.4)将右边#上记号向右移到下一个#上.若在遇到空白符之前没有遇到#,则将左边#上记号向右移到下一个#上,并将右边记号移到后面#上.若此时右边仍然找不到#,则接受.5)转到第三步.”,理论计算机科学基础,60,例4.7(元素区分问题),把每个xi与它右侧的所有xj相比在#上做记号,带字母表包含#,#上述语言都是可判定的(处处停机),图灵机的各种等价变形,理论计算机科学基础,61,理论计算机科学基础,62,图灵机的等价变形,双向无穷带多维带多带多头非确定型TM概念有很强的稳健性,多带图灵机,理论计算机科学基础,63,理论计算机科学基础,64,多带图灵机,多带图灵机的转移函数:QkQkL,Rk(qi,a1,ak)=(qj,b1,bk,L,R,L),理论计算机科学基础,65,定理4.8,定理4.8:每个多带TM都有等价单带TM.分析:“分道”:每道模拟一条带(改变字母表)“分段”:每段模拟一条带,理论计算机科学基础,66,定理4.8证明,证明:设计单带TMS来模拟多带TMM.S=“对于输入w=w1wn:1)S在自己带上放上#w1w2wn#B#B#.2)为了模拟一步移动,S从标记左端点的第一个#开始扫描,直到标记右端点的第k+1个#.确定虚拟读写头下的符号.然后S进行第二次扫描,根据M的转移函数来更新带子.3)任何时候,只要S将某个虚拟读写头向右移动到某个#上,S就在这个位置写下空白符,并把这个位置以右的所有内容向右平移一格.然后继续模拟.”(正确性证明)#,理论计算机科学基础,67,推论4.9,推论4.9:图灵可识别当且仅当可用多带图灵机识别,非确定型图灵机,理论计算机科学基础,68,理论计算机科学基础,69,非确定型图灵机,非确定型图灵机(NTM):QP(QL,R,S)计算树:非确定性分支,理论计算机科学基础,70,定理4.10,定理4.10:每个NTM都有等价DTM.分析:DTM“遍历”NTM计算树先深先宽,理论计算机科学基础,71,定理4.10证明图示,证明:用DTMD来模拟NTMN.,理论计算机科学基础,72,定理4.10证明,证明:用DTMD来模拟NTMN.D=“对输入w:1)开始时,第一个带包含w,其余两个带为空.2)把第一个带复制到第二个带上.3)在第二个带上模拟N在输入w上的某个非确定性计算分支.这个分支由第三个带指定.若遇到接受格局,则接受.否则进入第四步.4)在第三个带上,用字典序下的下一个串来替代原用的串.转到第二步.”,理论计算机科学基础,73,推论4.11-12,推论4.11:图灵可识别当且仅当可用非确定型图灵机识别推论4.12:图灵可判定当且仅当可用非确定型图灵机判定,枚举器与识别器,理论计算机科学基础,74,理论计算机科学基础,75,枚举器,计算装置的工作方式:识别器:输入x,输出0/1/?判定器:输入x,输出0/1转换器:输入x,输出y产生器:输入0n,输出xn枚举器:输入,输出x1,x2,x3,无遗漏,无多余(可重复),无顺序,理论计算机科学基础,76,定理4.13,定理4.13:图灵可识别等价于可枚举.分析:可识别可枚举:枚举*,逐个识别楔形过程:对s1,s2,sk运行k步.可识别可枚举:枚举,等待x出现,理论计算机科学基础,77,定理4.13证明,证明:()设枚举器E枚举语言A,则设计TMM识别A.M=“对输入w:1)运行E,每当E输出一个串时,将这个串与w进行比较.2)若w曾在E的输出中出现过,则接受.”,理论计算机科学基础,78,定理4.13证明,证明:().设TMM识别语言A,则设计枚举器E枚举A.设*=s1,s2,s3,.E=“忽略输入.1)对i=1,2,3,重复下列步骤.2)对s1,s2,s3,si中每一个,让M以其作为输入运行i步.3)如果有计算接受,则打印相应的sj.”,理论计算机科学基础,79,计算模型的等价性,计算模型图灵机(及其变种)-演算0型文法这些模型彼此等价可以互相模拟你的经验Pascal与LISP等价,算法的定义,理论计算机科学基础,80,理论计算机科学基础,81,算法(Algorithm),9世纪数学家al-Khowarizmi“fromthetownofKowarzimi”该地现在是Khiva,Uzbekistan他的著作复原和化简的规则Kitabal-jabrwalmuquabalaAlgebra一词也源自此书18世纪出现Algorithm一词原意阿拉伯数字十进制算术Algorism,理论计算机科学基础,82,希尔伯特第十问题,1900年,希尔伯特23个问题希尔伯特第10问题:有没有求多项式整数根的算法？“通过有限多次运算就可以决定的过程”6X3YZ2+3XY2-X3-10=0X2+Y2=Z2(勾股定理)Xn+Yn=Zn(n2)(费马定理),理论计算机科学基础,83,哥德尔,图灵,Godel不完备性定理:任何形式系统要么是不完备的,要么是不相容的“这句话没有证明”Church,Kleen:递归论Turing:图灵机通用机存在停机问题不可解(下一章)Davis,Putnam,Robinson,Matijasevic:第10问题否定回答,理论计算机科学基础,84,丘奇-图灵论题,算法处处停机图灵机=-演算=0型文法=算法是直觉概念图灵机,-演算,0型文法,是数学概念=是可以严格证明的定理可以作为定义,不能证明,理论计算机科学基础,85,算法的定义,丘奇-图灵论题(Church-TuringThesis)算法的直觉概念=图灵机算法,图灵机算法的描述,理论计算机科学基础,86,理论计算机科学基础,87,图灵机算法的描述方式,形式描述七元组实现描述用日常语言描述图灵机的运行(如何存放数据,如何移动读写头)不给出状态和转移函数的细节高层描述用日常语言描述算法不考虑对读写头和带的管理,理论计算机科学基础,88,描述图灵机输入的记号,图灵机的输入总是串其他输入对象必须表示成串多项式,图,文法,自动机,及其任意组合对象O的编码是多对象O1,O2,Ok的编码是可用多种合理方式来编码图灵机总能把一种编码翻译成另外一种编码,理论计算机科学基础,89,编码的细节,字符串x=010,y=11,=?1=001100101111|1|=2|x|+2|y|+22=11111001011|2|=|x|+|y|+2log|x|+2边界自明,自限界=111110010,=11001011|=|x|+2log|x|+23=11111001011001011|3|=|x|+|y|+2log|x|+2log|y|+4,理论计算机科学基础,90,描述图灵机算法的格式,带引号的锯齿状日常语言文字段将算法分成步骤,每个步骤可能包括图灵机计算的许多步用更深的缩进来表示算法的分块结构第一行描述机器的输入如果输入是对象的编码,就隐含着如下含义:图灵机首先检查输入是否是所要对象的编码,如果不是就拒绝,理论计算机科学基础,91,例4.14A=|G是连通无向图,分析:洪水算法(标记算法)高层描述:M=“输入是图G的编码:1)选择G的第一个顶点,并做上标记.2)重复下列步骤,直到没有新顶点可做标记.3)对于G的每个顶点,如果它是带标记顶点的邻点,则给它做上标记.4)扫描G的所有顶点,确定是否都已做上标记,如果是就接受,否则拒绝.”,理论计算机科学基础,92,例4.14实现描述的细节,图G的编码=(1,2,3,4)(1,2),(2,3),(3,1),(1,4)检查输入合法性顶点序列不含重复元素边序列中的顶点应该在顶点序列中算法步骤1)在最左端数字上加个点2,3)在一个未加点的顶点n1下画线,在一个已加点的顶点n2下画线,扫描边序列寻找(n1,n2),重新设置下画线4)扫描顶点序列,检查是否都已加点,递归定理及其证明(自我复制),理论计算机科学基础,93,理论计算机科学基础第9讲,94,悖论,生物都是机器现代假设生物都能自再生显然机器不能自再生错误!递归定理,理论计算机科学基础第9讲,95,引理7.1,引理7.1:存在可计算函数q:*,对任意串w,q(w)是图灵机Pw的描述,TMPw打印出w,然后停机.说明:w,q(w)=x,Pw(x)=w对任何w,Pw都存在从w得到的过程,是可计算的,理论计算机科学基础第9讲,96,引理7.1证明,证明:TMQ=“对输入串w:1)构造下列TMPw:Pw=“对任何输入:a)抹去输入;b)写下w;c)停机.”2)输出.”#,理论计算机科学基础第9讲,97,自我复制机,自己打印自己的TMTMSELFx,SELF(x)=main()printf(“main()printf(“main()”);=x,A(x)=,B(x)=,理论计算机科学基础第9讲,98,TMSELF,TMSELF打印构造:=.A=P,=q()B=“对输入,是TM的部分描述:1)计算q();2)用q()和合成完整的TM描述;3)打印这个描述,然后停机.”,理论计算机科学基础第9讲,99,递归定理,定理7.2(递归定理):设TMT计算函数t:*,则存在TMR计算函数r:*,使得w,r(w)=t(,w).说明:若t(x,y)是2元函数,则固定输入x=c后,变成1元函数t(c,y)若t(x,y)可计算,则对任意c,t(c,y)也可计算递归定理说:存在c,使得c就是计算t(c,y)的程序!,理论计算机科学基础第9讲,100,递归定理的证明,t:*,r:*,r(w)=t(,w)=,理论计算机科学基础第9讲,101,定理7.2递归定理的证明,证明:=,A=P,=q().B=“对输入w,输出q(w)”.TMR=“对输入w:1)运行A,在带上写下;2)运行B,在带上写下,拼装出;3)对运行T.”#注:q见引理7.1.,递归定理的应用(通用机),理论计算机科学基础,102,理论计算机科学基础第9讲,103,递归定理的用途,TM自引用定义可以在M的定义中使用,即TMM=“”是合法定义!先定义TMT=“对输入x,y:x”根据递归定理,存在这样的RTMR=“对输入y:”代替对角化证明ATM不可判定,MINTM不可识别不动点定理可计算函数t,TMF,L(t()=L(F),理论计算机科学基础第9讲,104,应用递归定理的术语,可以在M的定义中使用TMM=“得到自己的一个描述,”或:TMM=“”例:TMSELF=“对任意输入,1)利用递归定理得到自己的描述;2)打印.”或:TMSELF=“对任意输入,打印”,理论计算机科学基础第7讲,105,图灵机接受性问题,TM接受性问题检查一个图灵机是否接受一个给定的串语言ATM=|TMM接受串w,理论计算机科学基础第7讲,106,引理,引理:ATM是图灵可识别的证明思路:设计TMU模拟M在w上的计算当M在w上停机接受时,U接受当M在w上停机拒绝时,U拒绝当M在w上不停机时,U