Volume 84, Number 5, December 2008
Article Number 50005
Number of page(s) 6
Section General
Published online 16 December 2008
EPL, 84 (2008) 50005
DOI: 10.1209/0295-5075/84/50005

When are cellular automata random?

J. B. Coe1, 2, S. E. Ahnert3 and T. M. A. Fink1, 4, 2, 5

1   INSERM U900, Curie Institute - Paris, F-75248, France
2   Ecole des Mines de Paris, ParisTech - Fontainebleau, F-77300, France
3   Theory of Condensed Matter, Cavendish Laboratory - Cambridge, CB3 0HE, UK
4   CNRS UMR144, Curie Institute - Paris, F-75248, France
5   London Institute for Mathematical Sciences - 22 South Audley Street, London, W1K 2NY, UK

received 29 July 2008; accepted in final form 20 October 2008; published December 2008
published online 16 December 2008

A random cellular automaton is one in which a cell's behaviour is independent of its previous states. We derive analytical conditions which must be satisfied by random cellular automata and find deterministic and probabilistic cellular automata that satisfy these conditions. Many random cellular automata are seen to have a flow as they are updated through time. We define a correlation current that describes this flow and develop an analytical expression for its size. We compare results from this analytical expression with those from simulation. The randomness in a cell comes from randomness in adjacent cells or from the stochastic nature of update rules. We give an expression for how much randomness comes from each of these two sources.

02.50.-r - Probability theory, stochastic processes, and statistics.
05.50.+q - Lattice theory and statistics (Ising, Potts, etc.).

© EPLA 2008