资源描述：
《Springer.An.Introduction.to.Kolmogorov.Complexity.and.its.Applications.(Li.&.Vitanyi).(Springer.Verlag.1993)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、vPrefacetotheWearetoadmitnomorecausesofnaturalthings(aswearetoldbyNewton)thansuchasarebothtrueandsucienttoexplaintheirap-FirstEditionpearances.Thiscentralthemeisbasictothepursuitofscience,andgoesbacktotheprincipleknownasOccam'srazor:ifpresentedwithachoicebe
2、tweenindi erentalternatives,thenoneoughttoselectthesimplestone."Unconsciouslyorexplicitly,informalapplicationsofthisprincipleinscienceandmathematicsabound.Theconglomerateofdi erentresearchthreadsdrawingonanobjec-tiveandabsoluteformofthisapproachappearstobepar
3、tofasingleemergingdiscipline,whichwillbecomeamajorappliedsciencelikein-formationtheoryorprobabilitytheory.Weaimatprovidingauni edandcomprehensiveintroductiontothecentralideasandapplicationsofthisdiscipline.Intuitively,theamountofinformationina nitestringisthe
4、size(num-berofbinarydigits,orbits)oftheshortestprogramthatwithoutad-ditionaldata,computesthestringandterminates.Asimilarde nitioncanbegivenforin nitestrings,butinthiscasetheprogramproduceselementafterelementforever.Thus,alongsequenceof1'ssuchas11111:::1
5、{z}10
6、;000timescontainslittleinformationbecauseaprogramofsizeaboutlog10;000bitsoutputsit:fori:=1to10;000print1Likewise,thetranscendentalnumber=3:1415:::;anin nitesequenceofseeminglyrandom"decimaldigits,containsbutafewbitsofinfor-mation.(Thereisashortprogramthatpr
7、oducestheconsecutivedigitsofforever.)Suchade nitionwouldappeartomaketheamountofinformationinastring(orotherobject)dependontheparticularpro-gramminglanguageused.Fortunately,itcanbeshownthatallreasonablechoicesofprogramminglanguagesleadtoquanti cationoftheamou
8、ntofabsolute"informationinindividualobjectsthatisinvariantuptoanadditiveconstant.WecallthisquantitytheKolmogorovcomplexity"oftheobject.Ifanobjectcontainsregularities,thenithasashorterdescriptionthanitself.Wecallsuchanobjectcompressible."TheapplicationofKol
9、mogorovcomplexitytakesavarietyofforms,forexample,usingthefactthatsomestringsareextremelycompressible;usingthecompressibilityofstringsasaselectioncriterion;usingthefactthatmanystringsareno
