资源描述：
《algorithmic information theory(chaitin)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ALGORITHMICINFORMATIONTHEORYThirdPrintingGJChaitinIBM,POBox704YorktownHeights,NY10598chaitin@watson.ibm.comSeptember30,1997Thisbookwaspublishedin1987byCambridgeUni-versityPressasthe rstvolumeintheseriesCam-bridgeTractsinTheoreticalComputerScience.In1988and1990itwasreprintedwi
2、threvisions.Thisisthetextofthethirdprinting.HowevertheAPLcharactersetisnolongerused,sinceitisnotgen-erallyavailable.AcknowledgmentsTheauthorispleasedtoacknowledgepermissiontomakefreeuseofpreviouspublications:Chapter6isbasedonhis1975paperAtheoryofprogramsizeformallyidenticalt
3、oinformationtheory"publishedinvolume22ofthecJournaloftheACM,copyright1975,AssociationforComputingMachinery,Inc.,reprintedbypermission.Chapters7,8,and9arebasedonhis1987paperIncompletenesstheoremsforrandomreals"publishedinvolume8ofAdvancesinAp-cpliedMathematics,copyright1987by
4、AcademicPress,Inc.TheauthorwishestothankRalphGomory,GordonLasher,andthePhysicsDepartmentoftheWatsonResearchCenter.12ForewordTuring'sdeep1937papermadeitclearthatGodel'sastonishingearlierresultsonarithmeticundecidabilityrelatedinaverynaturalwaytoaclassofcomputingautomata,nonexi
5、stentatthetimeofTuring'spaper,butdestinedtoappearonlyafewyearslater,subsequentlytoproliferateastheubiquitousstored-programcomputeroftoday.Theappearanceofcomputers,andtheinvolvementofalargescienti ccommunityinelucidationoftheirpropertiesandlimitations,greatlyenrichedthelineoft
6、houghtopenedbyTuring.Turing'sdistinctionbetweencomputa-tionalproblemswasrawlybinary:someweresolvablebyalgorithms,othersnot.Laterwork,ofwhichanattractivepartiselegantlydevel-opedinthepresentvolume,re nedthisintoamultiplicityofscalesofcomputationaldiculty,whichisstilldevelopin
7、gasafundamentaltheoryofinformationandcomputationthatplaysmuchthesameroleincomputersciencethatclassicalthermodynamicsplaysinphysics:byde ningtheouterlimitsofthepossible,itpreventsdesignersofalgorithmsfromtryingtocreatecomputationalstructureswhichprov-ablydonotexist.Itisnotsurp
8、risingthatsuchathermodynamicsofinformationshouldbeasrichinphilosophi
