丘奇-图灵论题ppt课件

精选,1,朴秀峰xfpiao,计算理论,第3章丘奇-图灵论题,精选,2,引言,什么是计算？计算机的基本能力和局限性是什么？,精选,3,引言,计算机科学历史上关于概念的争论,什么是计算什么是操作系统基本上解决什么internet?什么是数据库什么是数据仓库还在争论什么是数据网格解决方法，给出大众能理解的代表,精选,4,引言,计算机科学历史上关于概念的争论,解决的办法，给出一个代表什么是3的倍数3N|N=1,2,3,x|xmod3=0代表元：3什么是操作系统代表元：Windows,Unix什么internet代表元：大众理解：Web，IE什么是计算?多个模型；代表元：图灵机,或递归函数论,精选,5,引言,在还没有计算机的时候，凭想象力把后来出现的把计算机的理论模型建立起来了。1936年想得如此周到、严密好像从高度文明的外星来的文化使者,精选,6,引言,AlanM.Turing(19121954),In1936,Turingintroducedhisabstractmodelforcomputationinhisarticle“OnComputableNumbers,”.,Atthesametime,AlonzoChurchpublishedsimilarideasandresults.殊途同归,Turingmodel成为理论计算科学的标准模型standardmodel,精选,7,引言,图灵机（TuringMachine，TM），是计算机的一种简单的数学模型。历史上，冯诺曼计算机的产生就是由图灵机诱发的。丘奇图灵论题：一切合理的计算模型都等同于图灵机.,精选,8,主要内容,3.1丘奇图灵论题3.1.1图灵机的形式化定义3.1.2图灵机的例子3.2图灵机的变形3.2.1多带图灵机3.2.2非确定型图灵机3.2.3枚举器3.2.4与其他模型的等价性3.3算法的定义3.3.1希尔伯特问题3.3.2描述图灵机的术语,精选,9,3.1图灵机(TurningMachine),非形式化描述,根据当前状态和字符xi，决定写移转三动作-写letter,有存储器-左或右移动转移状态可以作循环语句磁带相当于数组，可读写。这是增加的重要资源,每一步，读写头在单向无穷带上左右移动并读写。,精选,10,图灵机,stateq0,初始,带子上只有输入串w*,其它地方是空的。开始状态q0。,计算过程中读写头左右移动，机器内部状态改变，带子上内容重写。,数组结构,精选,11,图灵机,输出约定,三种输出：接受、拒绝、循环,非常规意义循环不停机引出可判定性,精选,12,图灵机与有限自动机,状态控制器,相似性：有限状态集区别：(1)图灵机在带子上既能读也能写。(2)图灵机的读写头既能向左也能向右移动。(3)图灵机的带子是无限长的。(4)图灵机进入拒绝和接受状体将立即停机。,精选,13,图灵机,考虑图灵机M1，它检查语言B=w#w|w0,1*的成员关系。即设计M1，使得如果输入是B的成员，它就接受，否则拒绝。M1=“对于输入字符串w(1)在#两边对应的位置上来回移动，检查这些对应位置是否包含相同的符号，如不是，或者没有#，则拒绝，为跟踪对应的符号，消去所有检查过的符号。(2)当#左边的所有符号都被消去时，检查#右侧是否还有符号，如果有则拒绝，否则接受。”,精选,14,M1的运行示意图,M,Tapeheadmovestoright,精选,15,M1的运行示意图,M,Tapeheadmovestoleft,精选,16,M1的运行示意图,M,Tapeheadmovestoright,精选,17,M1的运行示意图,M,Tapeheadmovestoleft,精选,18,M1的运行示意图,M,Tapeheadmovestoright,精选,19,M1的运行示意图,M,Tapeheadmovestoleft,精选,20,M1的运行示意图,M,accept,Tapeheadmovestoright,精选,21,图灵机的形式化定义,定义3.1,图灵机是一个7元组(Q,q0,qaccept,qreject)(1)Q是状态集。(2)是输入字母表，不包括特殊空白符号。(3)是带字母表，其中并且。(4):QQL,R是转移函数。(5)q0是起始状态。(6)qaccept是接受状态。(7)qreject是拒绝状态，qacceptqreject。,例如:(q,a)=(r,b,L),精选,22,图灵机的计算方式,开始时，M以最左边的n个带方格接收输入w=w1w2wn*，带的其余部分保持空白(即填以空白符)，读写头从最左边的带方格开始运行，注意不含空字符，故出现在带上的第一个空字符表示输入的结束。M开始运行后，计算根据转移函数所描述的规则进行，如果M试图将读写头从带的最左端再向左移出，即使转移函数指示的是L，读写头也停在原地不动。计算一直持续到它进入接受状态或拒绝状态，此时停机，如果二者都不发生，则M将永远运行下去。,精选,23,图灵机的格局,图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图灵机的格局。对于状态q和带字母表的两个字符串u和v，以uqv表示如下格局：当前状态是q，当前带上的内容是uv，读写头的当前位置是v的第一个符号，带上v的字符最后字符以后的符号都是空白符。例如，1011q701111,q7,精选,24,图灵机计算方式的形式化,如果图灵机能合法地从格局C1一步进入C2，则称格局C1产生格局C2。设a,b和c是中的符号，u和v是*中字符串，qi和qj是状态，则uaqibv和uqjacv是两个格局。如果转移函数满足(qi,b)=(qj,c,L)，则说uaqibv产生和uqjacv。M在输入w上的起始格局是格局q0w，表示机器处于起始状态q0，并且读写头处于带子的最左端位置，在接受格局里，状态是qaccept，在拒绝格局里，状态是qreject。接受和拒绝状态都是停机状态，它们都不再产生新的格局。由于图灵机只在接受或拒绝状态下才停机，可以等价地将状态转移函数简化:QQL,R其中Q是取消qaccept和qreject的Q。,精选,25,图灵机计算方式的形式化,图灵机M接受输入w，如果存在格局的序列Cl,C2,Ck使得：(1)Cl是M在输入w上的起始格局；(2)每一个Ci产生Ci+1；(3)Ck是接受格局。M接受的字符串的集合称为M的语言，或被M识别的语言，记为L(M)。,精选,26,图灵机的形式化定义,定义3.2,如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的(Turningrecognizable)。也称为递归可枚举语言。,输入上运行一个TM时，可能出现三种结果：接受、拒绝、循环（仅仅指机器不停机）对于一个输入，TM有两种方式不接受它：一种拒绝状态一种进入循环问题：如何区别长计算与死循环？,因此，我们喜欢对所有输入都停机的图灵机，永不循环，这种机器为判定器。因为它们总能决定是接受还是拒绝。,精选,27,图灵机的形式化定义,定义3.3,如果一个语言能被某一图灵机判定，则称该语言是图灵可判定的(Turningdecidable)。也称为递归语言。,可识别与可判定？1.可识别接受该语言；2.可判定可以不接受该语言。,精选,28,图灵机举例,例3.4描述TMM2，它识别的语言是所有由0组成、长度为2的方幂的字符串，即A=|n0,M2=“对于输入字符串w：1)从左往右扫描整个带子，隔一个字符消去一个0。2)如果在第1步之后，带子上只剩下唯一的一个0，则接受。3)如果在第1步之后，带子上包含不止一个0，并且0的个数是奇数，则拒绝。4)读写头返回至带子的最左端。5)转到第1步。”,精选,29,图灵机举例,q1,q3,q4,qreject,q2,qaccept,q5,0,R,RxR,R,0x,R,xR,xR,L,0R,xR,R,0x,R,xL0L,R,精选,30,图灵机的例子,每重复一次第1步，消去了一半个数的0。由于在第1步中，机器扫描了整个带子，故它能够知道它看到的0的个数是奇数还是偶数，如果是大于1的奇数，则输入中所含的0的个数不可能是2的方幂，此时机器就拒绝。但是，如果看到的0的个数是1，则输入中所含的0的个数肯定是2的方幂，此时机器就接受。M2=(Q,q1,qaccept,qreject)的形式化描述：Q=q1,q2,q3,q4,q5,qaccept,qreject，=0，=0,x,，将描述成状态图开始、接受和拒绝状态分别是q1,qaccept,qreject,精选,31,图灵机举例,例3.5下面给出图灵机M1形式化描述M1=(Q,q1,qaccept,qreject)，它的判定语言是B=w#w|w0,1*。,Q=q1,q2,q8,qaccept,qreject，=0,1,#且=0,1,#,x,。用状态图描述。开始、接受和拒绝状态分别是q1,qaccept,qreject。,精选,32,图灵机M1的状态图,q1,q8,q3,q5,q6,q4,q7,qaccept,q2,#R,xR,R,0,1R,#R,xR,0,1,xL,0,1L,#L,xR,1x,L,1x,R,0x,L,#R,0x,R,0,1R,xR,第一步由q1到q7实现，第二步由其余状态实现,精选,33,图灵机举例,例3.6图灵机M3做一些初等算术，它判定的语言C=aibjck|ij=k，且i,j,k1,M3=“对于输入字符串w：1)从左往右扫描输入，确认输入具有形式a*b*c*，否则拒绝。2)读写头回到带子的左端点。3)消去一个a，并向右扫描直到b出现。在b与c之间来回移动，成对地消去b和c，直到把所有的b都消去。如果c全消除后还有b，则拒绝。4)如果还有a未消去，则恢复所有已消去的b，再重复第3步。如果所有的a都已被消去，则检查所有的c是否都已被消去。如果是，则接受，否则拒绝。”,精选,34,图灵机举例,例3.7图灵机M4解所谓的元素区分问题。给出一列0,1组成的字符串系列，字符串之间用符号#隔开，M4的任务是：如果此序列中的所有字符串都不同，则接受。此语言是：E=#x1#x2#xl，xi0,1*,且对任意ij，xixj,机器M4将x1与x2到xl进行比较，然后将x2与x3到xl进行比较，依此类推。M4的非形式描述如下。,精选,35,图灵机举例,M4=“对于输入的w：1)在最左端的带符号的顶上做个记号。如果此带符号是空白符，则接受。如果此符号是#，则进行下一步。否则，拒绝。2)向右扫描下一个#，并在其顶上做第二个记号。如果在遇到空白符之前没有遇到#，则带上只有x1，因此接受。3)通过来回移动，比较做了记号的#的右边的两个字符串，如果它们相等，则拒绝。4)将两个记号中右边的那个向右移到下一个#上。如果在碰到空白符之前没有遇到#，则将左边的记号向右移到下一个#上，并且将右边记号移到后面的#上。如果这时右边记号还找不到#，则所有的字符串都已经比较过了，因而接受。5)转到第3步继续执行。”,精选,36,主要内容,3.1丘奇图灵论题3.1.1图灵机的形式化定义3.1.2图灵机的例子3.2图灵机的变形3.2.1多带图灵机3.2.2非确定型图灵机3.2.3枚举器3.2.4与其他模型的等价性3.3算法的定义3.3.1希尔伯特问题3.3.2描述图灵机的术语,精选,37,图灵机的变形,从不同的方面对TM进行扩充。双向无穷带TM允许TM的输入带是无穷的。多带TM允许TM有多于一条的输入带。此时每条带上将有一个读头。不确定的TM允许TM在某一状态下根据读入的符号选择地进行某一个动作：进入某个状态，在读头的当前位置印刷某个符号，将读头移向某个方向。多维TM相当于在双向TM的基础上进一步扩充，允许TM的“输入带”向更多的方向延伸。枚举器允许图灵机带有打印机。它们与基本的TM等价。在形式变化中保持不变的性质称为稳健性。,精选,38,多带图灵机,多带图灵机(multitapeTuringMachine)很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许多个带子同时进行读、写和移动读写头，其形式为：QkQkL,R,Sk此处k是带子的个数。表达式(qi,a1,a2,ak)=(qj,b1,b2,bk,L,R,L)指的是：若机器处于状态qi，读写头1到k所读的符号分别是a1到ak，则机器转移到状态qj，各读写头分别写下符号b1到bk，且按此式所指示的那样移动每个读写头。,精选,39,多带图灵机,将一个多带TMM转换为一个与之等价的单带TMS，关健是怎样用S来模拟M。假设M有k个带子。S把此k个带子的信息都存储在它的唯一带子上，并以此来模拟k个带子的效果，它用一个新的符号#作为定界符，以分开不同带子的内容。除了带内容之外，S还必须记录读写头的位置。为此，它在一个符号的顶上加个点，以此来标记读写头在其带上的位置。S把它们想象为虚拟带子和虚拟读写头。像以前一样，加点的带符号应是已经加进带字母表的新符号。,精选,40,多带图灵机,精选,41,多带图灵机,S=“对于输入w=w1wn：1)S在白己的带子上放入#w1w2wn#（上边没加点）此格式表示了M的全部k个带子的内容。2)为了模拟多带机的一步移动，S在其带子上从标记左端点的第一个#开始扫描，一直扫描到标记右端点的第(k+1)个#。其目的是确定虚拟读写头下的符号。然后S进行第二次扫描，并根据M的转移函数指示的运行方式更新其带子。3)任何时候，只要S将某个虚拟读写头向右移动到某个#上面，就意味着M已将自己相应的读写头移动到了其所在的带子中的空白区域上，即以前没有读过的区域上。因此，S在这个带方格上写下空白符，并将这个带方格到最右端的带方格中的内容都向右移动一个格。然后再像以前一样继续模拟。”,精选,42,多带图灵机,推论3.9,一个语言是图灵可识别的，当且仅当存在多带图灵机识别它。,一个图灵可识别语言可由一个普通的(单带)图灵机识别，这个普通图灵机是多带图灵机的一个特例，这就证明了此推论的一个方向。另一个方向可由定理3.8得证。,精选,43,非确定型图灵机,非确定型图灵机的有如其名，在计算的过程中，机器可以在多种可能性动作中选择一种继续进行。它的转移函数具有如下形式：:QP(QL,R）其计算是一棵树，不同分支对应着机器的不同可能性。,精选,44,非确定型图灵机,定理3.10,每个非确定型图灵机都等价于某一个确定型图灵机。,能用确定型TMD来模拟非确定型TMN的计算的证明思路是：让D试验N的非确定性计算的所有可能分支，若D能在某个分支中到达接受状态，则接受；否则D的模拟将永不终止。将N在输入w的计算看作一棵树，树的每个分支代表非确定型的分支，结点是N的一个格局，根是起始格局。TMD在这个树上搜索接受格局。我们采用“宽度优先”策略搜索整棵树，这个策略是：在搜索一个深度内的所有分支之后，再去搜索下一个深度内的所有分支。此方法能保证D可以访问树的所有结点，直到它遇到接受格局。,精选,45,非确定型图灵机,用于模拟的确定型TMD有3个带子。根据定理3.8，这等价于只有一个带子。机器D将这三个带子用于专门用途。第一个带子包含输入串，且不再改变；第二个带子存放N的带子中的内容，此内容对应N的非确定性计算的某个分支；第三个带子记录D在N的非确定性计算树中的位置。,输入带,模拟带,地址带,精选,46,非确定型图灵机,首先考虑第三个带子上表示的数据。N的每个格局确定一个集合，它是由此格局可能转移到的下一个格局组成，这些下一个格局是由N的转移函数指定的。N的非确定性计算中的每个结点最多有b个子结点，其中：b是上述集合中最大的集合所含的元素个数。对树的每个结点，可以给其分配一个地址，它是字母表b=1，2，b上的一个串。例如，把地址231分配给按以下方式到达的结点：从根出发走到它的第二个子结点，再由此走到第三个子结点，最后由此走到第一个子结点。此串中的数字告诉我们：在模拟N的非确定计算的一个分支时下一步应做什么。如果一个格局所能有的选择太少，则一个符号可能不对应任何选择。此种倩况下，地址将无效，不对应任何结点。第三个带子上包含b上的一个串，它代表N的计算树中如下分支：起点是根，终点是此串表示的地址所对应的结点，除非这个地址是无效的。空串是树根的地址。,精选,47,非确定型图灵机,D的描述如下：1)开始时，第一个带子包含输入w，第二和第三个带子都是空的。2)把第一个带子复制到第二个带子上。3)用第二个带子去模拟N在输入w上的非确定性计算的某个分支。在N的每一步动作之前，查询第三个带子上的下一个数字，以决定在N的转移函数所允许的选择中作何选择。如果第三个带子上没有符号剩下，或这个非确定性的选择是无效的，则放弃这个分支，转到第4步。如果遇到拒绝格局也转到第4步。如果遇到接受格局，则接受这个输入。4)在第二个带子上，用字典顺序下的下一个串来替代原有的串。转到第2步，以模拟N的计算的下一个分支。,精选,48,非确定型图灵机,推论3.11,一个语言是图灵可识别的，当且仅当存在非确定型图灵机识别它。,推论3.12,一个语言是可判定的，当且仅当存在非确定型图灵机判定它。,确定型图灵机自然是一个非确定型图灵机，此定理的一个方向由此立刻得证。另个方向可内定理3.10得证。,精选,49,枚举器,它是图灵机的一种变形。粗略地说，枚举器是带有打印机的图灵机，图灵机把打印机当作输出设备，从而可以打印串。每当图灵机想在打印序列中增加一个串时，就把此串送到打印机。枚举器以空白输入带开始运行，如果不停机，它可能会打印出串的一个无限序列。枚举器E所枚举的语言是最终打印出的串的集合。而且E可能以任意顺序生成这个语言中的串，甚至还会有重复。,精选,50,枚举器示意图,控制器,打印机,aababaabba,工作带,精选,51,枚举器,定理3.13,一个语言是图灵可识别的，当且仅当存在枚举器枚举它。,精选,52,枚举器,首先证明，如果有枚举器E枚举语言A，则有TMM识别A。TMM如下运行：M=“对于输入w：1)运行E。每当E输出一个串时，将之与w比较。2)如果w曾经在E的输出中出现过，则接受。”显然，M接受在E的输出序列中出现过的那些串。现在证明另一个方向。设s1，s2，s3，是*中的所有串。如果有TMM识别语言A，为A构造枚举器E如下：E“忽略输入。1)对i1，2，3，重复下列步骤。2)对s1，s2，s3，si中的每一个，M以其作为输入运行i步3)如果有计算接受，则打印出相应的sj。”如果M接受串s，它终将出现在E生成的打印列表中。,精选,53,通用图灵机,通用TM(universalTuringmachine)实现对所有TM的模拟。编码系统它可以在实现对TM的表示的同时，实现对该TM处理的句子的表示。用0和1对这些除空白符以外的其他的带符号进行编码。同时也可以用0和1对TM的移动函数进行编码。,精选,54,通用图灵机,M=(q1,q2,qn,0,1,0,1,B,q1,B,q2)用X1,X2,X3分别表示0,1,B，用D1,D2分别表示R,L。(qi,Xj)=(qk,Xl,Dm)可以用0i10j10k10l10m表示。M可用111code111code21111coder111codet是动作(qi,Xj)=(qk,Xl,Dm)的形如0i10j10k10l10m的编码。TMM和它的输入串w则可以表示成111code111code21111coder111w按照规范顺序分别对表示TM的符号行和表示输入的符号行进行排序。,精选,55,通用图灵机,设TMM2=(q1,q2,q3,q4,0,1,0,1,B,q4,B,q3)，其中的定义如下:(q4,0)=(q4,0,R)(q4,1)=(q1,1,R)(q1,0)=(q1,0,R)(q1,1)=(q2,1,R)(q2,0)=(q2,0,R)(q2,1)=(q3,1,R)编码为1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111通用TM检查M是否接受字符串0011011101110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111001101110,精选,56,主要内容,3.1丘奇图灵论题3.1.1图灵机的形式化定义3.1.2图灵机的例子3.2图灵机的变形3.2.1多带图灵机3.2.2非确定型图灵机3.2.3枚举器3.2.4与其他模型的等价性3.3算法的定义3.3.1希尔伯特问题3.3.2描述图灵机的术语,精选,57,算法的定义,非形式地说，算法是为实现某个任务而构造的简单指令集。在日常用语来说，算法有时称为过程或处方。算法在数学中也起着重要的作用。古代数学文献中包含了各种各样任务的算法描述，如寻找素数和最大公因子。当代数学中更是充满了算法。,精选,58,希尔伯特问题,1900年希尔伯特提出了23个数学问题。其中的第10个问题是关于算法的。通过有限多次运算就可以决定的过程。一个多项式是一些项的和，其中：每个项都是一个常数和一些变元的积，此常数叫系数（coefficient）。例如，6xxxyzz=6x3yz2是一个项，其系数是6；6x3yz2+3xy2-x3-10是一个多项式，它有四个项和三个变元x、y、z多项式的根（root）是对它的变元的一个赋值，使此多项式的值为0。上述多项式的一个根是x=5、y=3和z=0，这个根是整数根（integralroot），因为所有变元都被赋予整数值。,精选,59,希尔伯特问题,丘奇-图灵论题（Church-Turingthesis）希尔伯特第10问题旨在设计一个算法来检测一个多项式是否有整数根。现在用上述术语来重新陈述希尔伯特第10问题，设D=p|p是有整数根的多项式本质上，希尔伯特