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.
Tag - journal publication
How to simulate Turing Machines by invertible cellular automata
Saturday 5 January 2008
Abstract of the article
The issue of testing invertibility of cellular automata has been often discussed. The computation universality of cellular automata has long been positively resolved, and by showing that any cellular automaton could be simulated by an invertible one having a superior dimension, Toffoli proved that invertible cellular automaton of dimension d ≥2 were computation-universal. Kenichi Morita proved that any invertible Turing Machine could be simulated by a one-dimensional invertible cellular automaton, which proved computation-universality of invertible cellular automata. This article shows how to simulate any Turing Machine by an invertible cellular automaton with no loss of time and gives, as a corollary, an easier proof of this result.