丘奇-图灵论题

1朴秀峰[e-mail]计算理论2引言什么是计算？计算机的基本能力和局限性是什么？其它情况个的展开式中连续有若051)(nng3引言计算机科学历史上关于概念的争论什么是计算什么是操作系统基本上解决什么internet?什么是数据库什么是数据仓库还在争论什么是数据网格解决方法，给出大众能理解的代表4引言计算机科学历史上关于概念的争论解决的办法，给出一个代表什么是3的倍数{3N|N=1,2,3},{x|xmod3=0}代表元：3什么是操作系统代表元：Windows,Unix什么internet代表元：大众理解：Web，IE什么是计算?多个模型；代表元：图灵机,或递归函数论5引言在还没有计算机的时候，凭想象力把后来出现的把计算机的理论模型建立起来了。1936年想得如此周到、严密好像从高度文明的外星来的文化使者6引言AlanM.Turing(1912–1954)In1936,Turingintroducedhisabstractmodelforcomputationinhisarticle“OnComputableNumbers,”.Atthesametime,AlonzoChurchpublishedsimilarideasandresults.殊途同归Turingmodel成为理论计算科学的标准模型standardmodel7引言图灵机（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描述图灵机的术语93.1图灵机(TurningMachine)非形式化描述根据当前状态和字符xi，决定写移转三动作-写letter,有存储器-左或右移动-转移状态可以作循环语句磁带相当于数组，可读写。这是增加的重要资源internalstatesetQRL__1#0_1101每一步，读写头在单向无穷带上左右移动并读写。10图灵机stateq0___初始,带子上只有输入串w*,其它地方是空的。开始状态q0。计算过程中读写头左右移动，机器内部状态改变，带子上内容重写。•数组结构11图灵机输出约定三种输出：接受、拒绝、循环stateqaccept_vvvm21stateqreject_vvvm21or非常规意义循环——不停机引出可判定性12图灵机与有限自动机状态控制器aab相似性：有限状态集区别：(1)图灵机在带子上既能读也能写。(2)图灵机的读写头既能向左也能向右移动。(3)图灵机的带子是无限长的。(4)图灵机进入拒绝和接受状体将立即停机。13图灵机考虑图灵机M1，它检查语言B={w#w|w∈{0,1}*}的成员关系。即设计M1，使得如果输入是B的成员，它就接受，否则拒绝。M1=“对于输入字符串w(1)在#两边对应的位置上来回移动，检查这些对应位置是否包含相同的符号，如不是，或者没有#，则拒绝，为跟踪对应的符号，消去所有检查过的符号。(2)当#左边的所有符号都被消去时，检查#右侧是否还有符号，如果有则拒绝，否则接受。”14M1的运行示意图01100#01100X1100#01100X1100#01100X1100#01100MTapeheadmovestoright15M1的运行示意图X1100#01100X1100#01100X1100#X1100X1100#X1100MTapeheadmovestoleft16M1的运行示意图X1100#X1100X1100#X1100XX100#X1100XX100#X1100MTapeheadmovestoright17M1的运行示意图XX100#X1100XX100#X1100XX100#XX100XX100#XX100MTapeheadmovestoleft18M1的运行示意图XX100#XX100XX100#XX100XXX00#XX100XXX00#XX100MTapeheadmovestoright19M1的运行示意图XXXXX#XXXX0XXXXX#XXXXXXXXXX#XXXXXMXXXXX#XXXXXTapeheadmovestoleft20M1的运行示意图XXXXX#XXXXXXXXXX#XXXXXXXXXX#XXXXXMXXXXX#XXXXXacceptTapeheadmovestoright21图灵机的形式化定义定义3.1图灵机是一个7元组(Q,,,,q0,qaccept,qreject)(1)Q是状态集。(2)是输入字母表，不包括特殊空白符号。(3)是带字母表，其中并且。(4):Q×Q××{L,R}是转移函数。(5)q0是起始状态。(6)qaccept是接受状态。(7)qreject是拒绝状态，qaccept≠qreject。例如:(q,a)=(r,b,L)22图灵机的计算方式开始时，M以最左边的n个带方格接收输入w=w1w2…wn*，带的其余部分保持空白(即填以空白符)，读写头从最左边的带方格开始运行，注意不含空字符，故出现在带上的第一个空字符表示输入的结束。M开始运行后，计算根据转移函数所描述的规则进行，如果M试图将读写头从带的最左端再向左移出，即使转移函数指示的是L，读写头也停在原地不动。计算一直持续到它进入接受状态或拒绝状态，此时停机，如果二者都不发生，则M将永远运行下去。w1w2……wn23图灵机的格局图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图灵机的格局。对于状态q和带字母表的两个字符串u和v，以uqv表示如下格局：当前状态是q，当前带上的内容是uv，读写头的当前位置是v的第一个符号，带上v的字符最后字符以后的符号都是空白符。例如，1011q701111101101111q724图灵机计算方式的形式化如果图灵机能合法地从格局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。接受和拒绝状态都是停机状态，它们都不再产生新的格局。由于图灵机只在接受或拒绝状态下才停机，可以等价地将状态转移函数简化:Q'×Q××{L,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={|n≥0}20nM2=“对于输入字符串w：1)从左往右扫描整个带子，隔一个字符消去一个0。2)如果在第1步之后，带子上只剩下唯一的一个0，则接受。3)如果在第1步之后，带子上包含不止一个0，并且0的个数是奇数，则拒绝。4)读写头返回至带子的最左端。5)转到第1步。”29图灵机举例q1q3q4qrejectq2qacceptq50,RRxRR0x,RxRxRL0RxRR0x,RxL0LR30图灵机的例子每重复一次第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,qreject31图灵机举例例3.5下面给出图灵机M1形式化描述M1=(Q,,,,q1,qaccept,qreject)，它的判定语言是B={w#w|w{0,1}*}。Q={q1,q2,…,q8,qaccept,qreject}，={0,1,#}且={0,1,#,x,}。用状态图描述。开始、接受和拒绝状态分别是q1,qaccept,qreject。32图灵机M1的状态图q1q8q3q5q6q4q7qacceptq2#RxR□R0,1R#RxR0,1,xL0,1L#LxR#R0,1RxR第一步由q1到q7实现，第二步由其余状态实现33图灵机举例例3.6图灵机M3做一些初等算术，它判定的语言C={aibjck|i×j=k，且i,j,k≥1}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，xi{0,1}*,且对任意i≠j，xi≠xj}机器M4将x1与x2到xl进行比较，然后将x2与x3到xl进行比较，依此类推。M4的非形式描述如下。35图灵机举例M4=“对于输入的w：1)在最左端的带符号的顶上做个记号。如果此带符号是空白符，则接受。如果此符号是#，则进行下一步。否则，拒绝。2)向右扫描下一个#，并在其顶上做第二个记号。如果在遇到空白符之前没有遇到#，则带上只有x1，因此接受。3)通过来回移动，比较做了记号的#的右边的两个字符串，如果它们相等，则拒绝。4)将两个记号中右边的那个向右移到下一个#上。如果在碰到空白符之前没有遇到#，则将左边的记号向右移到下一个#上，并且将右边记号移到后面的#上。如果这时右边记号还找不到#，则所有的字符串都已经比较过了，因而接受。5)转到第3步继续执行。”36主要内容3.1丘奇—图灵