计算理论09-递归哥德尔

PartII:ComputabilityTheory计算理论引论

byMichaelSipserChapter7:RecursionTheoremDr.WeibingFengwbfeng@1今天课程

ChapterC7:C7.1PotentialProblemswith

InfiniteRecursion

Recursiontheorem递归可行性

UndecidabilitybySelf-Reference自引用Gödel’sIncompletenessTheorem哥德尔不完全定理2复习UndecidabilityThusFarcp130Undecidability–thusfar–usedtheundecidability

oftheacceptproblemATM.我们已经充分使用了接受问题的不可判定性WeprovedtheundecidabilityofATMbymakingexplicittheself-referenceparadox:

采用了自引用集合

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

技巧在于（直观解释）让程序处理自己的源程序：

LetPbeaTMthatrecognizesS,then

“Pon<P>”leadstoacontradiction.Crucialingredient:关键技术

Self-Reference:Paccepts<P>.3复习UndecidabilityThusFarcp130Undecidability–thusfar–usedtheundecidability

oftheacceptproblemATM.我们已经充分使用了接受问题的不可判定性WeprovedtheundecidabilityofATMbymakingexplicittheself-referenceparadox:采用了自引用集合

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

技巧在于（直观解释）让程序分析自己的源程序：

LetPbeaTMthatrecognizesS,then

“Pon<P>”leadstoacontradiction.Crucialingredient:关键技术

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

answerquestionsaboutitself<M>?程序自己分析自己的源程序会出什么结果？Sometimesthisisperfectlyokay:

-Howbigis<M>?

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

answerquestionsaboutitself<M>?程序自己分析自己的源程序会出什么结果？Sometimesthisisperfectlyokay:

-Howbigis<M>?

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

answerquestionsaboutitself<M>?程序自己分析自己的源程序会出什么结果？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=在这里调用自己9递归从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”从前有各庙，庙里有个老和尚，老和尚给小和尚将故事,讲的什么故事是……”Voidstory(){printf(“从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”)；story();}毛病，没有递归深度控制，栈溢出时死机镜子里面照镜子，电影里面放电影，故事里面讲故事更新奇的是：10递归从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”从前有各庙，庙里有个老和尚，老和尚给小和尚将故事,讲的什么故事是……”Voidstory(){printf(“从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”)；story();}毛病，没有递归深度控制，栈溢出时死机镜子里面照镜子，电影里面放电影，故事里面讲故事更新奇的是：11递归从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”从前有各庙，庙里有个老和尚，老和尚给小和尚将故事,讲的什么故事是……”Voidstory(){printf(“从前有个庙，庙里有个老和尚，老和尚给小和尚讲故事,讲的故事是：”)；story();}毛病，没有递归深度控制，栈溢出时死机镜子里面照镜子，电影里面放电影，故事里面讲故事,庄生梦蝶，更新奇的是：12The‘DrosteEffect’

Itseemsimpossibleto

haveafiniteobjectthat,

asapart,hasacomplete

descriptionofitself.Youexpectaconflict

betweenthefiniteamount

ofinformation-spaceand

theinfiniterecursion.

注意这里递归另例小学一年级语文数封面13The‘DrosteEffect’

Itseemsimpossibleto

haveafiniteobjectthat,

asapart,hasacomplete

descriptionofitself.Youexpectaconflict

betweenthefiniteamount

ofinformation-spaceand

theinfiniterecursion.

注意这里递归另例小学一年级语文数封面14InfiniteRecursioninMath<ep200Ontheotherhand,

weknowofmany

(mathematical)

objectsthathavea

finitedescription,

yetappeartobe

infinitelydetailed…分形数学15MPrintingM打印自己源程序

ep200cp130问题：自己调用自己的TM是否合法的图灵机

自己调用自己的程序是否合法的程序？本节要向证明，

满足一定规范非自己调用是合法的，从数学本质上看，是正确的，不是诡辩，不是悖论而且用途广泛.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.打印指定串的程序的源程序是可以用程序产生的

证明程序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);//函数值是一个源程序串的指针printf(p);}}下页是书上的证明21ASimpleLemmacp130LemmaC7.1

:Letwbeaninputstring,andletPw

beaTMthatprintsw.

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

证明程序

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);//函数值是一个源程序串的指针printf(p);}}下页是书上的证明22ASimpleLemma，cp130书上的证明LemmaC7.1

:Letwbeaninputstring,andletPw

beaTMthatprintsw.

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

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

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

库函数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可以是个串加密函数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可以是个串加密函数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描述的证明:已经有了程序T(w){加密..}，现在如下造程序R:R(w){char*s=<R>;//R自己的源程序或代码，前面已经证明可得

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描述的证明:已经有了程序T(w){加密..}，现在如下造程序R:R(w){char*s=<R>;//R自己的源程序或代码，前面已经证明可得

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描述的证明:已经有了程序T(w){加密..}，现在如下造程序R:R(w){char*s=<R>;//R自己的源程序或代码，前面已经证明可得

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可自己调自己

ispossible.ItshowsthatprogramslikeSELFarepossible.

Makesundecidabilityproofsmoretransparent

astheycannowbephrasedforasingleTM.1)Bla-bla-bla;平凡简单2)Lookat<M>;3)MoreBla-bla-bla;M=33ATMisUndecidable用新式武器来证明旧问题

定理6.3ep202Proofbycontradiction:用C语言描述

设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语言描述

设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.用自调用＋否定导出矛盾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计划自学内容，略讲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计划自学内容，略讲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.数学公理系统的局限性Notethatthisresult先于ofTuringand

thesolutionofHilbert’spolynomialproblem.Wewillneverbeabletohaveasystemthatcan

provealltruestatementsabout{0,1,2,…},+,.42数学哲学学派补充

1柏拉图主义，哥德尔等数学真理是客观的外在的，不依赖于数学家，唯物2直觉主义，拒绝完成先概念，否定排中律，要求构造选证明（机械唯物）3形式主义公理定理一切真理，希尔波特，布尔巴基。Turing研究了康托、哥德尔成果，提出了停机问题43数学哲学学派补充

历史上是先有哥德尔定理，后有停机问题不可判定反过来用停机问题不可判定也可以证明哥德尔定理证明：每一个算术命题编码称为有限串，所有的问题可列。对TMM输入W的停机问题是一个算术命题，也列在其中如果不存在不可判定命题，则停机问题可判定，矛盾。44数学哲学学派补充

理论与模型（model，模特）含有变量的

命题T(x1,x2,…Xn)在集合A={(a1,a2,an),b1,b2,…bn),…}上成立。则称A为T的模型。例子：T=信息技术是现代战争重要战力。

A={海湾战争，伊拉克战争，….}45ModelTheory集合＋运算

模型论ep205,cpConsiderthe‘model’fornaturalnumberswith

additionandmultiplication(N,+,).

Wewanttoknowwhichstatementsaboutthis

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

statementsabout/expressedin(N,+,).真命题称为定理

Amathematicaltheorytriestodescribethis

Th(N,+,)withaxiomsandderivationrules.公理系统描述定理的推理46ModelTheory集合＋运算

模型论ep205,cpConsiderthe‘model’fornaturalnumberswith

additionandmultiplication(N,+,).

Wewanttoknowwhichstatementsaboutthis

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

statementsabout/expressedin(N,+,).真命题称为定理

Amathematicaltheorytriestodescribethis

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

推不出的都不正确（如证关系数据库的armstrong公理）公理是不完全的

：有正确的命题，不能被推出存在命题A,A和~A都不能被证明

(A和～A中必有一真）所以不完全系统中一定有不可判定问题。公理是不完全的，可能是公理个数太少公理是不可靠，可能是公理太多，有互相矛盾的48公理系统基本概念公理是可靠的sound：推出的都正确公理是完全的complete：正确都能被推出

推不出的都不正确（如证关系数据库的armstrong公理）公理是不完全的

：有正确的命题，不能被推出存在命题A,A和~A都不能被证明

(A和～A中必有一真）所以不完全系统中一定有不可判定问题。公理是不完全的，可能是公理个数太少公理是不可靠，可能是公理太多，有互相矛盾的49公理系统基本概念公理是可靠的sound：推出的都正确公理是完全的complete：正确都能被推出

推不出的都不正确（如证关系数据库的armstrong公理）公理是不完全的

：有正确的命题，不能被推出存在命题A,A和~A都不能被证明

(A和～A中必有一真）所以不完全系统中一定有不可判定问题。公理是不完全的，可能是公理个数太少公理是不可靠，可能是公理太多，有互相矛盾的50Gödel’sIncompletenessThm

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

thatdecideslanguageslike

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

但有一些稍微复杂的系统不可判定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,+,)}.可判定

但有一些稍微复杂的系统不可判定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

说明在不太复杂的公理系统Th(N,+,)中有正确的但不能被证明的命题，说明公理系统的描述能力有限53CompletenessforTh(N,+)定理C7.10

ep207cp135

作为讨论题目，谁来自告奋勇？ThesetoftruestatementsTh(N,+)isdecidable.自然数和加法的系统是可判定的Theproofofthisresultscanbedonewithour

knowledgeoffiniteautomata:有限自动机可作加法体系结构课程中的加法器是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

用图灵机来证明哥德尔不完全定理的证明思路要点:

反设存在TMM，它能识别Th(N,+,)中的正确命题(即正确的都能被证明），给一个语句

,与

中必有一真。并行地调度并运行M()和M()。只要其中之一接受，就停止并接受那个语句。所以M能判定

Th(N,+,).给出M的描述<M>,考虑下列语句“Mwillrejectthisstatement”.利用计算历史,等价于

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

用图灵机来证明哥德尔不完全定理的证明思路要点:

反设存在TMM，它能识别Th(N,+,)中的正确命题(即正确的都能被证明），给一个语句

,与

中必有一真。并行地调度并运行M()和M()。只要其中之一接受，就停止并接受那个语句。所以M能判定

Th(N,+,).给出M的描述<M>,考虑下列语句“Mwillrejectthisstatement”.利用计算历史,等价于

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

形式化表达为

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

（somesmarttricks）

用Th(N,+,)的术语表达函数

REJECT(M,M)，则M=C[REJECT(M,M)(C)]也是系统

Th(N,+,)中的一个语句.

如果MTh(N,+,)(“istrue”)则M拒绝

M;

如果MTh(N,+,),则

Mistrue，andMdoes

notrejectM.与M的构造定义矛盾

与前几周证明的类似，这次更细致一些，58ProofIncompletenessThm(2)把M=(rejectingcomputinghistoryofMonM)

形式化表达为

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

（somesmarttricks）

用Th(N,+,)的术语表达函数

REJECT(M,M)，则M=C[REJECT(M,M)(C)]也是系统

Th(N,+,)中的一个语句.

如果MTh(N,+,)(“istrue”)则M拒绝

M;

如果MTh(N,+,),则

Mistrue，andMdoes

notrejectM.与M的构造定义矛盾

与前几周证明的类似，这次更细致一些，59TheConsequences?cp137ForanyaxiomaticdescriptionDofTh(N,+,),

wecanmakeastatementDthatwecannot

provewithD.WecanexpandtheDwithDorwithD.Cf.Euclideanandnon-Euclidean

geometry:欧氏集合与非欧几何

“Thesumoftheanglesofatriangle

isequaltotworightangles.”60TheConsequences?cp13761ExpandingtheTMModel

oracle

喻示,请圣贤帮忙，请专家顾问帮忙Justasanymathematicaltheory,wecanexpand

ourTuringmachinemodelfo