唐常杰翻译的计算理论导引

2020/5/13,1/88,LectureforComputationTheory,Book:计算理论导引IntroductiontotheTheoryofComputationChapter3TuringMachineProf:唐常杰TangChangjieHttp:/,2020/5/13,2/88,Outlinefortoday,Section3.13.2:Computability（补充）3.1TuringmachinesTM-computable/recognizablelanguages3.2VariantsofTMs（多带机，不确定机）,2020/5/13,3/88,2020/5/13,4/88,2020/5/13,5/88,Intersectiona,b,c;qi,qjQ,andMaTMwithtransitionfunction.格局C1产生格局C2Wesaythattheconfiguration“uaqibv”yieldstheconfiguration“uacqjb”ifandonlyif:(qi,b)=(qj,c,R).格局产生即格局按机演化翻译成格局演进似更恰当Similarly,if(qi,b)=(qj,c,L)/把当前的b改为c且左移then“uaqibv”yields“uqjacb”(Attheleftmostsideofthetapedifferent.),2020/5/13,37/88,AnElementaryTMStepep129cp89,Letu,v*;a,b,c;qi,qjQ,andMaTMwithtransitionfunction.格局C1产生格局C2Wesaythattheconfiguration“uaqibv”yieldstheconfiguration“uacqjv”ifandonlyif:(qi,b)=(qj,c,R).格局产生即格局按机演化翻译成格局演进似更恰当Similarly,if(qi,b)=(qj,c,L)/把当前的b改为c且左移then“uaqibv”yields“uqjacv”(Attheleftmostsideofthetapedifferent.),2020/5/13,38/88,Terminology格局,startingconfigurationoninputw:“q0w”初始格局acceptingconfiguration:“uqacceptv”接受格局返回truerejectingconfiguration:“uqrejectv”拒绝格局返回falseTheacceptingandrejectingconfigurationsarethehaltingconfigurations.,2020/5/13,39/88,Terminology格局,startingconfigurationoninputw:“q0w”初始格局acceptingconfiguration:“uqacceptv”接受格局返回truerejectingconfiguration:“uqrejectv”拒绝格局返回falseTheacceptingandrejectingconfigurationsarethehaltingconfigurations.,2020/5/13,40/88,用格局概念描述Acceptingep129,cp89,ATuringmachineMacceptsinputw*ifandonlyifthereisafinitesequenceofconfigurationsC1,C2,CkwithC1thestartingconfiguration“q0w”foralli=1,k1CiyieldsCi+1(followingMs)Ckisanacceptingconfiguration“uqacceptv”ThelanguagethatconsistsofallinputsthatareacceptedbyMisdenotedbyL(M).比喻：boolM(w)最后返回true,2020/5/13,41/88,用格局概念描述Acceptingep129,cp89,ATuringmachineMacceptsinputw*ifandonlyifthereisafinitesequenceofconfigurationsC1,C2,CkwithC1thestartingconfiguration“q0w”foralli=1,k1CiyieldsCi+1(followingMs)Ckisanacceptingconfiguration“uqacceptv”ThelanguagethatconsistsofallinputsthatareacceptedbyMisdenotedbyL(M).比喻：boolM(w)最后返回true,2020/5/13,42/88,用格局概念描述Acceptingep129,cp89,ATuringmachineMacceptsinputw*ifandonlyifthereisafinitesequenceofconfigurationsC1,C2,CkwithC1thestartingconfiguration“q0w”foralli=1,k1CiyieldsCi+1(followingMs)Ckisanacceptingconfiguration“uqacceptv”ThelanguagethatconsistsofallinputsthatareacceptedbyMisdenotedbyL(M).比喻：boolM(w)最后返回true,2020/5/13,43/88,用格局概念描述Acceptingep129,cp89,比喻录取会议论文TuringmachineM录取标准，程序委员会acceptsinputw*字符串，论文，configurationsC1,C2,Ck评审过程acceptingconfiguration“uqacceptv”录用uqrejectv”拒绝评审无反响-死机,2020/5/13,44/88,TuringRecognizable(Def.3.2)ep130cp89,AlanguageLisTuring-recognizableifandonlyifthereisaTMMsuchthatL=L(M).图灵可识:对wL函数M(w)返回true，对wL，无承诺,Note:OnaninputwL,themachineMcanhaltinarejectingstate,oritcanloopindefinitely.,Howdoyoudistinguishbetweenaverylongcomputationandonethatwillneverhalt?问题：如何区别长计算与死循环？,Alsocalled:arecursivelyenumerablelanguage.L又称为递归可枚举语言,2020/5/13,45/88,TuringRecognizable(Def.3.2)ep130cp89,AlanguageLisTuring-recognizableifandonlyifthereisaTMMsuchthatL=L(M).图灵可识:对wL函数M(w)返回true，对wL，无承诺,Note:OnaninputwL,themachineMcanhaltinarejectingstate,oritcanloopindefinitely.,Howdoyoudistinguishbetweenaverylongcomputationandonethatwillneverhalt?问题：如何区别长计算与死循环？,Alsocalled:arecursivelyenumerablelanguage.L又称为递归可枚举语言,2020/5/13,46/88,TuringRecognizable(Def.3.2)ep130cp89,AlanguageLisTuring-recognizableifandonlyifthereisaTMMsuchthatL=L(M).图灵可识:对wL函数M(w)返回true，对wL，无承诺,Note:OnaninputwL,themachineMcanhaltinarejectingstate,oritcanloopindefinitely.,Howdoyoudistinguishbetweenaverylongcomputationandonethatwillneverhalt?问题：如何区别长计算与死循环？,Alsocalled:arecursivelyenumerablelanguage.L又称为递归可枚举语言,2020/5/13,47/88,TuringDecidable(Def.3.3)图灵可判定ep130，cp84,Alsocalled:arecursivelanguage.递归语言，比递归可枚举要求高,AlanguageL=L(M)isdecidedbytheTMMifoneveryw,theTMfinishesinahaltingconfiguration.(Thatis:qacceptforwLandqrejectforallwL.)图灵可判定:对wL函数M(w)返回true，对wL，返回false,AlanguageLisTuring-decidableifandonlyifthereisaTMMthatdecidesL.图灵可判定语言,2020/5/13,48/88,TuringDecidable(Def.3.3)图灵可判定ep130，cp89,Alsocalled:arecursivelanguage.递归语言，比递归可枚举要求高,AlanguageL=L(M)isdecidedbytheTMMifoneveryw,theTMfinishesinahaltingconfiguration.(Thatis:qacceptforwLandqrejectforallwL.)图灵可判定:对wL函数M(w)返回true，对wL，返回false,AlanguageLisTuring-decidableifandonlyifthereisaTMMthatdecidesL.图灵可判定语言,2020/5/13,49/88,TuringDecidable(Def.3.3)图灵可判定ep130，cp89,Alsocalled:arecursivelanguage.递归语言，比递归可枚举要求高,AlanguageL=L(M)isdecidedbytheTMMifoneveryw,theTMfinishesinahaltingconfiguration.(Thatis:qacceptforwLandqrejectforallwL.)图灵可判定:对wL函数M(w)返回true，对wL，返回false,AlanguageLisTuring-decidableifandonlyifthereisaTMMthatdecidesL.图灵可判定语言,2020/5/13,50/88,Exa.3.4:判定A=0j|j=2n，n=0ep131，cp90,BoolM(w)/用C语言模拟TM,注意不要超标使用资源if(1appearinw)returnfalse;j=length(w);loop:If(j=1)returntrue;if(jmod2=0)i-;gotoloop;elsereturnfalse;/注意无论j为何值，总有结果,Checkifj=0orj=1,accept/rejectaccordinglyCheck,bygoinglefttorightifthestringhasevenoroddnumberofzerosIfoddthen“reject”Ifeventhengobackleft,erasinghalfthezerosgoto1算法伪码,2020/5/13,51/88,Exa.3.4:判定A=0j|j=2nep131，cp90,BoolM(j)/用C语言模拟TM,注意不要超标使用资源If(j=0)retuenfalse;If(j=1)returntrue;if(jmod2=0)returnM(j-1)/这里有点超前，使用了递归elseif(j1)returnfalse;/注意无论j为何值，总有结果,Checkifj=0orj=1,accept/rejectaccordinglyCheck,bygoinglefttorightifthestringhasevenoroddnumberofzerosIfoddthen“reject”Ifeventhengobackleft,erasinghalfthezerosgoto1算法伪码,2020/5/13,52/88,Exa.3.4:判定A=0j|j=2nep131，cp90,BoolM(j)/用C语言模拟TM,注意不要超标使用资源If(j=0)retuenfalse;If(j=1)returntrue;if(jmod2=0)returnM(j-1)/这里有点超前，使用了递归elseif(j1)returnfalse;/注意无论j为何值，总有结果,Checkifj=0orj=1,accept/rejectaccordinglyCheck,bygoinglefttorightifthestringhasevenoroddnumberofzerosIfoddthen“reject”Ifeventhengobackleft,erasinghalfthezerosgoto1算法伪码,2020/5/13,53/88,StatediagramsofTMs,LikewithPDA,wecanrepresentTuringmachinesby(elaborate)diagrams.SeeFiguresc4.4andc4.5fortwoexamples.见书Ep132,cp85未画出,大家一起读书,建议练习1：把图c4.4改写成为用goto(而不用递归）的C程序练习2:把有递归的程序改为迭代，再转化为图，比较简单，保存中间结果，j-1,以他作输入，重新计算Iftransitionrulesays:qi,b)=(qj,c,R),/读b写c且右移then:,qi,qj,bc,R,2020/5/13,54/88,StatediagramsofTMs,LikewithPDA,wecanrepresentTuringmachinesby(elaborate)diagrams.SeeFigures3.4andFig.3.5fortwoexamples.见书Ep132,cp90未画出,大家一起读书,建议练习1：把图3.4改写成为用goto(而不用递归）的C程序练习2:把有递归的程序改为迭代，再转化为图，比较简单，保存中间结果，j-1,以他作输入，重新计算Iftransitionrulesays:(qi,b)=(qj,c,R),/读b写c且右移then:,qi,qj,bc,R,2020/5/13,55/88,WhenDescribingTMep133,书上的例3.5,3.6,3.7比较细致，有点繁而不难，学生应仔细读一遍。课堂上讲较费时，效果不一定好以后有更高级的方法（例如给出的递归），体会一下低级方法的难处可忆苦思甜。,Standardtools:Expandingthealphabetwithseparator“#”,andunderlinedsymbols0,a,toindicateactivity.Typical:=0,1,#,_,0,1,2020/5/13,56/88,WhenDescribingTMep133,书上的例3.5,3.6,3.7比较细致，有点繁而不难，学生应仔细读一遍。课堂上讲较费时，效果不一定好以后有更高级的方法（例如给出的递归），体会一下低级方法的难处可忆苦思甜。,Standardtools:Expandingthealphabetwithseparator“#”,andunderlinedsymbols0,a,toindicateactivity.Typical:=0,1,#,_,0,1,2020/5/13,57/88,WhenDescribingTMep133略,ItisassumedthatyouarefamiliarwithTMsandwithprogrammingcomputers.,Clarityaboveall:highleveldescriptionofTMsisallowedbutshouldnotbeusedasatricktohidetheimportantdetailsoftheprogram.,Standardtools:Expandingthealphabetwithseparator“#”,andunderlinedsymbols0,a,toindicateactivity.Typical:=0,1,#,_,0,1,2020/5/13,58/88,3.2MultitapeTuringMachines多带图灵机ep136,cp93增加数组资源，期望编程简单,Ak-tapeTuringmachineMhaskdifferenttapesandread/writeheads.Itisthusdefinedbythe7-tuple(Q,q0,qaccept,qreject),withQfinitesetofstatesfiniteinputalphabet(without“_”)finitetapealphabetwith_q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction:Qqaccept,qrejectkQkL,Rk转写移,根据K条带上的存储数据现状决定写，移，转动作,2020/5/13,59/88,3.2MultitapeTuringMachines多带图灵机ep136,cp93,增加数组资源，期望编程简单,Ak-tapeTuringmachineMhaskdifferenttapesandread/writeheads.Itisthusdefinedbythe7-tuple(Q,q0,qaccept,qreject),withQfinitesetofstatesfiniteinputalphabet(without“_”)finitetapealphabetwith_q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction:Qqaccept,qrejectkQkL,Rk转写移,根据K条带上的存储数据现状决定写，移，转动作,2020/5/13,60/88,3.2MultitapeTuringMachines多带图灵机ep136,cp93,增加数组资源，期望编程简单,Ak-tapeTuringmachineMhaskdifferenttapesandread/writeheads.Itisthusdefinedbythe7-tuple(Q,q0,qaccept,qreject),withQfinitesetofstatesfiniteinputalphabet(without“_”)finitetapealphabetwith_q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction:Qqaccept,qrejectkQkL,Rk转写移,根据K条带上的存储数据现状决定写，移，转动作,2020/5/13,61/88,k-tapeTMsversus1-tapeTMsep137,cp93,Theorem3.8:Foreverymulti-tapeTMM,thereisasingle-tapeTMMsuchthatL(M)=L(M).Or,foreverymulti-tapeTMM,thereisanequivalentsingle-tapeTMM.多带机与单带机等价增加存储和数组(多带)只提速和简化，无本质改变,Provingandunderstandingthesekindsofrobustnessresults,isessentialforappreciatingthepoweroftheTuringmachinemodel.称为稳健性,FromthistheoremCorollaryc4.9follows:AlanguageLisTM-recognizableifandonlyifsomemulti-tapeTMrecognizesL.以后可用多带机作题，简单多了,2020/5/13,62/88,k-tapeTMsversus1-tapeTMsep137,cp93,Theorem3.8:Foreverymulti-tapeTMM,thereisasingle-tapeTMMsuchthatL(M)=L(M).Or,foreverymulti-tapeTMM,thereisanequivalentsingle-tapeTMM.多带机与单带机等价增加存储和数组(多带)只提速和简化，无本质改变,Provingandunderstandingthesekindsofrobustnessresults,isessentialforappreciatingthepoweroftheTuringmachinemodel.称为稳健性,FromthistheoremCorollaryc4.9follows:AlanguageLisTM-recognizableifandonlyifsomemulti-tapeTMrecognizesL.以后可用多带机作题，简单多了,2020/5/13,63/88,k-tapeTMsversus1-tapeTMsep137,cp88,Theorem3.8:Foreverymulti-tapeTMM,thereisasingle-tapeTMMsuchthatL(M)=L(M).Or,foreverymulti-tapeTMM,thereisanequivalentsingle-tapeTMM.多带机与单带机等价增加存储和数组(多带)只提速和简化，无本质改变,Provingandunderstandingthesekindsofrobustnessresults,isessentialforappreciatingthepoweroftheTuringmachinemodel.称为稳健性,FromthistheoremCorollaryc4.9follows:AlanguageLisTM-recognizableifandonlyifsomemulti-tapeTMrecognizesL.以后可用多带机作题，简单多了,2020/5/13,64/88,OutlineProofThm.3.8ep137,cp95,基本思想：用单磁头读4声道录音磁带,读出后复制在一条带上，通过mod(4),和数组下标映射，可以标识原产地，但能算出4带机的任务。内存少一些，程序复杂一点，慢一点。,2020/5/13,65/88,OutlineProofThm.3.8ep137,cp95,另一种比喻：先写一个有4个数组的C程序,然后写一个只有一个数组的程序去模拟上述程序，直观上是容易接受的，因为用下标映射实现模拟的难度不大。注意，现在下标需要顺序扫描，以后可证明可按下标随机存取图灵机（随机图灵机）写论文时从来不限制只能用低级图灵机证明问题，可以用最先进的工具。注意力集中在后面将要讨论的复杂度，P、NP问题，不必拘泥与这些技术细节,2020/5/13,66/88,OutlineProofThm.3.8ep137,cp95,另一种比喻：先写一个有4个数组的C程序,然后写一个只有一个数组的程序区模拟上述程序，直观上是容易接受的，因为用下标映射实现模拟的难度不大。注意，现在下标需要顺序扫描，以后可证明可按下标随机存取图灵机（随机图灵机）写论文时从来不限制只能用低级图灵机证明问题，可以用最先进的工具。注意力集中在后面将要讨论的复杂度，P、NP问题，不必拘泥与这些技术细节,2020/5/13,67/88,OutlineProofThm.3.8ep137,cp95模拟结构,造单带机模拟多带机（多带机模拟单带机不需证明）LetM=(Q,q0,qaccept,qreject)beak-tapeTM.Construct1-tapeMwithexpanded=#RepresentM-configurationu1qja1v1,u2qja2v2,ukqjakvkbyMconfiguration,qj#u1a1v1#u2a2v2#ukakvk分带符#,K道上当前字符,第1道第k道格局,2020/5/13,68/88,OutlineProofThm.3.8ep137,cp95模拟结构,造单带机模拟多带机（多带机模拟单带机不需证明）LetM=(Q,q0,qaccept,qreject)beak-tapeTM.Construct1-tapeMwithexpanded=#RepresentM-configurationu1qja1v1,u2qja2v2,ukqjakvkbyMconfiguration,qj#u1a1v1#u2a2v2#ukakvk分带符#,K道上当前字符,第1道第k道格局,2020/5/13,69/88,ProofThm.3.8(cont.)ep137,cp95模拟动作,Oninputw=w1wn,theTMMdoesthefollowing:Prepareinitialstring:#w1wn#_#_#_多带复制到单带Readtheunderlinedinputlettersk各带当前字SimulateMbyupdatingtheinputandtheunderliningofthehead-positions.通过下标映射模拟动作Repeat2-3untilMhasreachedahaltingstateHaltaccordingly.,PS:Iftheupdaterequiresoverwritinga#symbol,thenshiftthepart#_onepositiontotheright.,2020/5/13,70/88,ProofThm.3.8(cont.)ep137,cp95模拟动作,Oninputw=w1wn,theTMMdoesthefollowing:Prepareinitialstring:#w1wn#_#_#_多带复制到单带Readtheunderlinedinputlettersk各带当前字SimulateMbyupdatingtheinputandtheunderliningofthehead-positions.通过下标映射模拟动作Repeat2-3untilMhasreachedahaltingstateHaltaccordingly.,PS:Iftheupdaterequiresoverwritinga#symbol,thenshiftthepart#_onepositiontotheright.,2020/5/13,71/88,ProofThm.3.8(cont.)ep137,cp95模拟动作,Oninputw=w1wn,theTMMdoesthefollowing:Prepareinitialstring:#w1wn#_#_#_多带复制到单带Readtheunderlinedinputlettersk各带当前字SimulateMbyupdatingtheinputandtheunderliningofthehead-positions.通过下标映射模拟动作Repeat2-3untilMhasreachedahaltingstateHaltaccordingly.,PS:Iftheupdaterequiresoverwritinga#symbol,thenshiftthepart#_onepositiontotheright.,2020/5/13,72/88,NondeterministicTMsep138cp94非确定图灵机,AnondeterministicTuringmachineMcanhaveseveraloptionsateverystep.Itisdefinedbythe7-tuple(Q,q0,qaccept,qreject),withQfinitesetofstatesfiniteinputalphabet(without“_”)finitetapealphabetwith_q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction:Qqaccept,qrejectP(QL,R),2020/5/13,73/88,NondeterministicTMsep138cp94非确定图灵机,AnondeterministicTuringmachineMcanhaveseveraloptionsateverystep.Itisdefinedbythe7-tuple(Q,q0,qaccept,qreject),withQfinitesetofstatesfiniteinputalphabet(without“_”)finitetapealphabetwith_q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction:Qqaccept,qrejectP(QL,R),2020/5/13,74/88,NondeterministicTMsep138cp94非确定图灵机,AnondeterministicTuringmachineMcanhaveseveraloptionsateverystep.Itisdefinedbythe7-tuple(Q,q0,qaccept,qreject),withQfinitesetofstatesfiniteinputalphabet(without“_”)finitetapealphabetwith_q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction:Qqaccept,qrejectP(QL,R),转移函数：一格局有多种前途，在格局的幂集中看是单个元素类似于公司，集团,2020/5/13,75/88,NondeterministicTMsep138cp94非确定图灵机,考察一个确定格局演进，用C语言模拟它(q1,b)=(q2,c,R)，M1(Q,char*pCurr)if(Q=q1).考察一个不确定格局演进(q1,b)=(q2,c,R)|(q3,d,L)M3(Q,*pCurr)return(M1(Q,*pCurr)|M2(Q,*pCurr),2020/5/13,76/88,NondeterministicTMsep138cp94非确定图灵机,考察一个确定格局演进，用C语言模拟它(q1,b)=(q2,c,R)，M1(Q,char*pCurr)if(Q=q1)考察一个不确定格局演进(q1,b)=(q2,c,R)|(q3,d,L)M3(Q,*pCurr)if(Q=q1)&(*pCurr=b)return(M1(Q,*pCurr)|M2(Q,*pCurr).,多CPU并行或广度优先的树搜索回溯只要某一分支成功即可,2020/5/13,77/88,NondeterministicTMsep138cp94非确定图灵机,确定图灵机是不确定图灵机的特例。因此，不确定的能模拟确定的图灵机。想要证明不确定TM只不过是方便了用户（比较好制造，接近形象思维，而DTM接近逻辑思维），但能力无本质的提升。即NTM和TM计算能力基本等价，只是速度不同cp89思路：1三带机模拟不确定图灵机多一些存储可模拟不确定性2单带机模拟3带机（前面已经证明）三带机中，第1带保存输入。供多次扫描第2带用于计算第3带模拟不确定过程多个CPU的调度或模拟树搜索与回溯的当前位置，辅助第2带工作。,2020/5/13,78/88,NondeterministicTMsep138cp94非确定图灵机,确定图灵机是不确定图灵机的特例。因此，不确定的能模拟确定的图灵机。想要证明不确定TM只不过是方便了用户（比较好制造，接近形象思维，而DTM接近逻辑思维），但能力无本质的提升。即NTM和TM计算能力基本等价，只是速度不同cp89思路：1三带机模拟不确定图灵机多一些存储可模拟不确定性2单带机模拟3带机（前面已经证明）三带机中，第1带保存输入。供多次扫描(不确定，可后悔）第2带用于计算（模拟一个CPU,一条路线）第3带协调调度，不确定过程多个CPU的调度、树搜索与回溯的当前位置，辅助第2带工作。,2020/5/13,79/88,NondeterministicTMsep138cp94非确定图灵机,三带机中，第1带保存输入。供多次扫描第2带用于计算第3带模拟不确定过程多个CP