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

LectureforComputationTheory

Book:《计算理论导引》IntroductiontotheTheoryofComputationChapter3TuringMachineProf:唐常杰TangChangjie@Http:///~chjtangStudents:Phd,MSinCS.2000--2006,SCUStyle:Lecture/Seminar2021/5/91OutlinefortodaySection3.1—3.2:Computability（补充）3.1TuringmachinesTM-computable/recognizablelanguages3.2VariantsofTMs（多带机，不确定机）2021/5/92

2021/5/93

2021/5/94Intersection&Complement上次例题解法2：IsA={n+2|ninN,ninbinary}aRL?解：={0,1}，*isRL以1开始的二进编码是RL,{1}.*

(即自然数集合N}A={1}.(*

-{0,1,2}},2021/5/95UnionClosureProperties复习上周已讲Lemma:LetA1andA2betwoCFlanguages,

thentheunionA1A2iscontextfreeaswell.Proof:Assumethatthetwogrammarsare

G1=(V1,,R1,S1)andG2=(V2,,R2,S2).

ConstructathirdgrammarG3=(V3,,R3,S3)by:

V3=V1

V2

{S3}(newstartvariable)with

R3=R1R2

{S3S1S2}.

ItfollowsthatL(G3)=L(G1)L(G2).2021/5/96Intersection&Complement?复习：CFL对交运算和补运算不封闭LetagainA1andA2betwoCFlanguages.Onecanprovethat,ingeneral,

theintersectionA1

A2,andthecomplementĀ1=*\A1

arenotCFlanguages.直观解释：PDA资源不够多，，记忆能力不够，不能作复杂集合(如CFL)的减法Oneprovesthiswithspecificexamplesof

languages(seehomework).2021/5/97Intersection&Complement?复习：CFL对交运算和补运算不封闭LetagainA1andA2betwoCFlanguages.Onecanprovethat,ingeneral,

theintersectionA1

A2,andthecomplementĀ1=*\A1

arenotCFlanguages.直观解释：PDA资源不够多，，记忆能力不够，不能作复杂集合(如CFL)的减法Oneprovesthiswithspecificexamplesof

languages(seehomework).2021/5/98Whatdowereallyknow?引出问题CanwealwaysdecideifalanguageLisregular/Context-freeornot?Weknow:

{1x|x=0mod7}isregular（比较规律，可有限描述）

={1111111}*

{1x|xisprime}isnotregular（比较复杂。现在数学家还不能简单描述）Butwhatabout

{1x|xandx+2areprime}?

Thisis(yet)unknown.说明对语言的描述和判定是个需要研究的问题2021/5/99Whatdowereallyknow?引出问题CanwealwaysdecideifalanguageLisregular/

context-freeornot?Weknow:

{1x|x=0mod7}isregular（比较规律，可有限描述）

{1x|xisprime}isnotregular（比较复杂。现在数学家还不能简单描述）Butwhatabout

{1x|xandx+2areprime}?

Thisis(yet)unknown.说明对语言的描述和判定是个需要研究的问题2021/5/910DescribingaLanguageTheproblemliesintheinformalnotionof

adescription.Consider:

{n|n>2,a,b,c:an+bn=cn}费马问题，已解决,是空集

{x|inyearxthefirstfemaleUSpresident}

让历史告诉未来

{x|xis“aneasytoremembernumber”}

描述太含糊Wehavetodefinewhatwemeanby“description”

and“methodofdeciding2021/5/911DescribingaLanguageTheproblemliesintheinformalnotionof

adescription.Consider:

{n|n>2,a,b,c:an+bn=cn}费马问题，已解决,是空集

{x|inyearxthefirstfemaleUSpresident}

让历史告诉未来

{x|xis“aneasytoremembernumber”}

描述太含糊Wehavetodefinewhatwemeanby“description”

and“methodofdeciding”.2021/5/912DescribingaLanguageTheproblemliesintheinformalnotionof

adescription.Consider:

{n|a,b,c:an+bn=cn}费马问题，现已经解决是空集

{x|inyearxthefirstfemaleUSpresident}

让历史告诉未来

{x|xis“aneasytoremembernumber”}

描述太含糊Wehavetodefinewhatwemeanby“description”

and“methodofdeciding”.2021/5/913计算机科学历史上关于概念的争论什么是计算什么是操作系统基本上解决什么internet?什么是数据库什么是数据仓库还在争论什么是数据网格解决方法，给出大众能理解的代表下页2021/5/914计算机科学历史上关于概念的争论解决的办法，给出一个代表什么是3的倍数{3N|N=1,2,3},{x|xmod3=0}

代表元：0什么是操作系统代表元：Windows,Unix什么internet代表元大众理解：Web，IE什么是计算?代表元图灵机2021/5/915计算机科学历史上关于概念的争论解决的办法，给出一个代表什么是3的倍数{3N|N=1,2,3},{x|xmod3=0}

代表元：0什么是操作系统代表元：Windows,Unix什么internet代表元大众理解：Web，IE

什么是计算?代表元图灵机2021/5/916计算机科学历史上关于概念的争论解决的办法，给出一个代表什么是3的倍数{3N|N=1,2,3},{x|xmod3=0}

代表元：0什么是操作系统代表元：Windows,Unix什么internet代表元大众理解：Web，IE

什么是计算?多个模型，代表元；图灵机,或递归函数论2021/5/917Chap3TuringMachines

ep125cp87

在还没有计算机的时候，凭想象力把后来出现的把计算机的理论模型建立起来了。想得如此周到、严密

好像从高度文明的外星来的文化使者2021/5/918Chap3TuringMachines

ep125cp87

AfterAlanM.Turing(1912–1954)In1936,Turingintroducedhis

abstractmodelforcomputationin

hisarticle“OnComputableNumbers,withanapplicationtotheEntscheidungsproblem”.Atthesametime,AlonzoChurchpublished

similarideasandresults.However,theTuringmodelhasbecomethe

standardmodelintheoreticalcomputerscience.2021/5/919Chap3TuringMachines

ep125cp87

AfterAlanM.Turing(1912–1954)In1936,Turingintroducedhis

abstractmodelforcomputationin

hisarticle“OnComputableNumbers,withanapplicationtotheEntscheidungsproblem”.Atthesametime,AlonzoChurchpublished

similarideasandresults.However,theTuringmodelhasbecomethe

standardmodelintheoreticalcomputerscience.2021/5/920Chap3TuringMachines

ep125cp87

AfterAlanM.Turing(1912–1954)In1936,Turingintroducedhis

abstractmodelforcomputationin

hisarticle“OnComputableNumbers,”.Atthesametime,AlonzoChurchpublished

similarideasandresults.殊途同归However,theTuringmodelhasbecomethe

standardmodelintheoreticalcomputerscience.2021/5/921Chap3TuringMachines

复习：关于自动机和下推机中的状态的几种比喻1目标。Goto的目标，标号

2停顿。连续动作离散化的停顿，（直观启示可能来自于手摇计算机，齿轮动作实现，是离散的，一步）思考。新的起点，歇一口气，根据当前输入，思考下一步动作。（自动机不看历史，下推机看一点很短的历史--栈顶值）后面的图灵机中，三者都有2021/5/922InformalDescriptionTMep126cp87根据当前状态和字符xi,决定写移转三动作-写letter,有存储器

-左或右移动转移状态可以作循环语句磁带相当于数组，可读写。这是增加的重要资源internal

statesetQRLAteverystep,

theheadofthe

TMMreadsa

letterxifromthe

one-wayinfinite

tape.读写头在单向无穷带上左右移动并读写，2021/5/923InformalDescriptionTMep126cp87根据当前状态和字符xi,决定写移转三动作-写letter,有存储器

-左或右移动转移状态可以作循环语句磁带相当于数组，可读写。这是增加的重要资源internal

statesetQRLAteverystep,

theheadofthe

TMMreadsa

letterxifromthe

one-wayinfinite

tape.读写头在单向无穷带上左右移动并读写，2021/5/924InformalDescriptionTMep126cp87根据当前状态和字符xi,决定

写移转三动作-写letter,有存储器

-左或右移动转移状态可以作循环语句磁带相当于数组，可读写。这是增加的重要资源internal

statesetQRLAteverystep,

theheadofthe

TMMreadsa

letterxifromthe

one-wayinfinite

tape.读写头在单向无穷带上左右移动并读写，2021/5/925InputConventionep126-128stateq0初始,thetapecontainstheinput

w*,paddedwithblanks“_”,

andtheTMisinstartstateq0.Duringthecomputation,theheadmovesleft

andright(butnotbeyondtheleftmostpoint),

theinternalstateofthemachinechanges,

andthecontentofthetapeisrewritten.数组结构2021/5/926InputConventionep126-128stateq0初始,thetapecontainstheinput

w*,paddedwithblanks“_”,

andtheTMisinstartstateq0.Duringthecomputation,theheadmovesleft

andright(butnotbeyondtheleftmostpoint),

theinternalstateofthemachinechanges,

andthecontentofthetapeisrewritten.数组结构2021/5/927InputConventionep126-128stateq0初始,thetapecontainstheinput

w*,paddedwithblanks“_”,

andtheTMisinstartstateq0.Duringthecomputation,theheadmovesleft

andright(butnotbeyondtheleftmostpoint),

theinternalstateofthemachinechanges,

andthecontentofthetapeisrewritten.数组结构2021/5/928OutputConventionep126-129Thecomputationcanproceedindefinitely,orthe

machinesreachesoneofthetwohaltingstates:三种前途，接受、拒绝、死循环,boolsomeFunc()stateqacceptstateqrejector2021/5/929OutputConventionep126-129Thecomputationcanproceedindefinitely,orthe

machinesreachesoneofthetwohaltingstates:三种前途，接受、拒绝、死循环,boolsomeFunc()stateqacceptstateqrejector2021/5/930TuringMachine(Def.c4.1)ep128cp88元组式定义ATuringmachineMisdefinedbya

7-tuple(Q,,,,q0,qaccept,qreject),with

Qfinitesetofstates状态集合，相当于程序标号

finiteinputalphabet(without“_”)输入字符

finitetapealphabetwith{_}带字符q0startstateQ开始状态qacceptacceptstateQ接受状态qrejectrejectstateQ拒绝状态thetransitionfunction转移函数相当于移动+goto:Q\{qaccept,qreject}Q{L,R}

状态。当前字符转，写，移2021/5/931TuringMachine(Def.c4.1)ep128cp88元组式定义ATuringmachineMisdefinedbya

7-tuple(Q,,,,q0,qaccept,qreject),with

Qfinitesetofstates状态集合，相当于程序标号

finiteinputalphabet(without“_”)输入字符finitetapealphabetwith{_}带字符q0startstateQ开始状态qacceptacceptstateQ接受状态qrejectrejectstateQ拒绝状态(状态相当预程序中标号）

thetransitionfunction转移函数相当于移动+goto:Q\{qaccept,qreject}Q{L,R}

状态。当前字符转，写，移2021/5/932TuringMachine(Def.c4.1)ep128cp88元组式定义ATuringmachineMisdefinedbya

7-tuple(Q,,,,q0,qaccept,qreject),with

Qfinitesetofstates状态集合，相当于程序标号

finiteinputalphabet(without“_”)输入字符finitetapealphabetwith{_}带字符q0startstateQ开始状态qacceptacceptstateQ接受状态qrejectrejectstateQ拒绝状态thetransitionfunction转移函数相当于移动+goto:Q\{qaccept,qreject}Q{L,R}

状态。当前字符转，写，移2021/5/933ConfigurationofaTMep129cp88图稍有不同格局=状态＋已经处理部分＋今后任务，目前形式与任务Theconfiguration

ofaTuringmachineconsistsofthecurrentstateqQthecurrenttapecontents*thecurrentheadlocation{0,1,2,…}Thiscanbeexpressedasanelementof*Q*:q9becomes“101

q9

1_0#1”2021/5/934ConfigurationofaTMep129cp88图稍有不同格局=状态＋已经处理部分＋今后任务，目前形式与任务Theconfiguration

ofaTuringmachineconsistsofthecurrentstateqQthecurrenttapecontents*thecurrentheadlocation{0,1,2,…}Thiscanbeexpressedasanelementof*Q*:q9becomes“101

q9

1_0#1”2021/5/935AnElementaryTMStepep129cp89Letu,v*;a,b,c;qi,qjQ,andMaTM

withtransitionfunction.格局C1产生格局C2Wesaythattheconfiguration“uaqibv”

yields

theconfiguration“uacqjb”ifandonlyif:

(qi,b)=(qj,c,R).格局产生即格局按机演化翻译成格局演进似更恰当Similarly,if(qi,b)=(qj,c,L)//把当前的b改为c且左移

then“uaqibv”yields“uqjacb”

(Attheleftmostsideofthetapedifferent.)2021/5/936AnElementaryTMStepep129cp89Letu,v*;a,b,c;qi,qjQ,andMaTM

withtransitionfunction.格局C1产生格局C2Wesaythattheconfiguration“uaqibv”

yields

theconfiguration“uacqjv”ifandonlyif:

(qi,b)=(qj,c,R).格局产生

即格局按机演化翻译成格局演进似更恰当Similarly,if(qi,b)=(qj,c,L)//把当前的b改为c且左移

then“uaqibv”

yields“uqjacv”

(Attheleftmostsideofthetapedifferent.)2021/5/937Terminology格局startingconfigurationoninputw:“q0w”初始格局acceptingconfiguration:“uqacceptv”接受格局返回truerejectingconfiguration:“uqrejectv”拒绝格局返回falseTheacceptingandrejectingconfigurationsarethehaltingconfigurations.2021/5/938Terminology格局startingconfigurationoninputw:“q0w”初始格局acceptingconfiguration:“uqacceptv”接受格局返回truerejectingconfiguration:“uqrejectv”拒绝格局返回falseTheacceptingandrejectingconfigurationsarethehaltingconfigurations.2021/5/939用格局概念描述Acceptingep129,cp89ATuringmachineMacceptsinputw*

ifandonlyifthereisafinitesequenceof

configurationsC1,C2,…,Ckwith

C1thestartingconfiguration“q0w”foralli=1,…,k–1CiyieldsCi+1(followingM’s)Ckisanacceptingconfiguration“uqacceptv”Thelanguagethatconsistsofallinputsthatare

acceptedbyMisdenotedbyL(M).比喻：boolM(w)最后返回true2021/5/940用格局概念描述Acceptingep129,cp89ATuringmachineMacceptsinputw*

ifandonlyifthereisafinitesequenceof

configurationsC1,C2,…,Ckwith

C1thestartingconfiguration“q0w”foralli=1,…,k–1CiyieldsCi+1(followingM’s)Ckisanacceptingconfiguration“uqacceptv”Thelanguagethatconsistsofallinputsthatare

acceptedbyMisdenotedbyL(M).比喻：boolM(w)最后返回true2021/5/941用格局概念描述Acceptingep129,cp89ATuringmachineMacceptsinputw*

ifandonlyifthereisafinitesequenceof

configurationsC1,C2,…,Ckwith

C1thestartingconfiguration“q0w”foralli=1,…,k–1CiyieldsCi+1(followingM’s)Ckisanacceptingconfiguration“uqacceptv”Thelanguagethatconsistsofallinputsthatare

acceptedbyMisdenotedbyL(M).比喻：boolM(w)最后返回true2021/5/942用格局概念描述Acceptingep129,cp89比喻录取会议论文TuringmachineM录取标准，程序委员会acceptsinputw*字符串，论文，

configurationsC1,C2,…,Ck

评审过程

acceptingconfiguration“uqacceptv”录用uqrejectv”拒绝评审无反响--死机2021/5/943TuringRecognizable(Def.3.2)ep130cp89AlanguageLisTuring-recognizableifandonly

ifthereisaTMMsuchthatL=L(M).图灵可识:对

wL

函数M(w)返回true，对wL，无承诺Note:OnaninputwL,themachineMcan

haltinarejectingstate,oritcan‘loop’indefinitely.Howdoyoudistinguishbetweenaverylong

computationandonethatwillneverhalt?问题：如何区别长计算与死循环？Alsocalled:arecursivelyenumerablelanguage.L又称为递归可枚举语言2021/5/944TuringRecognizable(Def.3.2)ep130cp89AlanguageLisTuring-recognizableifandonly

ifthereisaTMMsuchthatL=L(M).图灵可识:对

wL

函数M(w)返回true，对wL，无承诺Note:OnaninputwL,themachineMcan

haltinarejectingstate,oritcan‘loop’indefinitely.Howdoyoudistinguishbetweenaverylong

computationandonethatwillneverhalt?问题：如何区别长计算与死循环？Alsocalled:arecursivelyenumerablelanguage.L又称为递归可枚举语言2021/5/945TuringRecognizable(Def.3.2)ep130cp89AlanguageLisTuring-recognizableifandonly

ifthereisaTMMsuchthatL=L(M).图灵可识:对

wL

函数M(w)返回true，对wL，无承诺Note:OnaninputwL,themachineMcan

haltinarejectingstate,oritcan‘loop’indefinitely.Howdoyoudistinguishbetweenaverylong

computationandonethatwillneverhalt?问题：如何区别长计算与死循环？Alsocalled:arecursivelyenumerablelanguage.L又称为递归可枚举语言2021/5/946TuringDecidable(Def.3.3)

图灵可判定ep130，cp84Alsocalled:arecursivelanguage.递归语言，比递归可枚举要求高AlanguageL=L(M)isdecidedbytheTMMifon

everyw,theTMfinishesinahaltingconfiguration.

(Thatis:qacceptforwLandqrejectforallwL.)图灵可判定:对

wL

函数M(w)返回true，对wL，返回falseAlanguageLisTuring-decidableifandonly

ifthereisaTMMthatdecidesL.图灵可判定语言

2021/5/947TuringDecidable(Def.3.3)

图灵可判定ep130，cp89Alsocalled:arecursivelanguage.递归语言，比递归可枚举要求高AlanguageL=L(M)isdecidedbytheTMMifon

everyw,theTMfinishesinahaltingconfiguration.

(Thatis:qacceptforwLandqrejectforallwL.)图灵可判定:对

wL

函数M(w)返回true，对wL，返回falseAlanguageLisTuring-decidableifandonly

ifthereisaTMMthatdecidesL.图灵可判定语言

2021/5/948TuringDecidable(Def.3.3)

图灵可判定ep130，cp89Alsocalled:arecursivelanguage.递归语言，比递归可枚举要求高AlanguageL=L(M)isdecidedbytheTMMifon

everyw,theTMfinishesinahaltingconfiguration.

(Thatis:qacceptforwLandqrejectforallwL.)图灵可判定:对

wL

函数M(w)返回true，对wL，返回falseAlanguageLisTuring-decidableifandonly

ifthereisaTMMthatdecidesL.图灵可判定语言

2021/5/949Exa.3.4:判定A={0j|j=2n

，n>=0}ep131，cp90BoolM(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,bygoinglefttorightifthestringhas

evenoroddnumberofzerosIfoddthen“reject”Ifeventhengobackleft,erasinghalfthezerosgoto1算法伪码2021/5/950Exa.3.4:判定A={0j|j=2n}ep131，cp90BoolM(j)//用C语言模拟TM,注意不要超标使用资源{If(j==0)retuenfalse;If(j==1)returntrue;if(jmod2==0)returnM(j-1)//这里有点超前，使用了递归

elseif(j>1)returnfalse;//注意无论j为何值，总有结果

}Checkifj=0orj=1,accept/rejectaccordinglyCheck,bygoinglefttorightifthestringhas

evenoroddnumberofzerosIfoddthen“reject”Ifeventhengobackleft,erasinghalfthezerosgoto1算法伪码2021/5/951Exa.3.4:判定A={0j|j=2n}ep131，cp90BoolM(j)//用C语言模拟TM,注意不要超标使用资源{If(j==0)retuenfalse;If(j==1)returntrue;if(jmod2==0)returnM(j-1)//这里有点超前，使用了递归

elseif(j>1)returnfalse;//注意无论j为何值，总有结果

}Checkifj=0orj=1,accept/rejectaccordinglyCheck,bygoinglefttorightifthestringhas

evenoroddnumberofzerosIfoddthen“reject”Ifeventhengobackleft,erasinghalfthezerosgoto1算法伪码2021/5/952StatediagramsofTMsLikewithPDA,wecanrepresentTuringmachines

by(elaborate)diagrams.SeeFiguresc4.4andc4.5fortwoexamples.见书Ep132,cp85未画出,大家一起读书,建议练习1：把图c4.4改写成为用goto(而不用递归）的C程序练习2:把有递归的程序改为迭代，再转化为图，比较简单，保存中间结果，j-1,以他作输入，重新计算Iftransitionrulesays:qi,b)=(qj,c,R),//读b写c且右移

then:qiqjbc,R2021/5/953StatediagramsofTMsLikewithPDA,wecanrepresentTuringmachines

by(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:qiqjbc,R2021/5/954WhenDescribingTMep133书上的例3.5,3.6,3.7比较细致，有点繁而不难，学生应仔细读一遍。课堂上讲较费时，效果不一定好以后有更高级的方法（例如给出的递归），体会一下低级方法的难处可忆苦思甜。Standardtools:Expandingthealphabetwith

separator“#”,andunderlinedsymbols0,a,toindicate‘activity’.Typical:={0,1,#,_,0,1}2021/5/955WhenDescribingTMep133书上的例3.5,3.6,3.7比较细致，有点繁而不难，学生应仔细读一遍。课堂上讲较费时，效果不一定好以后有更高级的方法（例如给出的递归），体会一下低级方法的难处可忆苦思甜。Standardtools:Expandingthealphabetwith

separator“#”,andunderlinedsymbols0,a,toindicate‘activity’.Typical:={0,1,#,_,0,1}2021/5/956WhenDescribingTMep133略ItisassumedthatyouarefamiliarwithTMsand

withprogrammingcomputers.Clarityaboveall:highleveldescriptionofTMs

isallowedbutshouldnotbeusedasatrickto

hidetheimportantdetailsoftheprogram.Standardtools:Expandingthealphabetwith

separator“#”,andunderlinedsymbols0,a,toindicate‘activity’.Typical:={0,1,#,_,0,1}2021/5/9573.2MultitapeTuringMachines

多带图灵机ep136,cp93增加数组资源，期望编程简单Ak-tapeTuringmachineMhaskdifferent

tapesandread/writeheads.Itisthusdefinedbythe7-tuple(Q,,,,q0,qaccept,qreject),with

Qfinitesetofstates

finiteinputalphabet(without“_”)finitetapealphabetwith{_}q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction

:Q\{qaccept,qreject}kQk{L,R}k转写移根据K条带上的存储数据现状决定写，移，转动作2021/5/9583.2MultitapeTuringMachines

多带图灵机ep136,cp93,增加数组资源，期望编程简单Ak-tapeTuringmachineMhaskdifferent

tapesandread/writeheads.Itisthusdefinedbythe7-tuple(Q,,,,q0,qaccept,qreject),with

Qfinitesetofstates

finiteinputalphabet(without“_”)finitetapealphabetwith{_}

q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction

:Q\{qaccept,qreject}kQk{L,R}k转写移根据K条带上的存储数据现状决定写，移，转动作2021/5/9593.2MultitapeTuringMachines

多带图灵机ep136,cp93,增加数组资源，期望编程简单Ak-tapeTuringmachineMhaskdifferent

tapesandread/writeheads.Itisthusdefinedbythe7-tuple(Q,,,,q0,qaccept,qreject),with

Qfinitesetofstates

finiteinputalphabet(without“_”)finitetapealphabetwith{_}q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction

:Q\{qaccept,qreject}kQk{L,R}k

转写移根据K条带上的存储数据现状决定写，移，转动作2021/5/960k-tapeTMsversus1-tapeTMsep137,cp93Theorem3.8:Foreverymulti-tapeTMM,there

isasingle-tapeTMM’suchthatL(M)=L(M’).Or,foreverymulti-tapeTMM,thereisan

equivalentsingle-tapeTMM’.多带机与单带机等价增加存储和数组(多带)只提速和简化，无本质改变Provingandunderstandingthesekindsofrobustness

results,isessentialforappreciatingthepowerofthe

Turingmachinemodel.称为稳健性FromthistheoremCorollaryc4.9follows:AlanguageLisTM-recognizableifandonlyifsomemulti-tapeTMrecognizesL.以后可用多带机作题，简单多了2021/5/961k-tapeTMsversus1-tapeTMsep137,cp93Theorem3.8:Foreverymulti-tapeTMM,there

isasingle-tapeTMM’suchthatL(M)=L(M’).Or,foreverymulti-tapeTMM,thereisan

equivalentsingle-tapeTMM’.多带机与单带机等价增加存储和数组(多带)只提速和简化，无本质改变Provingandunderstandingthesekindsofrobustness

results,isessentialforappreciatingthepowerofthe

Turingmachinemodel.称为稳健性FromthistheoremCorollaryc4.9follows:AlanguageLisTM-recognizableifandonlyifsomemulti-tapeTMrecognizesL.以后可用多带机作题，简单多了2021/5/962k-tapeTMsversus1-tapeTMsep137,cp88Theorem3.8:Foreverymulti-tapeTMM,there

isasingle-tapeTMM’suchthatL(M)=L(M’).Or,foreverymulti-tapeTMM,thereisan

equivalentsingle-tapeTMM’.多带机与单带机等价增加存储和数组(多带)只提速和简化，无本质改变Provingandunderstandingthesekindsofrobustness

results,isessentialforappreciatingthepowerofthe

Turingmachinemodel.称为稳健性FromthistheoremCorollaryc4.9follows:AlanguageLisTM-recognizableifandonlyifsomemulti-tapeTMrecognizesL.以后可用多带机作题，简单多了2021/5/963OutlineProofThm.3.8ep137,cp95基本思想：用单磁头读4声道录音磁带,读出后复制在一条带上，通过mod(4),和数组下标映射，可以标识原产地，，但能算出4带机的任务。内存少一些，程序复杂一点，慢一点。aei..男声bfj..女生cgk..鼓点dhl..配乐2021/5/964OutlineProofThm.3.8ep137,cp95另一种比喻：先写一个有4个数组的C程序,然后写一个只有一个数组的程序去模拟上述程序，直观上是容易接受的，因为用下标映射实现模拟的难度不大。

注意，现在下标需要顺序扫描，以后可证明可按下标随机存取图灵机（随机图灵机）写论文时从来不限制只能用低级图灵机证明问题，可以用最先进的工具。注意力集中在后面将要讨论的复杂度，P、NP问题，不必拘泥与这些技术细节2021/5/965OutlineProofThm.3.8ep137,cp95另一种比喻：先写一个有4个数组的C程序,然后写一个只有一个数组的程序区模拟上述程序，直观上是容易接受的，因为用下标映射实现模拟的难度不大。注意，现在下标需要顺序扫描，以后可证明可按下标随机存取图灵机（随机图灵机）写论文时从来不限制只能用低级图灵机证明问题，可以用最先进的工具。

注意力集中在后面将要讨论的复杂度，P、NP问题，不必拘泥与这些技术细节2021/5/966OutlineProofThm.3.8ep137,cp95

模拟结构造单带机模拟多带机（多带机模拟单带机不需证明）LetM=(Q,,,,q0,qaccept,qreject)beak-tapeTM.Construct1-tapeM’withexpanded’={#}RepresentM-configuration

u1qja1v1,u2qja2v2,…,

ukqjakvk

byM’configuration,

qj#u1a1v1#u2a2v2#…#ukakvk

分带符#,K道上当前字符第1道第k道格局2021/5/967OutlineProofThm.3.8ep137,cp95

模拟结构造单带机模拟多带机（多带机模拟单带机不需证明）LetM=(Q,,,,q0,qaccept,qreject)beak-tapeTM.Construct1-tapeM’withexpanded’={#}RepresentM-configuration

u1qja1v1,u2qja2v2,…,

ukqjakvk

byM’configuration,

qj#u1a1v1#u2a2v2#…#ukakvk

分带符#,K道上当前字符第1道第k道格局2021/5/968ProofThm.3.8(cont.)ep137,cp95模拟动作Oninputw=w1…wn,theTMM’doesthefollowing:Prepareinitialstring:#w1…wn#_##_#_

多带复制到单带Readtheunderlinedinputlettersk各带当前字SimulateMbyupdatingtheinputandthe

underliningofthehead-positions.

通过下标映射模拟动作Repeat2-3untilMhasreachedahaltingstateHaltaccordingly.PS:Iftheupdaterequiresoverwritinga#symbol,

thenshiftthepart#_onepositiontotheright.2021/5/969ProofThm.3.8(cont.)ep137,cp95模拟动作Oninputw=w1…wn,theTMM’doesthefollowing:Prepareinitialstring:#w1…wn#_##_#_

多带复制到单带Readtheunderlinedinputlettersk各带当前字SimulateMbyupdatingtheinputandthe

underliningofthehead-positions.

通过下标映射模拟动作Repeat2-3untilMhasreachedahaltingstateHaltaccordingly.PS:Iftheupdaterequiresoverwritinga#symbol,

thenshiftthepart#_onepositiontotheright.2021/5/970ProofThm.3.8(cont.)ep137,cp95模拟动作Oninputw=w1…wn,theTMM’doesthefollowing:Prepareinitialstring:#w1…wn#_##_#_

多带复制到单带Readtheunderlinedinputlettersk各带当前字SimulateMbyupdatingtheinputandthe

underliningofthehead-positions.

通过下标映射模拟动作Repeat2-3untilMhasreachedahaltingstateHaltaccordingly.PS:Iftheupdaterequiresoverwritinga#symbol,

thenshiftthepart#_onepositiontotheright.2021/5/971NondeterministicTMsep138cp94非确定图灵机AnondeterministicTuringmachineMcanhave

severaloptionsateverystep.Itisdefinedbythe7-tuple(Q,,,,q0,qaccept,qreject),with

Qfinitesetofstates

finiteinputalphabet(without“_”)finitetapealphabetwith{_}q0startstateQqacceptacceptstateQqrejectrejectstateQthetransitionfunction

:Q\{qaccept,qreject}P(Q{L,R})2021/5/972NondeterministicTMsep138cp94非确定图灵机AnondeterministicTuringmachineMcanhave

severaloptionsateverystep.Itisdefinedbythe7-tuple(Q,,,,q0,qaccept,qreject),withQfinitesetofstates

finiteinputalph