资源描述：
《Kolmogorov Complexity》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、KolmogorovComplexityLanceFortnow1.Introduction010101010101010101010101100111011101011100100110110100110010110100101100Considerthethreestringsshownabove.Althoughallare24-bitbinarystringsandthereforeequallylikelytorepresenttheresultof24
ipsofafaircoin,thereisamarkeddi erenc
2、einthecomplexityofdescribingeachofthethree.The rststringcanbefullydescribedbystatingthatitisa24-bitstringwitha1inpositionniffnisodd,thethirdhasthepropertythatpositioniisa1iffthereareanoddnumberof1'sinthebinaryexpansionofpositioni,butthesecondstringappearsnottohaveasimilarl
3、ysimpledescription,andthusinordertodescribethestringwearerequiredtoreciteitscontentsverbatim.Whatisadescription?Fix=f0;1g.Letf:7!.Then(relativetof),adescriptionofastringissimplysome withf( )=:Careisneededinusingthisde nition.Withoutfurtherrestrictions,paradoxesarepo
4、ssible(considerthedescriptionthesmallestpositiveintegernotdescribableinfewerthan ftywords").Werestrictfbyrequiringthatitbecomputable,althoughnotnecessarilytotal,butdonotinitiallyconcernourselveswiththetime-complexityoff.Wearenowabletode neKolmogorovComplexityCf:(minfjpj:f
5、(p)=xgifx2ranfDe nition1.1.Cf(x)=1otherwiseItwouldbebettertohavea xednotionofdescriptionratherthanhavingtode nefeachtime.Or,indeed,tohaveanotionofcomplexitythatdoesnotvaryaccordingtowhichfwechoose.Tosomeextentthisproblemisunavoidable,butwecanachieveasortofindependenceifweu
6、seaUniversalTuringMachineThisarticlewaspreparedfromnotesoftheauthortakenbyAmyGaleinKaikoura,January2000.2(UTM).Asiswellknown,thereexistsaTuringMachineUsuchthatforallpartialcomputablef,thereexistsaprogrampsuchthatforally,U(p;y)=f(y).Wede neapartialcomputablefunctiongbylett
7、ingg(0jpj1py)=U(p;y).Thefollowingbasicfactisnotdiculttosee,andremovesthedependenceonf.ThusitallowsustotalkabouttheKolmogorovcomplexity.Claim1.1.Forallpartialcomputablefthereexistsaconstantcsuchthatforallx,Cg(x)Cf(x)+c.(Infact,c=2jpj+1,wherepisaprogramforf.)Nowde neC(x)=C
8、g(x).Aswehaveseen,thisiswithinaconstantofothercomplexities.WecanalsoextendClaim1.1tobinar
