资源描述：
《Algrothm information theroy.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ALGORITHMICINFORMATIONTHEORYThirdPrintingGJChaitinIBM,POBox218YorktownHeights,NY10598chaitin@us.ibm.comApril2,2003Thisbookwaspublishedin1987byCambridgeUni-versityPressasthe rstvolumeintheseriesCam-bridgeTractsinTheoreticalComputerScience.In1988and1990itwasreprintedwithrevisio
2、ns.Thisisthetextofthethirdprinting.HowevertheAPLcharactersetisnolongerused,sinceitisnotgen-erallyavailable.AcknowledgmentsTheauthorispleasedtoacknowledgepermissiontomakefreeuseofpreviouspublications:Chapter6isbasedonhis1975paperAtheoryofprogramsizeformallyidenticaltoinformat
3、iontheory"publishedinvolume22oftheJournaloftheACM,copyrightc1975,AssociationforComputingMachinery,Inc.,reprintedbypermission.Chapters7,8,and9arebasedonhis1987paperIncompletenesstheoremsforrandomreals"publishedinvolume8ofAdvancesinAp-pliedMathematics,copyrightc1987byAcademicP
4、ress,Inc.TheauthorwishestothankRalphGomory,GordonLasher,andthePhysicsDepartmentoftheWatsonResearchCenter.12ForewordTuring'sdeep1937papermadeitclearthatG¨odel'sastonishingearlierresultsonarithmeticundecidabilityrelatedinaverynaturalwaytoaclassofcomputingautomata,nonexistentatt
5、hetimeofTuring'spaper,butdestinedtoappearonlyafewyearslater,subsequentlytoproliferateastheubiquitousstored-programcomputeroftoday.Theappearanceofcomputers,andtheinvolvementofalargescienti ccommunityinelucidationoftheirpropertiesandlimitations,greatlyenrichedthelineofthoughtop
6、enedbyTuring.Turing'sdistinctionbetweencomputa-tionalproblemswasrawlybinary:someweresolvablebyalgorithms,othersnot.Laterwork,ofwhichanattractivepartiselegantlydevel-opedinthepresentvolume,re nedthisintoamultiplicityofscalesofcomputationaldiculty,whichisstilldevelopingasafund
7、amentaltheoryofinformationandcomputationthatplaysmuchthesameroleincomputersciencethatclassicalthermodynamicsplaysinphysics:byde ningtheouterlimitsofthepossible,itpreventsdesignersofalgorithmsfromtryingtocreatecomputationalstructureswhichprov-ablydonotexist.Itisnotsurprisingth
8、atsuchathermodynamicsofinformationshouldbeasrichinphilosophicalconse
