On the length of programs for computing finite bin

ONTHELENGTHOFPROGRAMSFORCOMPUTINGFINITEBINARYSEQUENCES:STATISTICALCONSIDERATIONSJournaloftheACM16(1969),pp.145{159GregoryJ.Chaitin1BuenosAires,ArgentinaAbstractAnattemptismadetocarryoutaprogram(outlinedinapreviouspa-per)fordeningtheconceptofarandomorpatternless,nitebinarysequence,andforsubsequentlydeningarandomorpatternless,in-nitebinarysequencetobeasequencewhoseinitialsegmentsareallrandomorpatternlessnitebinarysequences.Adenitionbasedon12G.J.Chaitinthebounded-transferTuringmachineisgivendetailedstudy,butinsuf-cientunderstandingofthiscomputingmachineprecludesacompletetreatment.Acomputingmachineisintroducedwhichavoidsthesedif-culties.KeyWordsandPhrases:computationalcomplexity,sequences,randomsequences,Turingma-chinesCRCategories:5.22,5.5,5.61.IntroductionInthissectionadenitionispresentedoftheconceptofarandomorpatternlessbinarysequencebasedon3-tape-symbolbounded-transferTuringmachines.2Thesecomputingmachineshavebeenintroducedandstudiedin[1],whereaproposaltoapplytheminthismannerismade.Theresultsfrom[1]whichareusedinstudyingthedenitionarelistedforreferenceattheendofthissection.AnN-state,3-tape-symbolbounded-transferTuringmachineisde-nedbyanN-row,3-columntable.Eachofthe3Nplacesinthistablemustcontainanorderedpair(i;j)ofnaturalnumberswhereitakesonvaluesfrombtob,andjfrom1to5.3Theseentriesconstitute,whenspecied,theprogramoftheN-state,3-tape-symbolbounded-transferTuringmachineandaretobeinterpretedasfollows.Anentry(i;j)inthekthrowandthepthcolumnofthetablemeansthatwhenthemachineisinitskthstate,andthesquareofitsone-wayinnitetape1Address:MarioBravo249,BuenosAires,Argentina.2Thechoiceof3-tape-symbolmachinesismademerelyforthepurposeofxingideas.3Herebisaconstantwhosevalueistoberegardedasxedthroughoutthispaper.Itsexactvalueisnotimportantaslongasitisnot\toosmall.Foranexplanationofthemeaningof\toosmall,andproofsthatbcanbechosensothatitisnottoosmall,see[1,Secs.2.1and2.2].(bwillnotbementionedagain.)ComputingFiniteBinarySequences:StatisticalConsiderations3BlackBoxTapeEndofTapeScanner100100::::::6Figure1.ATuringmachineHalted01111000::::::6Figure2.Theendofacomputationwhichisbeingscannedcontainsthepthsymbol,thenif1k+iN,themachineistogotoits(k+i)-thstate(otherwise,themachineistohalt)afterperformingoneofthefollowingoperations:(a)movingthetapeonesquaretotherightifj=5;(b)movingthetapeonesquaretotheleftifj=4;(c)marking(overprinting)thesquarebeingscannedwiththejthsymbolif1j3.Therst,second,andthirdsymbolsarecalled,respectively,theblank(forunmarkedsquare),0,and1.Abounded-transferTuringmachinemayberepresentedschemati-callyasshowninFigure1.Wemakethefollowingstipulations:initiallythemachineisinitsrststateandscanningtherstsquareofthetape;nobounded-transferTuringmachinemayinthecourseofacalculationscantheendsquareofthetapeandthenmovethetapeonesquaretotheright;initiallyallsquaresofthetapeareblank;onlyorderstotrans-fertostateN+1maybeusedtohaltthemachine.Abounded-transfer4G.J.ChaitinTuringmachineissaidtocalculateaparticularnitebinarysequence(e.g.01111000)ifthemachinestopswiththatsequencewrittenattheendofitstape,withallothersquaresofthetapeblank,andwithitsscannerontherstblanksquareofthetape.Figure2illustratesama-chinewhichhascalculatedtheparticularsequencementionedabove.Beforeproceedingwewouldliketomakeacommentfromthepointofviewoftheprogrammer.Thelogicaldesignofthebounded-transferTuringmachineprovidesautomaticallyforrelocationofprograms,andtheprecedingparagraphestablisheslinkageconventionsforsubroutineswhichcalculatenitebinarysequences.Twofunctionsarenowdenedwhichplayfundamentalrolesinallthatfollows.L,therstfunction,4isdenedonthesetofallnitebinarysequencesSasfollows:AnN-state,3-tape-symbolbounded-transferTuringmachinecanbeprogrammedtocalculateSifandonlyifNL(S).ThesecondfunctionL(Cn)isdenedasL(Cn)=maxSoflengthnL(S)wherethemaximumistaken(asindicated)overallbinarysequencesSoflengthn.Alsodenoteby5CnthesetofallbinarysequencesSoflengthnsatisfyingL(S)=L(Cn).Anattemptismadein[1,Sec.3.1]tomakeitplausible,onthebasisofvariousphilosophicalconsiderations,thatthepatternlessorrandomnitebinarysequencesoflengthnarethosesequencesSforwhichL(S)isapproximatelyequaltoL(Cn).Hereanattemptismadetoclarifythis(somewhatinformal)denitionandtomakeitplausiblebyprovingvariousresultsconcerningwhatmaybetermedstatisticalpropertiesofsuchnitebinarysequences.ThesetC1ofpatternlessorrandom,innitebinarysequencesisformallydenedtobethesetofallinnitebinarysequencesSwhichsatisfythefollowinginequalityforallsucientlylargevaluesofn:L(Sn)L(Cn)f(n)4Useoftheletter\Lissuggestedbythephrase\theLengthofprogramneces-saryforcomputing:::.5Useoftheletter\Cissuggestedbythephrase\themostComplexbinarysequencesoflength:::.ComputingFiniteBinarySequences:StatisticalConsiderations5wheref(n)=3log2nandSnisthesequenceoftherstnbitsofS.Thisdenition,unliketherst,isquiteprecisebutisalsosomewhatarbitrary.Thefailuretostatetheexactcut-opointatwhichL(S)becomestoosmallforStobeconsideredrandomorpatternlessgivestotherstdenitionitsinformalcharacter.Butinthecaseofnitebinarysequences,