Two-dimensional Kolmogorov complexity and an empirical validation of the Coding theorem method by compressibility

Submi ed 26 May 2015 Accep ed 1 Sep embe 2015 Published 30 Sep embe 2015 Co esponding au ho Hec o Zenil, hec o[email p o ec ed] Academic edi o Mikael Skoglund Addi ional In o ma ion and Decla a ions can be ound on page 29 DOI 10.7717/pee j-cs.23 Copy igh 2015 Zenil e al. Dis ibu ed unde C ea i e Commons CC-BY 4.0 OPEN ACCESS Two-dimensional Kolmogo o complexi y and an empi ical alida ion o he Coding heo em me hod by comp essibili y Hec o Zenil1,2,6, Fe nando Sole -Toscano3,6, Jean-Paul Delahaye4,6 and Nicolas Gau i 5,6 1Uni o Compu a ional Medicine, Depa men o Medicine Solna, SciLi eLab (Science o Li e Labo a o y), Cen e o Molecula Medicine and Ka olinska Ins i u e, S ockholm, Sweden 2Depa men o Compu e Science, Uni e si y o Ox o d, UK 3G upo de L´ ogica, Lenguaje e In o maci´ on, Uni e sidad de Se illa, Spain 4CRISTAL (Cen e de eche che en in o ma ique, signal e au oma ique de Lille), F ance 5CHA Lab, ´ Ecole P a ique des Hau es E udes, Pa is, F ance 6Algo i hmic Na u e G oup, LABoRES, Pa is, F ance ABSTRACT We p opose a measu e based upon he undamen al heo e ical concep in algo i hmic in o ma ion heo y ha p o ides a na u al app oach o he p oblem o e alua ing n-dimensional complexi y by using an n-dimensional de e minis ic Tu ing machine. The echnique is in e es ing because i p o ides a na u al algo i h- mic p ocess o symme y b eaking gene a ing complex n-dimensional s uc u es om pe ec ly symme ic and ully de e minis ic compu a ional ules p oducing a dis ibu ion o pa e ns as desc ibed by algo i hmic p obabili y. Algo i hmic p obabili y also elegan ly connec s he equency o occu ence o a pa e n wi h i s algo i hmic complexi y, hence e ec i ely p o iding es ima ions o he complexi y o he gene a ed pa e ns. Expe imen s o alida e es ima ions o algo i hmic complexi y based on hese concep s a e p esen ed, showing ha he measu e is s able in he ace o some changes in compu a ional o malism and ha esul s a e in ag eemen wi h he esul s ob ained using lossless comp ession algo i hms when bo h me hods o e lap in hei ange o applicabili y. We hen use he ou pu equency o he se o 2-dimensional Tu ing machines o classi y he algo i hmic complexi y o he space- ime e olu ions o Elemen a y Cellula Au oma a. Subjec s Compu a ional Biology, A i icial In elligence, Theo y and Fo mal Me hods Keywo ds Algo i hmic complexi y, Algo i hmic p obabili y, Kolmogo o –Chai in complexi y, Algo i hmic in o ma ion heo y, Cellula au oma a, Solomono –Le in uni e sal dis ibu ion, In o ma ion heo y, Dimensional complexi y, Image complexi y, Small Tu ing machines INTRODUCTION The ques ion o na u al measu es o complexi y o objec s o he han s ings and sequences, in pa icula sui ed o 2-dimensional objec s, is an open impo an p oblem in complexi y science and wi h po en ial applica ions o molecule olding, cell dis ibu ion, a i icial li e and obo ics. He e we p o ide a measu e based upon he undamen al How o ci e his a icle Zenil e al. (2015), Two-dimensional Kolmogo o complexi y and an empi ical alida ion o he Coding heo em me hod by comp essibili y. Pee J Compu . Sci. 1:e23;DOI 10.7717/pee j-cs.23 heo e ical concep ha p o ides a na u al app oach o he p oblem o e alua ing n-dimensional algo i hmic complexi y by using an n-dimensional de e minis ic Tu ing machine, popula ized unde he e m o Tu mi es o n=2, om which he so-called Lang on’s an is an example o a Tu ing uni e sal Tu mi e. A se ies o expe imen s o alida e es ima ions o Kolmogo o complexi y based on hese concep s is p esen ed, showing ha he measu e is s able in he ace o some changes in compu a ional o malism and ha esul s a e in ag eemen wi h he esul s ob ained using lossless comp ession algo- i hms when bo h me hods o e lap in hei ange o applicabili y. We also p esen a di ide and conque algo i hm ha we call Block Decomposi ion Me hod (BDM) applica ion o classi ica ion o images and space– ime e olu ions o disc e e sys ems, p o iding e idence o he soundness o he me hod as a complemen a y al e na i e o comp ession algo i hms o he e alua ion o algo i hmic complexi y. We p o ide exac nume ical app oxima ions o Kolmogo o complexi y o squa e image pa ches o size 3 and mo e, wi h he BDM allowing scalabili y o la ge 2-dimensional a ays and e en g ea e dimensions. The challenge o inding and de ining 2-dimensional complexi y measu es has been iden i ied as an open p oblem o ounda ional cha ac e in complexi y science (Feldman & C u ch ield, 2003;Shalizi, Shalizi & Haslinge , 2004). Indeed, o example, humans unde s and 2-dimensional pa e ns in a way ha seems undamen ally di e en han 1-dimensional (Feldman, 2008). These measu es a e impo an because cu en 1-dimensional measu es may no be sui able o 2-dimensional pa e ns o asks such as quan i a i ely measu ing he spa ial s uc u e o sel -o ganizing sys ems. On he one hand, he applica ion o Shannon’s En opy and Kolmogo o complexi y has adi ionally been designed o s ings and sequences. Howe e , n-dimensional objec s may ha e s uc u e only dis inguishable in hei na u al dimension and no in lowe dimensions. This is indeed a ques ion ela ed o he loss o in o ma ion in dimension educ ionali y (Zenil, Kiani & Tegn´ e , in p ess). A ew measu es o 2-dimensional complexi y ha e been p oposed be o e building upon Shannon’s en opy and block en opy (Feldman & C u ch ield, 2003;And ienko, B illian o & Ku hs, 2000), mu ual in o ma ion and minimal su icien s a is ics (Shalizi, Shalizi & Haslinge , 2004) and in he con ex o ana omical b ain MRI analysis (Young e al., 2009;Young & Schu , 2008). A mo e ecen applica ion, also in he medical con ex ela ed o a measu e o consciousness, was p oposed using lossless comp essibili y o EGG b ain image analysis was p oposed in Casali e al. (2013). On he o he hand, o Kolmogo o complexi y, he common app oach o e alua ing he algo i hmic complexi y o a s ing has been by using lossless comp ession algo i hms because he leng h o lossless comp ession is an uppe bound o Kolmogo o complexi y. Sho s ings, howe e , a e di icul o comp ess in p ac ice, and he heo y does no p o- ide a sa is ac o y solu ion o he p oblem o he ins abili y o he measu e o sho s ings. He e we use so-called Tu mi es (2-dimensional Tu ing machines) o es ima e he Kolmogo o complexi y o images, in pa icula space– ime diag ams o cellula au oma a, using Le in’s Coding heo em om algo i hmic p obabili y heo y. We s udy he p oblem o he a e o con e gence by compa ing app oxima ions o a uni e sal dis ibu ion using di e en (and la ge ) se s o small Tu ing machines and compa ing he esul s o Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 2/31 ha o lossless comp ession algo i hms ca e ully de ising es s a he in e sec ion o he applica ion o comp ession and algo i hmic p obabili y. We ound ha s ings which a e mo e andom acco ding o algo i hmic p obabili y also u n ou o be less comp essible, while less andom s ings a e clea ly mo e comp essible. Comp ession algo i hms ha e p o en o be signally applicable in se e al domains (see e.g., Li & Vi ´ anyi, 2009), yielding su p ising esul s as a me hod o app oxima ing Kolmogo o complexi y. Hence hei success is in pa a ma e o hei use ulness. He e we show ha an al e na i e (and complemen a y) me hod yields compa ible esul s wi h he esul s o lossless comp ession. Fo his we de ised an a ul echnique by g ouping s ings ha ou me hod indica ed had he same p og am-size complexi y, in o de o cons uc iles o conca ena ed s ings o he same complexi y (while a oiding epe i ion, which could easily be exploi ed by comp ession). Then a lossless gene al comp ession algo i hm was used o comp ess he iles and asce ain whe he he iles ha we e mo e comp essed we e he ones c ea ed wi h highly complex s ings acco ding o ou me hod. Simila ly, iles wi h low Kolmogo o complexi y we e es ed o de e mine whe he hey we e be e com- p essed. This was indeed he case, and we epo hese esul s in ‘Valida ion o he Coding Theo em Me hod by Comp essibili y’. In ‘Compa ison o Kmand comp ession o cellula au oma a’ we also show ha he Coding heo em me hod yields a e y simila classi ica ion o he space– ime diag ams o Elemen a y Cellula Au oma a, despi e he disad an age o ha ing used a limi ed sample o a Uni e sal Dis ibu ion. In all cases he s a is ical e idence is s ong enough o sugges ha he Coding heo em me hod is sound and capable o p oducing sa is ac o y esul s. The Coding heo em me hod also ep esen s he only cu en ly a ailable me hod o dealing wi h e y sho s ings and in a sense is an expensi e bu powe ul “mic oscope” o cap u ing he in o ma ion con en o e y small objec s. KOLMOGOROV–CHAITIN COMPLEXITY Cen al o algo i hmic in o ma ion heo y (AIT) is he de ini ion o algo i hmic (Kolmogo o –Chai in o p og am-size) complexi y (Kolmogo o , 1965;Chai in, 1969): KT(s)=min{|p|,T(p)=s}.(1) Tha is, he leng h o he sho es p og am p ha ou pu s he s ing s unning on a uni e sal Tu ing machine T. A classic example is a s ing composed o an al e na ion o bi s, such as (01)n, which can be desc ibed as “n epe i ions o 01”. This epe i i e s ing can g ow as while i s desc ip ion will only g ow by abou log2(n). On he o he hand, a andom-looking s ing such as 011001011010110101 may no ha e a much sho e desc ip ion han i sel . Uncompu abili y and ins abili y o K A echnical incon enience o Kas a unc ion aking s o he leng h o he sho es p og am ha p oduces sis i s uncompu abili y (Chai in, 1969). In o he wo ds, he e is no p og am which akes a s ing sas inpu and p oduces he in ege K(s)as ou pu . This is usually conside ed a majo p oblem, bu one ough o expec a uni e sal measu e o complexi y Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 3/31 o ha e such a p ope y. On he o he hand, Kis mo e p ecisely uppe semi-compu able, meaning ha one can ind uppe bounds, as we will do by applying a echnique based on ano he semi-compu able measu e o be p esen ed in he ‘Solomono –Le in Algo i hmic P obabili y’. The in a iance heo em gua an ees ha complexi y alues will only di e ge by a cons an c(e.g., he leng h o a compile , a ansla ion p og am be ween U1and U2) and ha hey will con e ge a he limi . In a iance Theo em (Calude, 2002;Li & Vi ´ anyi, 2009): I U1and U2a e wo uni e sal Tu ing machines and KU1(s)and KU2(s) he algo i hmic complexi y o s o U1and U2, he e exis s a cons an csuch ha o all s: |KU1(s)−KU2(s)|<c.(2) Hence he longe he s ing, he less impo an cis (i.e., he choice o p og amming language o uni e sal Tu ing machine). Howe e , in p ac ice ccan be a bi a ily la ge because he in a iance heo em ells no hing abou he a e o con e gence be ween KU1 and KU2 o a s ing so inc easing leng h, hus ha ing an impo an impac on sho s ings. SOLOMONOFF–LEVIN ALGORITHMIC PROBABILITY The algo i hmic p obabili y (also known as Le in’s semi-measu e) o a s ing sis a measu e ha desc ibes he expec ed p obabili y o a andom p og am p unning on a uni e sal (p e ix- ee1) Tu ing machine Tp oducing supon hal ing. Fo mally (Solomono , 1964; 1The g oup o alid p og ams o ms a p e ix- ee se (no elemen is a p e ix o any o he , a p ope y necessa y o keep 0<m(s) < 1). Fo de ails see Calude (2002). Le in, 1974;Chai in, 1969), m(s)= p:T(p)=s 1/2|p|.(3) Le in’s semi-measu e2m(s)de ines a dis ibu ion known as he Uni e sal Dis ibu ion 2I is called a semi measu e because he sum is ne e 1, unlike p obabili y measu es. This is due o he Tu ing machines ha ne e hal . (a beau i ul in oduc ion is gi en in Ki che , Li & Vi anyi (1997)). I is impo an o no ice ha he alue o m(s)is domina ed by he leng h o he smalles p og am p(when he denomina o is la ge ). Howe e , he leng h o he smalles p ha p oduces he s ing s is K(s). The semi-measu e m(s)is he e o e also uncompu able, because o e e y s,m(s) equi es he calcula ion o 2−K(s), in ol ing K, which is i sel uncompu able. An al e na i e o he adi ional use o comp ession algo i hms is he use o he concep o algo i hmic p obabili y o calcula e K(s)by means o he ollowing heo em. Coding Theo em (Le in, 1974): |−log2m(s)−K(s)|<c.(4) This means ha i a s ing has many desc ip ions i also has a sho one. I beau i ully connec s equency o complexi y, mo e speci ically he equency o occu ence o a s ing wi h i s algo i hmic (Kolmogo o ) complexi y. The Coding heo em implies ha (Co e & Thomas, 2006;Calude, 2002) one can calcula e he Kolmogo o complexi y o a s ing om Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 4/31 i s equency (Delahaye & Zenil, 2007b;Delahaye & Zenil, 2007a;Zenil, 2011;Delahaye & Zenil, 2012), simply ew i ing he o mula as: Km(s)= −log2m(s)+O(1). (5) An impo an p ope y o mas a semi-measu e is ha i domina es any o he e ec i e semi-measu e µ, because he e is a cons an cµsuch ha o all s,m(s)≥cµµ(s). Fo his eason m(s)is o en called a Uni e sal Dis ibu ion (Ki che , Li & Vi anyi, 1997). THE CODING THEOREM METHOD Le D(n,m)be a unc ion (Delahaye & Zenil, 2012) de ined as ollows: D(n,m)(s)=|{T∈(n,m):Tp oduces s}| |{T∈(n,m):Thal s }| (6) whe e (n,m)deno es he se o Tu ing machines wi h ns a es and msymbols, unning wi h emp y inpu , and |A|is, in his case, he ca dinali y o he se A. In Zenil (2011) and Delahaye & Zenil (2012) we calcula ed he ou pu dis ibu ion o Tu ing machines wi h 2-symbols and n=1,...,4 s a es o which he Busy Bea e (Rad´ o, 1962) alues a e known, in o de o de e mine he hal ing ime, and in Sole -Toscano e al. (2014) esul s we e imp o ed in e ms o numbe and Tu ing machine size (5 s a es) and in he way in which an al e na i e o he Busy Bea e in o ma ion was p oposed, hence no longe needing exac in o ma ion o hal ing imes in o de o app oxima e an in o ma i e dis ibu ion. He e we conside an expe imen wi h 2-dimensional de e minis ic Tu ing machines (also called Tu mi es) in o de o es ima e he Kolmogo o complexi y o 2-dimensional objec s, such as images ha can ep esen space– ime diag ams o simple sys ems. A Tu mi e is a Tu ing machine which has an o ien a ion and ope a es on a g id o “ ape”. The machine can mo e in 4 di ec ions a he han in he adi ional le and igh mo emen s o a adi ional Tu ing machine head. A e e ence o his kind o in es iga ion and de ini ion o 2D Tu ing machines can be ound in Wol am (2002), one popula and possibly one o he i s examples o his a ia ion o a Tu ing machine is Lag on’s an (Lang on, 1986) also p o en o be capable o Tu ing-uni e sal compu a ion. In ‘Compa ison o Kmand app oaches based on comp ession’, we will use he so-called Tu mi es o p o ide e idence ha Kolmogo o complexi y e alua ed h ough algo i hmic p obabili y is consis en wi h he o he (and oday only) me hod o app oxima ing K, namely lossless comp ession algo i hms. We will do his in an a ul way, gi en ha comp ession algo i hms a e unable o comp ess s ings ha a e oo sho , which a e he s ings co e ed by ou me hod. This will in ol e conca ena ing s ings o which ou me hod es ablishes a Kolmogo o complexi y, which hen a e gi en o a lossless comp ession algo i hm in o de o de e mine whe he i p o ides consis en es ima ions, ha is, o de e mine whe he s ings a e less comp essible whe e ou me hod says ha hey ha e g ea e Kolmogo o complexi y and whe he s ings a e mo e comp essible whe e ou me hod says hey ha e lowe Kolmogo o complexi y. We p o ide e idence ha his is ac ually he case. Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 5/31 In ‘Compa ison o Kmand comp ession o cellula au oma a’ we will apply he esul s om he Coding heo em me hod o app oxima e he Kolmogo o complexi y o 2-dimensional e olu ions o 1-dimensional, closes neighbo Cellula Au oma a as de ined in Wol am (2002), and by way o o e ing a con as o he app oxima ion p o ided by a gene al lossless comp ession algo i hm (De la e). As we will see, in all hese expe imen s we p o ide e idence ha he me hod is jus as success ul as comp ession algo i hms, bu unlike he la e , i can deal wi h sho s ings. De e minis ic 2-dimensional Tu ing machines (Tu mi es) Tu mi es o 2-dimensional (2D) Tu ing machines un no on a 1-dimensional ape bu in a 2-dimensional unbounded g id o a ay. A each s ep hey can mo e in ou di e en di ec ions (up,down,le , igh ) o s op. T ansi ions ha e he o ma {n1,m1} → {n2,m2,d}, meaning ha when he machine is in s a e n1and eads symbols m1, i w i es m2, changes o s a e n2and mo es o a con iguous cell ollowing di ec ion d. I n2is he hal ing s a e hen dis s op. In o he cases, dcan be any o he o he ou di ec ions. Le (n,m)2Dbe he se o Tu ing machines wi h ns a es and msymbols. These machines ha e nm en ies in he ansi ion able, and o each en y {n1,m1} he e a e 4nm +mpossible ins uc ions, ha is, mdi e en hal ing ins uc ions (w i ing one o he di e en symbols) and 4nm non-hal ing ins uc ions (4 di ec ions, ns a es and m di e en symbols). So he numbe o machines in (n,m)2Dis (4nm +m)nm. I is possible o enume a e all hese machines in he same way as 1D Tu ing machines (e.g., as has been done in Wol am (2002) and Joos en (2012)). We can assign one numbe o each en y in he ansi ion able. These numbe s go om 0 o 4nm +m−1 (gi en ha he e a e 4nm +m di e en ins uc ions). The numbe s co esponding o all en ies in he ansi ion able (i espec i e o he con en ion ollowed in so ing hem) o m a numbe wi h nm digi s in base 4nm+m. Then, he ansla ion o a ansi ion able o a na u al numbe and ice e sa can be done h ough elemen a y a i hme ical ope a ions. We ake as ou pu o a 2D Tu ing machine he minimal a ay ha includes all cells isi ed by he machine. No e ha his p obably includes cells ha ha e no been isi ed, bu i is he mo e na u al way o p oducing ou pu wi h some egula o ma and a he same ime educing he se o di e en ou pu s. Figu e 1 shows an example o he ansi ion able o a Tu ing machine in (3,2)2Dand i s execu ion o e a ‘0’- illed g id. We show he po ion o he g id ha is e u ned as he ou pu a ay. Two o he six cells ha e no been isi ed by he machine. AN APPROXIMATION TO THE UNIVERSAL DISTRIBUTION We ha e un all machines in (4,2)2Djus as we ha e done be o e o de e minis ic 1-dimensional Tu ing machines (Delahaye & Zenil, 2012;Sole -Toscano e al., 2014). Tha is, conside ing he ou pu o all di e en machines s a ing bo h in a ‘0’- illed g id (all whi e) and in a ‘1’- illed (all black) g id. Symme ies a e desc ibed and used in he same way han in Sole -Toscano e al. (2014) in o de o a oid unning a la ge numbe o machines whose ou pu can be p edic ed om o he equi alen machines (by o a ion, Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 6/31 Figu e 1 Top: Example o a de e minis ic 2-dimensional Tu ing machine. Bo om: Accumula ed un ime dis ibu ion o (4,2)2D. ansposi ion, 1-complemen a ion, e e sion, e c.) ha p oduce equi alen ou pu s wi h he same equency. We also used a educed enume a ion o a oid unning ce ain i ial machines whose beha io can be p edic ed om he ansi ion able, as well as il e s o de ec non-hal ing machines be o e exhaus ing he en i e un ime. In he educed enume a ion we conside ed only machines wi h an ini ial ansi ion mo ing o he igh and changing o a di e en s a e han he ini ial and hal ing s a es. Machines mo ing o he ini ial s a e a he s a ing ansi ion un o e e , and machines mo ing o he hal ing s a e p oduce single-cha ac e ou pu . So we educe he numbe o ini ial ansi ions in (n,m)2D o m(n−1)( he machine can w i e any o he msymbols and change o any s a e in {2,...,n}). The se o di e en machines is educed acco dingly o k(n−1)(4nm +m)nm−1. To enume a e hese machines we cons uc a mixed- adix numbe , gi en ha he digi co esponding o he ini ial ansi ion now goes om 0 o m(n−1)−1. To he ou pu ob ained when unning his educed enume a ion we add he single-cha ac e a ays ha co espond o machines Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 7/31 mo ing o he ini ial s a e a he s a ing ansi ion. These machines and hei ou pu can be easily quan i ied. Also, o ake in o accoun machines wi h he ini ial ansi ion mo ing in a di e en di ec ion han he igh one, we conside he 90, 180 and 270 deg ee o a ions o he s ings p oduced, gi en ha o any machine mo ing up (le /down) a he ini ial ansi ion, he e is ano he one mo ing igh ha p oduces he iden ical ou pu bu o a es −90 (−180/−270) deg ees. Se ing he un ime The Busy Bea e un ime alue o (4,2)is 107 s eps upon hal ing. Bu no equi alen Busy Bea e s a e known o 2-dimensional Tu ing machines (al hough a ia ions o Tu mi e’s Busy Bea e unc ions ha e been p oposed (Pegg, 2013)). So o se he un ime in ou expe imen we gene a ed a sample o 334 ×108 andom machines in he educed enume a ion. We used a un ime o 2,000 s eps o he un ime sample, his is 10.6% o he machines in he educed enume a ion o (4,2)2D, bu 1,500 s eps o unning all (4,2)2D. These machines we e gene a ed ins uc ion by ins uc ion. As we ha e explained abo e, i is possible o assign a na u al numbe o e e y ins uc ion. So o gene a e a andom machine in he educed enume a ion o (n,m)2Dwe p oduce a andom numbe om 0 o m(n−1)−1 o he ini ial ansi ion and om 0 o 4nm +m−1 o he o he nm −1 ansi ions. We used he implemen a ion o he Me senne Twis e in he Boos C++ lib a y. The ou pu o his sample was he dis ibu ion o he un ime o he hal ing machines. Figu e 1 shows he p obabili y ha a andom hal ing machine will hal in a mos he numbe o s eps indica ed on he ho izon al axis. Fo 100 s eps his p obabili y is 0.9999995273. No e ha he machines in he sample a e in he educed enume a ion, a la ge numbe o e y i ial machines hal ing in jus one s ep ha ing been emo ed. So in he comple e enume a ion he p obabili y o hal ing in a mos 100 s eps is e en g ea e . Bu we ound some high un ime alues—p ecisely 23 machines equi ed mo e han 1,000 s eps. The highes alue was a machine p og essing h ough 1,483 s eps upon hal ing. So we ha e enough e idence o belie e ha by se ing he un ime a 2,000 s eps we ha e ob ained almos all (i no all) ou pu a ays. We an all 6 ×347Tu ing machines in he educed enume a ion o (4,2)2D. Then we applied he comple ions explained be o e. OUTPUT ANALYSIS The inal ou pu ep esen s he esul o 2(4nm +m)2execu ions (all machines in (4,2)2D s a ing wi h bo h blank symbols ‘0’ and ‘1’). We ound 3,079,179,980,224 non-hal ing machines and 492,407,829,568 hal ing machines. A numbe o 1,068,618 di e en bina y a ays we e p oduced a e 12 days o calcula ion wi h a supe compu e o medium size (a 25×86-64 CPUs unning a 2,128 MHz each wi h 4 GB o memo y each, loca ed a he Cen o In o m´ a ico Cien ´ ı ico de Andaluc´ ıa (CICA), Spain. Le D(4,2)2Dbe he se cons uc ed by di iding he occu ences o each di e en a ay by he numbe o hal ing machines as a na u al ex ension o Eq. (6) o 2-dimensional Tu ing machines. Then, o e e y s ing s, Km,2D(s)= −log2(D(4,2)(s)) (7) Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 8/31 Figu e 2 The op 36 objec s in D(4,2)2Dp eceded by hei Km,2D alues, so ed by highe o lowe e- quency and he e o e om smalle o la ge Kolmogo o complexi y a e applica ion o he Coding heo em. Only non-symme ical cases a e displayed. The g id is only o illus a ion pu poses. using he Coding heo em (Eq. (3)). Figu e 2 shows he op 36 objec s in D(4,2)2D, ha is he objec s wi h lowes Kolmogo o complexi y alues. E alua ing 2-dimensional Kolmogo o complexi y D(4,2)2Ddeno es he equency dis ibu ion (a calcula ed Uni e sal Dis ibu ion) om he ou pu o de e minis ic 2-dimensional Tu ing machines, wi h associa ed complexi y measu e Km,2D.D(4,2)2Ddis ibu es 1,068,618 a ays in o 1,272 di e en complexi y alues, wi h a minimum complexi y alue o 2.22882 bi s (an explana ion o non-in ege p og am-size complexi y is gi en in Sole -Toscano e al. (2014) and Sole -Toscano e al. (2013)), a maximum alue o 36.2561 bi s and a mean o 35.1201. Conside ing he numbe o possible squa e bina y a ays gi en by he o mula 2d×d(wi hou conside ing any symme ies), D(4,2)2Dcan be said o p oduce all squa e bina y a ays o leng h up o 3×3, ha is 3 d=12d×d=530 squa e a ays, and 60,016 o he 2(4×4)=65,536 squa e a ays wi h side o leng h (o dimension) d=4. I only p oduces 84,104 o he 33,554,432 Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 9/31 Figu e 7 Top: Dis ibu ion o complexi y alues o di e en s ing leng hs (l). Bo om: Dis ibu ion o he comp essed leng hs o he iles. Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 16/31 Figu e 8 Sca e plo o Kmwi h 2-dimensional Tu ing machines (Tu mi es) as a unc ion o Kmwi h 1-dimensional Tu ing machines. s ings g ows ( igh pa o he diag ams), he comp essed iles a e la ge , so hey a e ha de o comp ess. The ele an excep ion is leng h 15, bu his is p obably ela ed o he low numbe o s ings o ha leng h ha we ha e ound, which a e su ely no he mos complex s ings o leng h 15. We ha e used o he comp esso s such as GZIP (which uses Lempel–Zi algo i hm LZ77) and BZIP2 (Bu ows–Wheele block so ing ex comp ession algo i hm and Hu man coding), wi h se e al comp ession le els. The esul s a e simila o hose shown in Fig. 7. Compa ing (4,2)2Dand (4,2) We shall now look a how 1-dimensional a ays (hence s ings) p oduced by 2D Tu ing machines co ela e wi h s ings ha we ha e calcula ed be o e (Zenil, 2011;Delahaye & Zenil, 2012;Sole -Toscano e al., 2014) (deno ed by D(5)). In a sense his is like changing he Tu ing machine o malism o see whe he he new dis ibu ion esembles dis ibu ions ollowing o he Tu ing machine o malisms, and whe he i is obus enough. All Tu ing machines in (4,2)a e included in (4,2)2Dbecause hese a e jus he machines ha do no mo e up o down. We i s compa ed he alues o he 1,832 ou pu s ings in (4,2) o he 1-dimensional a ays ound in (4,2)2D. We a e also in e es ed in he ela ion be ween he anks o hese 1,832 s ings in bo h (4,2)and (4,2)2D. Figu e 8 shows he link be ween Km,2Dwi h 2D Tu ing machines as a unc ion o o dina y Km,1D( ha is, simply Kmas de ined in Sole -Toscano e al. (2014)). I sugges s a s ong almos -linea o e all associa ion. The co ela ion coe icien =0.9982 con i ms Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 17/31 Figu e 9 Sca e plo o Kmwi h 2-dimensional Tu ing machines as a unc ion o Kmwi h 1- dimensional Tu ing machines by leng h o s ings, o s ings o leng h 5–13. he linea associa ion, and he Spea man co ela ion coe icien s=0.9998 p o es a igh and inc easing unc ional ela ion. The leng h lo s ings is a possible con ounding ac o . Howe e Fig. 9 sugges s ha he link be ween one and 2-dimensional complexi ies is no explainable by l. Indeed, he pa ial co ela ion Km,1DKm,2D.l=0.9936 s ill deno es a igh associa ion. Figu e 9 also sugges s ha complexi ies a e mo e s ongly linked wi h longe s ings. This is in ac he case, as Table 2 shows: he s eng h o he link inc eases wi h he leng h o he esul ing s ings. One and 2-dimensional complexi ies a e ema kably co ela ed and may be conside ed wo measu es o he same unde lying ea u e o he s ings. How hese measu es a y is ano he ma e . The eg ession o Km,2Don Km,1Dgi es he ollowing app oxima e ela ion: Km,2D≈2.64 +1.11Km,1D. No e ha his sub le depa u e om iden i y may be a consequence o a sligh non-linea i y, a ea u e isible in Fig. 8. Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 18/31 Table 2 Co ela ion coe icien s be ween one and 2-dimensional complexi ies by leng h o s ings. Leng h (l) Co ela ion 5 0.9724 6 0.9863 7 0.9845 8 0.9944 9 0.9977 10 0.9952 11 1 12 1 Compa ison o Kmand comp ession o cellula au oma a A 1-dimensional CA can be ep esen ed by an a ay o cells xiwhe e i∈Z(in ege se ) and each x akes a alue om a ini e alphabe Σ. Thus, a sequence o cells {xi}o ini e leng h ndesc ibes a s ing o global con igu a ion c on Σ. This way, he se o ini e con igu a ions will be exp essed as Σn. An e olu ion comp ises a sequence o con igu a ions {ci}p oduced by he mapping Φ:Σn→Σn; hus he global ela ion is symbolized as: Φ(c )→c +1(8) whe e ep esen s ime and e e y global s a e o cis de ined by a sequence o cell s a es. The global ela ion is de e mined o e he cell s a es in con igu a ion c upda ed simul aneously a he nex con igu a ion c +1by a local unc ion ϕas ollows: ϕ(x i− ,...,x i,...,x i+ )→x +1 i.(9) Wol am (2002) ep esen s 1-dimensional cellula au oma a (CA) wi h wo pa ame e s (k, )whe e k= |Σ|is he numbe o s a es, and is he neighbo hood adius. Hence his ype o CA is de ined by he pa ame e s (2,1). The e a e Σndi e en neighbo hoods (whe e n=2 +1) and kkndis inc e olu ion ules. The e olu ions o hese cellula au oma a usually ha e pe iodic bounda y condi ions. Wol am calls his ype o CA Elemen a y Cellula Au oma a (deno ed simply by ECA) and he e a e exac ly kkn=256 ules o his ype. They a e conside ed he mos simple cellula au oma a (and among he simples compu ing p og ams) capable o g ea beha io al ichness. 1-dimensional ECA can be isualized in 2-dimensional space– ime diag ams whe e e e y ow is an e olu ion in ime o he ECA ule. By hei simplici y and because we ha e a good unde s anding abou hem (e.g., a leas one ECA is known o be capable o Tu ing uni e sali y (Cook, 2004;Wol am, 2002)) hey a e excellen candida es o es ou measu e Km,2D, being jus as e ec i e as o he me hods ha app oach ECA using comp ession algo i hms (Zenil, 2010) ha ha e yielded he esul s ha Wol am ob ained heu is ically. Km,2Dcompa ison wi h comp essed ECA e olu ions We ha e seen ha ou Coding heo em me hod wi h associa ed measu e Km(o Km,2Din his pape o 2D Kolmogo o complexi y) is in ag eemen wi h bi s ing complexi y as Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 19/31 app oached by comp essibili y, as we ha e epo ed in ‘Compa ison o Kmand app oaches based on comp ession’. The Uni e sal Dis ibu ion om Tu ing machines ha we ha e calcula ed (D(4,2)2D) will help us o classi y Elemen a y Cellula Au oma a. Classi ica ion o ECA by comp ess- ibili y has been done be o e in Zenil (2010) wi h esul s ha a e in comple e ag eemen wi h ou in ui ion and knowledge o he complexi y o ce ain ECA ules (and ela ed o Wol am’s (2002) classi ica ion). In Zenil (2010) bo h classi ica ions by simples ini ial condi ion and andom ini ial condi ion we e unde aken, leading o a s able comp ess- ibili y classi ica ion o ECAs. He e we ollowed he same p ocedu e o bo h simples ini ial condi ion (single black cell) and andom ini ial condi ion in o de o compa e he classi ica ion o he one ha can be app oxima ed by using D(4,2)2D, as ollows. We will say ha he space– ime diag am (o e olu ion) o an Elemen a y Cellula Au oma on ca e ime has complexi y: Km,2Dd×d(c )= q∈{c }d×d Km,2D(q). (10) Tha is, he complexi y o a cellula au oma on cis he sum o he complexi ies o he q a ays o image pa ches in he pa i ion ma ix {c }d×d om b eaking {c }in o squa e a ays o leng h dp oduced by he ECA a e s eps. An example o a pa i ion ma ix o an ECA e olu ion is shown in Fig. 13 o ECA Rule 30 and d=3 whe e =6. No ice ha he bounda y condi ions o a pa i ion ma ix may equi e he addi ion o a mos d−1 emp y ows o d−1 emp y columns o he bounda y as shown in Fig. 13 (o al e na i ely he dismissal o a mos d−1 ows o d−1 columns) i he dimensions (heigh and wid h) a e no mul iples o d, in his case d=3. I he classi ica ion o all ules in ECA by Km,2Dyields he same classi ica ion ob ained by comp essibili y, one would be pe suaded ha Km,2Dis a good al e na i e o comp essibili y as a me hod o app oxima ing he Kolmogo o complexi y o objec s, wi h he signal ad an age ha Km,2Dcan be applied o e y sho s ings and e y sho a ays such as images. Because all possible 29a ays o size 3 ×3 a e p esen in Km,2Dwe can use his a ays se o y o classi y all ECAs by Kolmogo o complexi y using he Coding Theo em me hod. Figu e 6 shows all ele an (non-symme ic) a ays. We deno e by Km,2D3×3 his subse om Km,2D. Figu e 11 displays he sca e plo o comp ession complexi y agains Km,2D3×3calcula ed o e e y cellula au oma on. I shows a posi i e link be ween he wo measu es. The Pea son co ela ion amoun s o =0.8278, so he de e mina ion coe icien is 2=0.6853. These alues co espond o a s ong co ela ion, al hough smalle han he co ela ion be ween 1- and 2-dimensional complexi ies calcula ed in ‘Compa ison o Kmand app oaches based on comp ession’. Conce ning o de s a ising om hese measu es o complexi y, hey oo a e s ongly linked, wi h a Spea man co ela ion o s=0.9200. The sca e plo s (Fig. 11) show a s ong ag eemen be ween he Coding heo em me hod and he adi ional comp ession me hod when bo h a e used o classi y ECAs by hei app oxima ion o Kolmogo o complexi y. Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 20/31 Figu e 10 All he i s 128 ECAs ( he o he 128 a e 0–1 e e ed ules) s a ing om he simples (black cell) ini ial con igu a ion unning o =36 s eps, so ed om lowes o highes complexi y acco ding o Km,2D3×3.No ice ha he same p ocedu e can be ex ended o i s use on a bi a y images. Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 21/31 Figu e 11 Sca e plo s o Comp ess e sus Km,2D3×3on he 128 i s ECA e olu ions a e =90 s eps. Top: Dis ibu ion o poin s along he axes displaying clus e s o equi alen ules and a dis ibu ion co esponding o he known complexi y o a ious cases. Bo om: Same plo bu wi h some ECA ules highligh ed some o which we e used in he side by side compa ison in Fig. 13 (bu unlike he e, he e o a single black cell ini ial condi ion). Tha ules dis ibu e on he diagonal indica es ha bo h me hods a e co ela ed as heo e ically expec ed (e en i lossless comp ession is a o m o en opy a e up o he comp ession ixed maximum wo d leng h). Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 22/31 The anomalies ound in he classi ica ion o Elemen a y Cellula Au oma a (e.g., Rule 77 being placed among ECA wi h high complexi y acco ding o Km,2D3×3) is a limi a ion o Km,2D3×3i sel and no o he Coding heo em me hod which o d=3 is unable o “see” beyond 3-bi squa es using, which is ob iously e y limi ed. And ye he deg ee o ag eemen wi h comp essibili y is su p ising (as well as wi h in ui ion, as a glance a Fig. 10 shows, and as he dis ibu ion o ECAs s a ing om andom ini ial condi ions in Fig. 13 con i ms). In ac an a e age ECA has a complexi y o abou 20K bi s, which is qui e a la ge p og am-size when compa ed o wha we in ui i ely gauge o be he complexi y o each ECA, which may sugges ha hey should ha e smalle p og ams. Howe e , one can hink o D(4,2)2D3×3as a emp ing o econs uc he e olu ion o each ECA o he gi en numbe o s eps wi h squa e a ays only 3 bi s in size, he complexi y o he h ee squa e a ays adding up o app oxima e Km,2Do he ECA ule. Hence i is he deploymen o D(4,2)2D3×3 ha akes be ween 500 o 50K bi s o econs uc e e y ECA space– ime e olu ion depending on how andom e sus how simple i is. O he ways o exploi he da a om D(4,2)2D(e.g., non-squa e a ays) can be u ilized o explo e be e classi ica ions. We hink ha cons uc ing a Uni e sal Dis ibu ion om a la ge se o Tu ing machines, e.g., D(5,2)2D4×4will deli e mo e accu a e esul s bu he e we will also in oduce a weak o he de ini ion o he complexi y o he e olu ion o a cellula au oma on. Spli ing ECA ules in a ay squa es o size 3 is like ying o look h ough li le windows 9 pixels wide one a a ime in o de o ecognize a ace, o aining a “mic oscope” on a plane in he sky. One can do be e wi h he Coding heo em me hod by going u he han we ha e in he calcula ion o a 2-dimensional Uni e sal Dis ibu ion (e.g., calcula ing in ull o a sample o D(5,2)2D4×4), bu e en ually how a his p ocess can be aken is dic a ed by he compu a ional esou ces a hand. Ne e heless, one should use a elescope whe e elescopes a e needed and a mic oscope whe e mic oscopes a e needed. Block Decomposi ion Me hod One can hink o an imp o emen in esolu ion o Km,2D(c) o g owing space– ime diag ams o cellula au oma on by aking he log2(n)o he sum o he a ays whe e nis he numbe o epea ed a ays, ins ead o simply adding he complexi y o he image pa ches o a ays. Tha is, one penalizes epe i ion o imp o e he esolu ion o Km,2D o la ge images as a so o “op ical lens”. This is possible because we know ha he Kolmogo o complexi y o epea ed objec s g ows by log2(n), jus as we explained wi h an example in ‘Kolmogo o –Chai in Complexi y’. Adding he complexi y app oxima ion o each a ay in he pa i ion ma ix o a space– ime diag am o an ECA p o ides an uppe bound on he ECA Kolmogo o complexi y, as i shows ha he e is a p og am ha gene a es he ECA e olu ion pic u e wi h he leng h equal o he sum o he p og ams gene a ing all he sub-a ays (plus a small alue co esponding o he code leng h o join he sub-a ays). So i a sub-a ay occu s n imes we do no need o conside i s complexi y n imes bu log2(n). Taking in o accoun his, Eq. (10) can be hen ew i en as: K′ m,2Dd×d(c )= ( u,nu)∈{c }d×d Km( u)+log2(nu)(11) Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 23/31 whe e ua e he di e en squa e a ays in he pa i ion {c }d×do he ma ix c and nu he mul iplici y o u, ha is he numbe o epe i ions o d×d-leng h pa ches o squa e a ays ound in c . F om now on we will use K′ o squa es o size g ea e han 3 and i may be deno ed only by Ko by BDM s anding o Block decomposi ion me hod. BDM has now been applied success ully o measu e, o example, he Kolmogo o complexi y o g aphs and complex ne wo ks (Zenil e al., 2014) by way o hei adjacency ma ices (a 2D g id) and was shown o be consis en wi h labelled and unlabelled (up o isomo phisms) g aphs. Now complexi y alues o K′ m,2Dd×d ange be ween 70 and 3K bi s wi h a mean p og am-size alue o abou 1K bi s. The classi ica ion o ECA, acco ding o Eq. (11), is p esen ed in Fig. 12. The e is an almos pe ec ag eemen wi h a classi ica ion by lossless comp ession leng h (see Fig. 13) which makes e en one wonde whe he he Coding heo em me hod is ac ually p o iding mo e accu a e app oxima ions o Kolmogo o complexi y han lossless comp essibili y o his objec s leng h. No ice ha he same p ocedu e can be ex ended o i s use on a bi a y images. We denomina e his echnique Block Decomposi ion Me hod. We hink i will p o e o be use ul in a ious a eas, including machine lea ning as an o Kolmogo o complexi y (o he con ibu ions o ML inspi ed in Kolmogo o complexi y can be ound in Hu e (2003)). Also wo h no ice ha he ac ha ECA can be success ully classi ied by Km,2Dwi h an app oxima ion o he Uni e sal Dis ibu ion calcula ed om Tu ing machines (TM) sugges s ha ou pu equency dis ibu ions o ECA and TM canno be bu s ongly co ela ed, some hing ha we had ound and epo ed be o e in Zenil & Delahaye (2010) and Delahaye & Zenil (2007b). Ano he a ia ion o he same Km,2Dmeasu e is o di ide he o iginal image in o all possible squa e a ays o a gi en leng h a he han aking a pa i ion. This would, howe e , be exponen ially mo e expensi e han he pa i ion p ocess alone, and gi en he esul s in Fig. 12 u he a ia ions do no seem o be needed, a leas no o his case. Robus ness o he app oxima ions o m(s) One impo an ques ion ha a ises when posi ing he soundness o he Coding heo em me hod as an al e na i e o ha ing o pick a uni e sal Tu ing machine o e alua e he Kolmogo o complexi y Ko an objec , is how many a bi a y choices a e made in he p ocess o ollowing one o ano he me hod and how impo an hey a e. One o he mo i a ions o he Coding heo em me hod is o deal wi h he cons an in ol ed in he In a iance heo em (Eq. (2)), which depends on he (p e ix- ee) uni e sal Tu ing machine chosen o measu e Kand which has such an impac on eal-wo ld applica ions in ol ing sho s ings. While he cons an in ol ed emains, gi en ha a e applica ion o he Coding heo em (Eq. (3)) we ein oduce he cons an in he calcula ion o K, a legi ima e ques ion o ask is wha di e ence i makes o ollow he Coding heo em me hod compa ed o simply picking he uni e sal Tu ing machine. On he one hand, one has o bea in mind ha no o he me hod exis ed o app ox- ima ing he Kolmogo o complexi y o sho s ings. On he o he hand, we ha e ied o minimize any a bi a y choice, om he o malism o he compu ing model o he Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 24/31 Figu e 12 Block Decomposi ion Me hod.All he i s 128 ECAs ( he o he 128 a e 0–1 e e ed ules) s a ing om he simples (black cell) ini ial con igu a ion unning o =36 s eps, so ed om lowes o highes complexi y acco ding o Klog as de ined in Eq. (11). Zenil e al. (2015), Pee J Compu . Sci., DOI 10.7717/pee j-cs.23 25/31