资源描述：
《The Limits of Mathematics (Discrete Mathematics and Theoretical Computer Science)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、THELIMITSOFMATHEMATICSG.J.ChaitinIBM,POBox704YorktownHeights,NY10598chaitin@watson.ibm.comarXiv:chao-dyn/9407003v17Jul1994DraftJuly7,1994ToFran¸coisePrefaceInaremarkabledevelopment,Ihaveconstructedanewdefinitionforaself-delimitinguniversalTuringmachine(UTM)thatiseasytoprogramandrunsveryquickly.Thisp
2、rovidesanewfoundationforalgorithmicinformationtheory(AIT),whichisthetheoryofthesizeinbitsofprogramsforself-delimitingUTM’s.Previously,AIThadanabstractmathematicalquality.Nowitispossibletowritedownexecutableprogramsthatembodytheconstructionsintheproofsoftheorems.SoAITgoesfromdealingwithremoteidealiz
3、edmythicalobjectstobeingatheoryaboutpracticaldown-to-earthgadgetsthatonecanactuallyplaywithanduse.Thisnewself-delimitingUTMisimplementedviaanextremelyfastLISPinterpreterwritteninC.TheuniversalTuringmachineUiswrit-teninthisLISP.ThisLISPalsoservesasaveryhigh-levelassemblertoputtogetherbinaryprogramsf
4、orU.TheprogramsthatgointoU,andwhosesizewemeasure,arebitstrings.TheoutputfromU,ontheotherhand,consistsofasingleLISPS-expression,inthecaseoffinitecomputations,andofaninfinitesetoftheseS-expressions,inthecaseofinfinitecomputations.TheLISPusedhereisbasedontheversionofLISPthatIusedinmybookAlgorithmicInform
5、ationTheory,CambridgeUniversityPress,1987.Thedifferenceisthata)Ihavefoundaself-delimitingwaytogivebinarydatatoLISPprograms,andb)Ihavefoundanaturalwaytohandleunendingcomputations,whichiswhatformalaxiomaticsystemsare,inLISP.Usingthisnewsoftware,aswellasthelatesttheoreticalideas,itisnowpossibletogiveas
6、elf-contained“handson”coursepresentingveryconcretelymylatestproofsofmytwofundamentalinformation-vvitheoreticincompletenesstheorems.ThefirstofthesetheoremsstatesthatanN-bitformalaxiomaticsystemcannotenableonetoexhibitanyspecificobjectwithprogram-sizecomplexitygreaterthanN+c.Thesecondofthesetheoremssta
7、testhatanN-bitformalaxiomaticsystemcannotenableonetodeterminemorethanN+c′scatteredbitsofthehaltingprobabilityΩ.Mostpeoplebelievethatanythingthatistrueistrueforareason.Thesetheoremsshowthatsomethingsaretruef
