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.
Quoting this publication
This article was published in English in Theoretical Computer Science, a very good journal of theoretical computer science (hence the title).
Even if the article was published in May 2001, the last revision is dated 31 march 1999. Sometimes, the editorial process is that long...
@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
}
