In this article, written jointly with Enrico Formenti and Bruno Durand, we present a new approach to cellular automata (CA) classification based on algorithmic complexity. We construct a parameter κ which is based only on the transition table of CA and measures the "randomness" of evolutions; κ is better, in a certain sense, than any other parameter recursively definable on CA tables. We investigate the relations between the classical topological approach and ours one. Our parameter is compared with Langton's λ parameter: κ turns out to be theoretically better and also agrees with some practical evidences reported in literature. Finally, we propose a protocol to approximate κ and make experiments on CA dynamical behavior.
Even if written as published in may 2001, the last revision is dated from the 31st of March, 1999. Sometimes, it's a very long process to get an article published. It was submitted to numerous conferences before getting out as a journal papel: ISAAC'97, ICALP'98, MFCS'98, FCT'97, also as an internal research report... The various versions are too similar and do not deserve a separate presentation (or distribution).
The documents
Citing this publication
This article was published in Theoretical Computer Science, a top theoretical computer science-journal.
@Article{ddf01,
author = {Jean-Christophe Dubacq and Bruno Durand and Enrico Formenti},
title = {{Kolmogorov} complexity and cellular automata classification},
journal = {Theoretical Computer Science},
year = {2001},
volume = {259},
number = {1--2},
pages = {271--285},
month = may
}