资源描述：
《Instructor_s_Manual_for_Computability_and_Logic》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、INSTRUCTOR’SMANUALFORCOMPUTABILITYANDLOGICFIFTHEDITIONPARTA.FORALLREADERSsJOHNP.BURGESSProfessorofPhilosophyPrincetonUniversityjburgess@princeton.eduNoteThisworkissubjecttocopyright,butinstructorswhoadoptComputability&Logicasatextbookareherebyauthorizedtoc
2、opyanddistributethepresentPartA.ThispermissiondoesnotextendtoPartB.ContentsDependenceofChapters(Leitfaden)2GeneralRemarksonProblems(forStudents)3HintsforOdd-NumberedProblemsComputabilityTheory4HintsforOdd-NumberedProblemsBasicMetalogic11Errata2023Dependenc
3、eofChapters1&2Preliminaries3-4Turingmachines6&7Recursiveness9&10First-orderlogic5Abacuscomputability12-14Metatheoryoffirst-orderlogic8Turing’stheorem19-21Topicsinmetalogic11.1Church’stheorem,proof#111.2Church’stheorem,proof#215Arithmetization16Representabi
4、lity17FirstIncompletenessTheorem22-26Topicsinarithmetic18SecondIncompletenessTheorem27Provabilitylogic4GeneralRemarksonProblems(forStudents)•Theproblemsforeachchaptershouldbereadaspartofthatchapter,eventhosethatarenotassigned.Theyoftenaddimportantinformati
5、onnotcoveredinthetext.•Theresultsofearlierproblems,whetherornotassigned,maybeusedinlaterproblems.Manyproblemsarepartsofsequences.•Beforeworkingtheproblemsforanychapter,checktoseewhetherthereareanyerratalistedforthatchapter,andespeciallyforitsproblems.•Hint
6、sareprovidedforodd-numberedproblemsinchapters1-18.Thehintsforsomeproblemsareinevitablymoresubstantialthanthoseforothers.5HintsforOdd-NumberedProblems:ComputabilityTheory(Chapters1-8)Chapter11.1Theconverseassertionfollowsfromthefirstassertionbyapplyingittof
7、-1anditsinversef-1-1.1.3For(a)considertheidentityfunctioni(a)=aforallainA.For(b)and(c)usetheprecedingtwoproblems,asperthegeneralhintabove.1.5Showbothsetsaredenumerable.1.7IfwecanfixforeachianenumerationofAiAi={ai1,ai2,ai3,…}Thenwecanenumerate∪A,whichisthes
8、etofallaijforalliandjinthesamewayweenumeratedpairs(i,j)inExample1.2.However,whenweassumethatforeachAithereexistsanenumerationofit,itfollowsthatthereexistmanydifferentsuchenumerationsforeachAi;andwhensettheory
