When are cellular automata random?

Of the 256 elementary cellular automata, 28 of them exhibit random behavior over time, but spatio-temporal currents still lurk underneath.

EPL 84, 50005 (2008)

J. Coe, S. Ahnert, T. Fink

When are cellular automata random?

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.

More in Surprises from simple rules

  • Physical Review E

    Assessing self-assembly

    The information needed to self-assemble a structure quantifies its modularity and explains the prevalence of certain structures over others.

  • EPL

    Single elimination competition

    In single elimination competition the best indicator of success is a player's wealth: the accumulated wealth of all defeated players.