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