




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 破产重整厂房股权转让合同范本
- 拆迁项目风险评估与管理合同
- 财务担保业务信息共享合作协议
- 彩钢房安全责任书(适用于学校建筑)
- 2025年中考考前最后一卷化学(广州卷)(全解全析)
- 避难室工程作业指导书书
- 宿舍管理饭堂管理制度
- 医院仪器放置管理制度
- 公司租金收缴管理制度
- 团内激励团员管理制度
- 最简单装修合同协议书
- 阿米巴模式的合同协议书
- DB32/T 4622.4-2023采供血过程风险管理第4部分:血液成分制备和供应风险控制规范
- 技术员奖励协议书
- 北京市先农坛体育运动技术学校招聘笔试真题2024
- 2025年供应链管理专业考试试题及答案
- 打破传统藩篱:小学高段先写后教习作教学模式的创新与实践
- 2025山东能源集团营销贸易限公司招聘机关部分业务人员31人易考易错模拟试题(共500题)试卷后附参考答案
- 2024年漳州市招聘中小学幼儿园教师真题
- 2025年道德与法治课程考试试卷及答案
- 天津2025年中国医学科学院放射医学研究所第一批招聘笔试历年参考题库附带答案详解
评论
0/150
提交评论