計(jì)算理論09-遞歸哥德爾

PartII:ComputabilityTheory計(jì)算理論引論

byMichaelSipserChapter7:RecursionTheoremDr.WeibingFengwbfeng@1今天課程

ChapterC7:C7.1PotentialProblemswith

InfiniteRecursion

Recursiontheorem遞歸可行性

UndecidabilitybySelf-Reference自引用G?del’sIncompletenessTheorem哥德爾不完全定理2復(fù)習(xí)UndecidabilityThusFarcp130Undecidability–thusfar–usedtheundecidability

oftheacceptproblemATM.我們已經(jīng)充分使用了接受問題的不可判定性WeprovedtheundecidabilityofATMbymakingexplicittheself-referenceparadox:

采用了自引用集合

S={<M>|TMsMthatdonotaccept<M>}

技巧在于（直觀解釋）讓程序處理自己的源程序：

LetPbeaTMthatrecognizesS,then

“Pon<P>”leadstoacontradiction.Crucialingredient:關(guān)鍵技術(shù)

Self-Reference:Paccepts<P>.3復(fù)習(xí)UndecidabilityThusFarcp130Undecidability–thusfar–usedtheundecidability

oftheacceptproblemATM.我們已經(jīng)充分使用了接受問題的不可判定性WeprovedtheundecidabilityofATMbymakingexplicittheself-referenceparadox:采用了自引用集合

S={<M>|TMsMthatdonotaccept<M>}

技巧在于（直觀解釋）讓程序分析自己的源程序：

LetPbeaTMthatrecognizesS,then

“Pon<P>”leadstoacontradiction.Crucialingredient:關(guān)鍵技術(shù)

Self-Reference:Paccepts<P>.4Self-Referenceep198,cp130WhathappensifacomputerprogramMtriesto

answerquestionsaboutitself<M>?程序自己分析自己的源程序會(huì)出什么結(jié)果？Sometimesthisisperfectlyokay:

-Howbigis<M>?

-Is<M>aproperTM?Otherquestionsleadtoparadoxes:有時(shí)似是而非-Does<M>haltornot?如停機(jī)-IsthereasmallerprogramM’thatisequivalent?5Self-Referenceep198,cp130WhathappensifacomputerprogramMtriesto

answerquestionsaboutitself<M>?程序自己分析自己的源程序會(huì)出什么結(jié)果？Sometimesthisisperfectlyokay:

-Howbigis<M>?

-Is<M>aproperTM?Otherquestionsleadtoparadoxes:有時(shí)似是而非-Does<M>haltornot?如停機(jī)-IsthereasmallerprogramM’thatisequivalent?6Self-Referenceep198,cp130WhathappensifacomputerprogramMtriesto

answerquestionsaboutitself<M>?程序自己分析自己的源程序會(huì)出什么結(jié)果？Sometimesthisisperfectlyokay:

-Howbigis<M>?

-Is<M>aproperTM?Otherquestionsleadto

paradoxes:有時(shí)似是而非-Does<M>haltornot?如停機(jī)-IsthereasmallerprogramM’thatisequivalent?7AvoidingParadoxes?ep199paradox是錯(cuò)誤理解的問題。Maybe自引用的悖論原源自TM不能考慮自己isnotabletoconsideritself?

Question:Howisitpossibletohavethestructure:1)Bla-bla-bla;2)LookatM=;3)MoreBla-bla-bla;4)DosomethingweirdM=Howcanwehave

thecomplete

descriptionofM

insideMitself?1)Bla-bla-bla;2)LookatM=;3)MoreBla-bla-bla;4)DosomethingweirdM=1)Bla-bla-bla;2)LookatM=;3)MoreBla-bla-bla;4)DosomethingweirdM=8AvoidingParadoxes?Ep199

遞歸Aparadoxisamisunderstoodproblem.

Maybetheparadoxesofself-referencesoccur

becauseaTMisnotabletoconsideritself?Question:Howisitpossibletohavethestructure:1)Bla-bla-bla;2)LookatM=;3)MoreBla-bla-bla;4)DosomethingweirdM=Howcanwehave

thecomplete

descriptionofM

insideMitself?1)Bla-bla-bla;2)LookatM=;3)MoreBla-bla-bla;4)DosomethingweirdM=1)Bla-bla-bla;（平凡）2)LookatM=;3)MoreBla-bla-bla;4)Dosomethingweird(奇怪動(dòng)作）M=在這里調(diào)用自己9遞歸從前有個(gè)廟，廟里有個(gè)老和尚，老和尚給小和尚講故事,講的故事是：”從前有各廟，廟里有個(gè)老和尚，老和尚給小和尚將故事,講的什么故事是……”Voidstory(){printf(“從前有個(gè)廟，廟里有個(gè)老和尚，老和尚給小和尚講故事,講的故事是：”)；story();}毛病，沒有遞歸深度控制，棧溢出時(shí)死機(jī)鏡子里面照鏡子，電影里面放電影，故事里面講故事更新奇的是：10遞歸從前有個(gè)廟，廟里有個(gè)老和尚，老和尚給小和尚講故事,講的故事是：”從前有各廟，廟里有個(gè)老和尚，老和尚給小和尚將故事,講的什么故事是……”Voidstory(){printf(“從前有個(gè)廟，廟里有個(gè)老和尚，老和尚給小和尚講故事,講的故事是：”)；story();}毛病，沒有遞歸深度控制，棧溢出時(shí)死機(jī)鏡子里面照鏡子，電影里面放電影，故事里面講故事更新奇的是：11遞歸從前有個(gè)廟，廟里有個(gè)老和尚，老和尚給小和尚講故事,講的故事是：”從前有各廟，廟里有個(gè)老和尚，老和尚給小和尚將故事,講的什么故事是……”Voidstory(){printf(“從前有個(gè)廟，廟里有個(gè)老和尚，老和尚給小和尚講故事,講的故事是：”)；story();}毛病，沒有遞歸深度控制，棧溢出時(shí)死機(jī)鏡子里面照鏡子，電影里面放電影，故事里面講故事,莊生夢(mèng)蝶，更新奇的是：12The‘DrosteEffect’

Itseemsimpossibleto

haveafiniteobjectthat,

asapart,hasacomplete

descriptionofitself.Youexpectaconflict

betweenthefiniteamount

ofinformation-spaceand

theinfiniterecursion.

注意這里遞歸另例小學(xué)一年級(jí)語(yǔ)文數(shù)封面13The‘DrosteEffect’

Itseemsimpossibleto

haveafiniteobjectthat,

asapart,hasacomplete

descriptionofitself.Youexpectaconflict

betweenthefiniteamount

ofinformation-spaceand

theinfiniterecursion.

注意這里遞歸另例小學(xué)一年級(jí)語(yǔ)文數(shù)封面14InfiniteRecursioninMath<ep200Ontheotherhand,

weknowofmany

(mathematical)

objectsthathavea

finitedescription,

yetappeartobe

infinitelydetailed…分形數(shù)學(xué)15MPrintingM打印自己源程序

ep200cp130問題：自己調(diào)用自己的TM是否合法的圖靈機(jī)

自己調(diào)用自己的程序是否合法的程序？本節(jié)要向證明，

滿足一定規(guī)范非自己調(diào)用是合法的，從數(shù)學(xué)本質(zhì)上看，是正確的，不是詭辯，不是悖論而且用途廣泛.16MPrintingM打印自己源程序

ep200cp130Attempttodescribeaprogramthatprintsitself:

M=print(“print(“print(“print…TheDrosteeffectforcesMtobeinfinite.打印下面語(yǔ)句兩個(gè)副本，第二次加引號(hào)：considerthefollowinghigh-levelprogram:print_twice_2nd_time_with_(“_“):

(“print_twice_2nd_time_with_(“_“):”)

…SoitispossibletohavesuchaTMM.

TheRecursionTheoremmakesthisexplicit.17MPrintingM打印自己源程序

ep200cp130錯(cuò)誤方法：Attempttodescribeaprogramthatprintsitself:

M=print(“print(“print(“print…TheDrosteeffectforcesMtobeinfinite.正確方法打印下面語(yǔ)句兩個(gè)副本，第二次加引號(hào)：considerthefollowinghigh-levelprogram:print_twice_2nd_time_with_(“_“):

(“print_twice_2nd_time_with_(“_“):”)

…SoitispossibletohavesuchaTMM.

TheRecursionTheoremmakesthisexplicit.18TheRecursionTheorem

為定理C7.2（遞歸的可行性）作準(zhǔn)備

ep200,cp131TherecursiontheoreminCSshowshowwecan

dealwiththeDroste/self-referenceeffectforTMs.遞歸的可行性ThekeyideaistosplittheTMintotwoparts:

1)astringthatdescribes2ndpartofprogram

獲得描述自己的串（稍難）2)aprogramthatprintsthestring‘smart’打印指定的串（不難）Howtoconstructaprogram<SELF>that

printsitself…且看下面細(xì)細(xì)道來19TheRecursionTheorem

為定理C7.2（遞歸的可行性）作準(zhǔn)備

ep200,cp131TherecursiontheoreminCSshowshowwecan

dealwiththeDroste/self-referenceeffectforTMs.遞歸的可行性ThekeyideaistosplittheTMintotwoparts:

1)astringthatdescribes2ndpartofprogram

獲得描述第二部分串（稍難）2)aprogramthatprintsthestring‘smart’

打印指定的串（不難）Howtoconstructaprogram<SELF>that

printsitself…且看下面細(xì)細(xì)道來20ASimpleLemmacp130LemmaC7.1

:Letwbeaninputstring,andletPw

beaTMthatprintsw.

Thefunctionq(w)=<Pw>isTMcomputable.打印指定串的程序的源程序是可以用程序產(chǎn)生的

證明程序Pw(x){x[0]=0;printf(w);}//總是打印外部串Wq:Σ*Σ*,使得

q(w)=“Pw(x){x[0]=0;printf(w);}”

造計(jì)算q的TMQ(C程序)如下：Q(w){char*p=q(w);//函數(shù)值是一個(gè)源程序串的指針printf(p);}}下頁(yè)是書上的證明21ASimpleLemmacp130LemmaC7.1

:Letwbeaninputstring,andletPw

beaTMthatprintsw.

Thefunctionq(w)=<Pw>isTMcomputable.打印指定串的程序的源程序是可以用程序產(chǎn)生的

證明程序

Pw(x){x[0]=0;printf(w);}//總是打印外部串W

q:Σ*Σ*,使得

q(w)=“Pw(x){x[0]=0;printf(w);}”

造計(jì)算q的TMQ(C程序)如下：Q(w){char*p=q(w);//函數(shù)值是一個(gè)源程序串的指針printf(p);}}下頁(yè)是書上的證明22ASimpleLemma，cp130書上的證明LemmaC7.1

:Letwbeaninputstring,andletPw

beaTMthatprintsw.

Thefunctionq(w)=<Pw>isTMcomputable.打印指定串的程序的源程序是可以用程序產(chǎn)生的Proof:ConsidertheTM(oninputw):

1)ConstructTMPw: 1)eraseinput 2)writewandhalt2)Output<Pw>23利用引理，造一個(gè)能打印自己源程序的程序

TheProgram<SELF>=<AB>ep201cp130用C語(yǔ)言描述

庫(kù)函數(shù)B(<M>){Get_source_as(<M>,P<M>)；//反編譯printf(“%s%s”,P<M>,<M>);}main(charargv[],intargc)//輸入w為argv[1]=w{char*A=<B>;//B的源程序,如用argv[0]即EXE名,復(fù)制串B(<A>);}下頁(yè)是書上的證明輸入TM,輸出：源程序串24利用引理，造打印自己源程序的程序

TheProgram<SELF>=<AB>ep201cp130TheSELF-programconsistsoftwopartsAandB:Firstpart:A=P<B>,sowewillwaitwiththisone…Bpart(oninput<M>withMaTMsubroutine):

1)Read<M>,compute<P<M>>%seeLemma6.1

2)Use<M>and<P<M>>toprint<P<M>M>NowweknowwhatP<B>lookslike.25WorkingofSELF:ep201P<1)Given…2)…M>>1)Given<M>,compute<P<M>>//反編譯2)Use<M>and<P<M>>toprint<P<M>M>AfterA-partonthetape:1)Given<M>...M>B1readsinputontape,computes<P<1)Given...M>>>B2prints:

P<1)Given…M>>1)Given...M>A=

B1=

B2=B1,B2的串26RecursionTheoremep200Insteadofprinting,aTMcandoanythingelse

withitsowndescription.可以把打印(printf)改成其他任何處理，如加密，例如下面的t可以是個(gè)串加密函數(shù)RecursionTheorem(6.2):Lett:***bea

TM-computablefunction.ThereisaTuring

machineRthatcomputesthefunctionr:**

withr(w)=t(<R>,w)foreveryw*.(InthecaseofSELF,wehadt(x,y)=x.)27RecursionTheoremep200Insteadofprinting,aTMcandoanythingelse

withitsowndescription.可以把打印(printf)改成其他任何處理，如加密，例如下面的t可以是個(gè)串加密函數(shù)RecursionTheorem(6.2):Lett:***bea

TM-computablefunction.ThereisaTuring

machineRthatcomputesthefunctionr:**

withr(w)=t(<R>,w)foreveryw*.(InthecaseofSELF,wehadt(x,y)=x.)28RecursionTheoremep200,cp131RecursionTheorem(C7.2):Lett:***beaTM-computablefunction.ThereisaTuringmachineRthatcomputesthefunctionr:**withr(w)=t(<R>,w)foreveryw*.C描述的證明:已經(jīng)有了程序T(w){加密..}，現(xiàn)在如下造程序R:R(w){char*s=<R>;//R自己的源程序或代碼，前面已經(jīng)證明可得

s=s+w;//或用strcatT(S);}意義：R把自己的源程序作為處理的首部，當(dāng)w=NULL時(shí)，R自己處理自己（注意由于T是任何程序，例如是加密程序，則R把自己加密）下頁(yè)是書上的證明29RecursionTheoremep200,cp131RecursionTheorem(C7.2):Lett:***beaTM-computablefunction.ThereisaTuringmachineRthatcomputesthefunctionr:**withr(w)=t(<R>,w)foreveryw*.C描述的證明:已經(jīng)有了程序T(w){加密..}，現(xiàn)在如下造程序R:R(w){char*s=<R>;//R自己的源程序或代碼，前面已經(jīng)證明可得

s=s+w;//或用strcatT(S);}意義：R把自己的源程序作為處理的首部，當(dāng)w=NULL時(shí)，R自己處理自己（注意由于T是任何程序，例如是加密程序，則R把自己加密）下頁(yè)是書上的證明30RecursionTheoremep200,cp131RecursionTheorem(C7.2):Lett:***beaTM-computablefunction.ThereisaTuringmachineRthatcomputesthefunctionr:**withr(w)=t(<R>,w)foreveryw*.C描述的證明:已經(jīng)有了程序T(w){加密..}，現(xiàn)在如下造程序R:R(w){char*s=<R>;//R自己的源程序或代碼，前面已經(jīng)證明可得

s=s+w;//或用strcatT(S);}意義：R把自己的源程序作為處理的首部，當(dāng)w=NULL時(shí)，R自己處理自己（注意由于T是任何程序，例如是加密程序，則R把自己加密）下頁(yè)是書上的證明31ProofRecursionTheorem6.2

ep200cp131書上的證明，稍難理解Lett:***beaTM-computablefunction.

ThereisaTMRthatcomputesthefunction

r(w)=t(<R>,w)foreveryw*.Proof:LetTbetheTMthatcomputest.

TheTMRconsistsof3parts:A,B,T(inputw):

A=P<BT>B=Readinput<M>,print<P<M>M>

T=Calculateton(tapecontent,w).32ApplicationRecursionThmcp131-132Therecursiontheoremmakesitclearthatself-

referenceispossibleforTMs:TM可自己調(diào)自己

ispossible.ItshowsthatprogramslikeSELFarepossible.

Makesundecidabilityproofsmoretransparent

astheycannowbephrasedforasingleTM.1)Bla-bla-bla;平凡簡(jiǎn)單2)Lookat<M>;3)MoreBla-bla-bla;M=33ATMisUndecidable用新式武器來證明舊問題

定理6.3ep202Proofbycontradiction:用C語(yǔ)言描述

設(shè)boolDeter_Accept(M,w)是接受判定程序，造TMB(w)如下：boolB(w){printf(<B>);//打印自己的源程序

OK=!Deter_Accept(B,W);//遞歸returnOK}//如果B接受w,OK=false,則B不接受w,下頁(yè)是書上的證明TheoremC7.3:Theacceptancelanguage

ATM={<M,w>|TMMacceptsinputw}

isundecidable.接受問題是不可判定的34ATMisUndecidable用新式武器來證明舊問題

定理6.3ep202Proofbycontradiction:用C語(yǔ)言描述

設(shè)boolDeter_Accept(M,w)是接受判定程序，造TMB(w)如下：boolB(w)//Deter_Accept(B,W）{printf(<B>);//打印自己的源程序

OK=!Deter_Accept(B,W);//遞歸returnOK}//如果B接受w,OK=false,則B不接受w,矛盾下頁(yè)是書上的證明TheoremC7.3:Theacceptancelanguage

ATM={<M,w>|TMMacceptsinputw}

isundecidable.接受問題是不可判定的Deter_Accept(M,x)對(duì)任何M,x都能判定，對(duì)特殊的M=B,x=w當(dāng)然也能35ATMisUndecidable用新式武器來證明舊問題

定理6.3ep202Proofbycontradiction:書上的證明

AssumethatHdecidesATM.ConstructthefollowingTMB(inputw):

1)Printowndescription<B>

2)RunHoninput<B,w>

3)NegateanswerofHTheoremC7.3:Theacceptancelanguage

ATM={<M,w>|TMMacceptsinputw}

isundecidable.接受問題是不可判定的TheanswerofHon<B,w>andthereply

ofBon<w>willdisagree.Contradiction.36上述方法的竅門ThepreviousproofgivesaTM-computable

counterexampleforeveryHattempt.用自調(diào)用＋否定導(dǎo)出矛盾ForeveryTMHthatclaimstodecideATM,

constructthefollowingTMB(inputw):

1)Printowndescription<B>2)RunHoninput<B,w>3)NegateanswerofHItdoesn’trequireahumantocomeupwith

acounterexampleforH…37定理C7.5cp132MINTM={<M>|M是極小TM,等價(jià)TM中最短}定理C7.5MINTM不可判定自學(xué)。38C7.2MathematicalTheories

ep204，cp133計(jì)劃自學(xué)內(nèi)容，略講Thetheoryof(un)decidabilityhelpsusto

understandthelimitationsoflogicaltheories.不可判定問題表明邏輯的局限性Considersomestatementsaboutthenatural

numbersN={0,1,2,…}:qpx,y[p>q&(x,y>1xyp)]因子分解a,b,c,n[(a,b,c>0&an+bn=cn)n2]費(fèi)馬定理qpx,y[p>q&(x,y>1(xyp&xyp+2))]Wewanttoprovestatementslikethese.39C7.2MathematicalTheories

ep204，cp133計(jì)劃自學(xué)內(nèi)容，略講Thetheoryof(un)decidabilityhelpsusto

understandthelimitationsoflogicaltheories.不可判定問題表明邏輯的局限性Considersomestatementsaboutthenatural

numbersN={0,1,2,…}:qpx,y[p>q&(x,y>1xyp)]因子分解a,b,c,n[(a,b,c>0&an+bn=cn)n2]費(fèi)馬定理qpx,y[p>q&(x,y>1(xyp&xyp+2))]Wewanttoprovestatementslikethese.40IncompletenessTheorem哥德爾不完全定理KurtG?del41IncompletenessTheorem哥德爾不完全定理In1931,KurtG?delpublishedhis“überformalunentscheidbareS?tzederPrincipiaMathematicaundverwandterSystemeI”,inwhichheprovedthatformalmathematicalsystemshaveonlylimitedpower.數(shù)學(xué)公理系統(tǒng)的局限性Notethatthisresult先于ofTuringand

thesolutionofHilbert’spolynomialproblem.Wewillneverbeabletohaveasystemthatcan

provealltruestatementsabout{0,1,2,…},+,.42數(shù)學(xué)哲學(xué)學(xué)派補(bǔ)充

1柏拉圖主義，哥德爾等數(shù)學(xué)真理是客觀的外在的，不依賴于數(shù)學(xué)家，唯物2直覺主義，拒絕完成先概念，否定排中律，要求構(gòu)造選證明（機(jī)械唯物）3形式主義公理定理一切真理，希爾波特，布爾巴基。Turing研究了康托、哥德爾成果，提出了停機(jī)問題43數(shù)學(xué)哲學(xué)學(xué)派補(bǔ)充

歷史上是先有哥德爾定理，后有停機(jī)問題不可判定反過來用停機(jī)問題不可判定也可以證明哥德爾定理證明：每一個(gè)算術(shù)命題編碼稱為有限串，所有的問題可列。對(duì)TMM輸入W的停機(jī)問題是一個(gè)算術(shù)命題，也列在其中如果不存在不可判定命題，則停機(jī)問題可判定，矛盾。44數(shù)學(xué)哲學(xué)學(xué)派補(bǔ)充

理論與模型（model，模特）含有變量的

命題T(x1,x2,…Xn)在集合A={(a1,a2,an),b1,b2,…bn),…}上成立。則稱A為T的模型。例子：T=信息技術(shù)是現(xiàn)代戰(zhàn)爭(zhēng)重要戰(zhàn)力。

A={海灣戰(zhàn)爭(zhēng)，伊拉克戰(zhàn)爭(zhēng)，….}45ModelTheory集合＋運(yùn)算

模型論ep205,cpConsiderthe‘model’fornaturalnumberswith

additionandmultiplication(N,+,).

Wewanttoknowwhichstatementsaboutthis

modelaretrueandwhicharefalse.想分辨命題的真假The‘theory’Th(N,+,)isthesetofalltrue

statementsabout/expressedin(N,+,).真命題稱為定理

Amathematicaltheorytriestodescribethis

Th(N,+,)withaxiomsandderivationrules.公理系統(tǒng)描述定理的推理46ModelTheory集合＋運(yùn)算

模型論ep205,cpConsiderthe‘model’fornaturalnumberswith

additionandmultiplication(N,+,).

Wewanttoknowwhichstatementsaboutthis

modelaretrueandwhicharefalse.想分辨命題的真假The‘theory’Th(N,+,)isthesetofalltrue

statementsabout/expressedin(N,+,).真命題稱為定理

Amathematicaltheorytriestodescribethis

Th(N,+,)withaxiomsandderivationrules.公理系統(tǒng)描述定理的推理47公理系統(tǒng)基本概念公理是可靠的sound：推出的都正確公理是完全的complete：正確都能被推出

推不出的都不正確（如證關(guān)系數(shù)據(jù)庫(kù)的armstrong公理）公理是不完全的

：有正確的命題，不能被推出存在命題A,A和~A都不能被證明

(A和～A中必有一真）所以不完全系統(tǒng)中一定有不可判定問題。公理是不完全的，可能是公理個(gè)數(shù)太少公理是不可靠，可能是公理太多，有互相矛盾的48公理系統(tǒng)基本概念公理是可靠的sound：推出的都正確公理是完全的complete：正確都能被推出

推不出的都不正確（如證關(guān)系數(shù)據(jù)庫(kù)的armstrong公理）公理是不完全的

：有正確的命題，不能被推出存在命題A,A和~A都不能被證明

(A和～A中必有一真）所以不完全系統(tǒng)中一定有不可判定問題。公理是不完全的，可能是公理個(gè)數(shù)太少公理是不可靠，可能是公理太多，有互相矛盾的49公理系統(tǒng)基本概念公理是可靠的sound：推出的都正確公理是完全的complete：正確都能被推出

推不出的都不正確（如證關(guān)系數(shù)據(jù)庫(kù)的armstrong公理）公理是不完全的

：有正確的命題，不能被推出存在命題A,A和~A都不能被證明

(A和～A中必有一真）所以不完全系統(tǒng)中一定有不可判定問題。公理是不完全的，可能是公理個(gè)數(shù)太少公理是不可靠，可能是公理太多，有互相矛盾的50G?del’sIncompletenessThm

ep207,cp135哥德爾不完全定理Ultimately,amathematicianwantstohaveaTM

thatdecideslanguageslike

T={s|sTh(N,+,)}.可判定

但有一些稍微復(fù)雜的系統(tǒng)不可判定Somespecificexamples:

Th(N,+)isaTM-decidableset可識(shí)別定理C7.10Th(N,+,)isanotaTM-recognizableset不可識(shí)別Th(R,+,)isTM-decidable可識(shí)別51G?del’sIncompletenessThm

ep207,cp135哥德爾不完全定理Ultimately,amathematicianwantstohaveaTM

thatdecideslanguageslike

T={s|sTh(N,+,)}.可判定

但有一些稍微復(fù)雜的系統(tǒng)不可判定Somespecificexamples:

Th(N,+)isaTM-decidableset可判定定理C7.10Th(N,+,)isanotaTM-recognizableset不可判定Th(R,+,)isTM-decidable可判定52Whatdoesthismean?Ep206WecantrytoformalizethetheoryofTh(N,+,)

withaxiomsandderivationrules.

Withsuchanaxiomatizationwecanmakean

enumeratingTMthatspitsoutprovenstatements

aboutTh(N,+,).G?del’sincompleteness

說明在不太復(fù)雜的公理系統(tǒng)Th(N,+,)中有正確的但不能被證明的命題，說明公理系統(tǒng)的描述能力有限53CompletenessforTh(N,+)定理C7.10

ep207cp135

作為討論題目，誰(shuí)來自告奮勇？ThesetoftruestatementsTh(N,+)isdecidable.自然數(shù)和加法的系統(tǒng)是可判定的Theproofofthisresultscanbedonewithour

knowledgeoffiniteautomata:有限自動(dòng)機(jī)可作加法體系結(jié)構(gòu)課程中的加法器是DFA(bit加和進(jìn)位機(jī)制）-Regularlanguagesareclosedunder,,and&.-Problem1.25:{(a1,…,an,b)|a1+…+an=b}isaRL.Wecandescribethevalidityofstatementslike

withafiniteautomatonforinputs(x1,x2).54ExampleforTh(N,+)ep207Considerapotentialelementofthetheory,likeFirst,wemakeafiniteautomatonfortheRL

{(x1,x2,x3)|x1+x2=x1+x3}Next,weusethisautomatontobuildanon-

deterministiconefor{(x1,x2)|x3x1+x2=x1+x3}Samefor{(x1)|x2x3x1+x2=x1+x3}…Finally,wewillhavethelanguage{()}ifistrue,

ortheemptylanguageifisfalse.55ProofIncompletenessThmC7.14cp137

用圖靈機(jī)來證明哥德爾不完全定理的證明思路要點(diǎn):

反設(shè)存在TMM，它能識(shí)別Th(N,+,)中的正確命題(即正確的都能被證明），給一個(gè)語(yǔ)句

,與

中必有一真。并行地調(diào)度并運(yùn)行M()和M()。只要其中之一接受，就停止并接受那個(gè)語(yǔ)句。所以M能判定

Th(N,+,).給出M的描述<M>,考慮下列語(yǔ)句“Mwillrejectthisstatement”.利用計(jì)算歷史,等價(jià)于

M=(rejectingcomputinghistoryofMonM)接下頁(yè)56ProofIncompletenessThmC7.14cp137

用圖靈機(jī)來證明哥德爾不完全定理的證明思路要點(diǎn):

反設(shè)存在TMM，它能識(shí)別Th(N,+,)中的正確命題(即正確的都能被證明），給一個(gè)語(yǔ)句

,與

中必有一真。并行地調(diào)度并運(yùn)行M()和M()。只要其中之一接受，就停止并接受那個(gè)語(yǔ)句。所以M能判定

Th(N,+,).給出M的描述<M>,考慮下列語(yǔ)句“Mwillrejectthisstatement”.利用計(jì)算歷史,等價(jià)于

M=(rejectingcomputinghistoryofMonM)接下頁(yè)57ProofIncompletenessThm(2)把M=(rejectingcomputinghistoryofMonM)

形式化表達(dá)為

M=C[REJECT(M,M)(C)]利用遞歸定理和一些技巧

（somesmarttricks）

用Th(N,+,)的術(shù)語(yǔ)表達(dá)函數(shù)

REJECT(M,M)，則M=C[REJECT(M,M)(C)]也是系統(tǒng)

Th(N,+,)中的一個(gè)語(yǔ)句.

如果MTh(N,+,)(“istrue”)則M拒絕

M;

如果MTh(N,+,),則

Mistrue，andMdoes

notrejectM.與M的構(gòu)造定義矛盾

與前幾周證明的類似，這次更細(xì)致一些，58ProofIncompletenessThm(2)把M=(rejectingcomputinghistoryofMonM)

形式化表達(dá)為

M=C[REJECT(M,M)(C)]利用遞歸定理和一些技巧

（somesmarttricks）

用Th(N,+,)的術(shù)語(yǔ)表達(dá)函數(shù)

REJECT(M,M)，則M=C[REJECT(M,M)(C)]也是系統(tǒng)

Th(N,+,)中的一個(gè)語(yǔ)句.

如果MTh(N,+,)(“istrue”)則M拒絕

M;

如果MTh(N,+,),則

Mistrue，andMdoes

notrejectM.與M的構(gòu)造定義矛盾

與前幾周證明的類似，這次更細(xì)致一些，59TheConsequences?cp137ForanyaxiomaticdescriptionDofTh(N,+,),

wecanmakeastatementDthatwecannot

provewithD.WecanexpandtheDwithDorwithD.Cf.Euclideanandnon-Euclidean

geometry:歐氏集合與非歐幾何

“Thesumoftheanglesofatriangle

isequaltotworightangles.”60TheConsequences?cp13761ExpandingtheTMModel

oracle

喻示,請(qǐng)圣賢幫忙，請(qǐng)專家顧問幫忙Justasanymathematicaltheory,wecanexpand

ourTuringmachinemodelfo