計算理論09-遞歸哥德爾

PartII:ComputabilityTheory計算理論引論

byMichaelSipserChapter7:RecursionTheoremDr.WeibingFengwbfeng@1今天課程

ChapterC7:C7.1PotentialProblemswith

InfiniteRecursion

Recursiontheorem遞歸可行性

UndecidabilitybySelf-Reference自引用G?del’sIncompletenessTheorem哥德爾不完全定理2復習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復習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>?程序自己分析自己的源程序會出什么結(jié)果？Sometimesthisisperfectlyokay:

-Howbigis<M>?

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

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

-Howbigis<M>?

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

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

-Howbigis<M>?

-Is<M>aproperTM?Otherquestionsleadto

paradoxes:有時似是而非-Does<M>haltornot?如停機-IsthereasmallerprogramM’thatisequivalent?7AvoidingParadoxes?ep199paradox是錯誤理解的問題。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(奇怪動作）M=在這里調(diào)用自己9遞歸從前有個廟，廟里有個老和尚，老和尚給小和尚講故事,講的故事是：”從前有各廟，廟里有個老和尚，老和尚給小和尚將故事,講的什么故事是……”Voidstory(){printf(“從前有個廟，廟里有個老和尚，老和尚給小和尚講故事,講的故事是：”)；story();}毛病，沒有遞歸深度控制，棧溢出時死機鏡子里面照鏡子，電影里面放電影，故事里面講故事更新奇的是：10遞歸從前有個廟，廟里有個老和尚，老和尚給小和尚講故事,講的故事是：”從前有各廟，廟里有個老和尚，老和尚給小和尚將故事,講的什么故事是……”Voidstory(){printf(“從前有個廟，廟里有個老和尚，老和尚給小和尚講故事,講的故事是：”)；story();}毛病，沒有遞歸深度控制，棧溢出時死機鏡子里面照鏡子，電影里面放電影，故事里面講故事更新奇的是：11遞歸從前有個廟，廟里有個老和尚，老和尚給小和尚講故事,講的故事是：”從前有各廟，廟里有個老和尚，老和尚給小和尚將故事,講的什么故事是……”Voidstory(){printf(“從前有個廟，廟里有個老和尚，老和尚給小和尚講故事,講的故事是：”)；story();}毛病，沒有遞歸深度控制，棧溢出時死機鏡子里面照鏡子，電影里面放電影，故事里面講故事,莊生夢蝶，更新奇的是：12The‘DrosteEffect’

Itseemsimpossibleto

haveafiniteobjectthat,

asapart,hasacomplete

descriptionofitself.Youexpectaconflict

betweenthefiniteamount

ofinformation-spaceand

theinfiniterecursion.

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

Itseemsimpossibleto

haveafiniteobjectthat,

asapart,hasacomplete

descriptionofitself.Youexpectaconflict

betweenthefiniteamount

ofinformation-spaceand

theinfiniterecursion.

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

weknowofmany

(mathematical)

objectsthathavea

finitedescription,

yetappeartobe

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

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

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

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

ep200cp130Attempttodescribeaprogramthatprintsitself:

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

(“print_twice_2nd_time_with_(“_“):”)

…SoitispossibletohavesuchaTMM.

TheRecursionTheoremmakesthisexplicit.17MPrintingM打印自己源程序

ep200cp130錯誤方法：Attempttodescribeaprogramthatprintsitself:

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

(“print_twice_2nd_time_with_(“_“):”)

…SoitispossibletohavesuchaTMM.

TheRecursionTheoremmakesthisexplicit.18TheRecursionTheorem

為定理C7.2（遞歸的可行性）作準備

ep200,cp131TherecursiontheoreminCSshowshowwecan

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

1)astringthatdescribes2ndpartofprogram

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

printsitself…且看下面細細道來19TheRecursionTheorem

為定理C7.2（遞歸的可行性）作準備

ep200,cp131TherecursiontheoreminCSshowshowwecan

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

1)astringthatdescribes2ndpartofprogram

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

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

printsitself…且看下面細細道來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);}”

造計算q的TMQ(C程序)如下：Q(w){char*p=q(w);//函數(shù)值是一個源程序串的指針printf(p);}}下頁是書上的證明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);}”

造計算q的TMQ(C程序)如下：Q(w){char*p=q(w);//函數(shù)值是一個源程序串的指針printf(p);}}下頁是書上的證明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利用引理，造一個能打印自己源程序的程序

TheProgram<SELF>=<AB>ep201cp130用C語言描述

庫函數(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名,復制串B(<A>);}下頁是書上的證明輸入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可以是個串加密函數(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可以是個串加密函數(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把自己的源程序作為處理的首部，當w=NULL時，R自己處理自己（注意由于T是任何程序，例如是加密程序，則R把自己加密）下頁是書上的證明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把自己的源程序作為處理的首部，當w=NULL時，R自己處理自己（注意由于T是任何程序，例如是加密程序，則R把自己加密）下頁是書上的證明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把自己的源程序作為處理的首部，當w=NULL時，R自己處理自己（注意由于T是任何程序，例如是加密程序，則R把自己加密）下頁是書上的證明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;平凡簡單2)Lookat<M>;3)MoreBla-bla-bla;M=33ATMisUndecidable用新式武器來證明舊問題

定理6.3ep202Proofbycontradiction:用C語言描述

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

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

ATM={<M,w>|TMMacceptsinputw}

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

定理6.3ep202Proofbycontradiction:用C語言描述

設(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,矛盾下頁是書上的證明TheoremC7.3:Theacceptancelanguage

ATM={<M,w>|TMMacceptsinputw}

isundecidable.接受問題是不可判定的Deter_Accept(M,x)對任何M,x都能判定，對特殊的M=B,x=w當然也能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)用＋否定導出矛盾ForeveryTMHthatclaimstodecideATM,

constructthefollowingTMB(inputw):

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

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

ep204，cp133計劃自學內(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]費馬定理qpx,y[p>q&(x,y>1(xyp&xyp+2))]Wewanttoprovestatementslikethese.39C7.2MathematicalTheories

ep204，cp133計劃自學內(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]費馬定理qpx,y[p>q&(x,y>1(xyp&xyp+2))]Wewanttoprovestatementslikethese.40IncompletenessTheorem哥德爾不完全定理KurtG?del41IncompletenessTheorem哥德爾不完全定理In1931,KurtG?delpublishedhis“überformalunentscheidbareS?tzederPrincipiaMathematicaundverwandterSystemeI”,inwhichheprovedthatformalmathematicalsystemshaveonlylimitedpower.數(shù)學公理系統(tǒng)的局限性Notethatthisresult先于ofTuringand

thesolutionofHilbert’spolynomialproblem.Wewillneverbeabletohaveasystemthatcan

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

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

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

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

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

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

模型論ep205,cpConsiderthe‘model’fornaturalnumberswith

additionandmultiplication(N,+,).

Wewanttoknowwhichstatementsaboutthis

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

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

Amathematicaltheorytriestodescribethis

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

模型論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ù)庫的armstrong公理）公理是不完全的

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

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

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

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

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

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

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

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

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

thatdecideslanguageslike

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

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

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

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

thatdecideslanguageslike

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

但有一些稍微復雜的系統(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

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

ep207cp135

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

knowledgeoffiniteautomata:有限自動機可作加法體系結(jié)構(gòu)課程中的加法器是DFA(bit加和進位機制）-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

用圖靈機來證明哥德爾不完全定理的證明思路要點:

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

,與

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

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

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

用圖靈機來證明哥德爾不完全定理的證明思路要點:

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

,與

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

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

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

形式化表達為

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

（somesmarttricks）

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

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

Th(N,+,)中的一個語句.

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

M;

如果MTh(N,+,),則

Mistrue，andMdoes

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

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

形式化表達為

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

（somesmarttricks）

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

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

Th(N,+,)中的一個語句.

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

M;

如果MTh(N,+,),則

Mistrue，andMdoes

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

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

wecanmakeastatementDthatwecannot

provewithD.WecanexpandtheDwithDorwithD.Cf.Euclideanandnon-Euclidean

geometry:歐氏集合與非歐幾何

“Thesumoftheanglesofatriangle

isequaltotworightangles.”60TheConsequences?cp13761ExpandingtheTMModel

oracle

喻示,請圣賢幫忙，請專家顧問幫忙Justasanymathematicaltheory,wecanexpand

ourTuringmachinemodelfo