Rule 90

In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. In each time step all values are simultaneously replaced by the XOR of their two neighboring values.^[1] Martin, Odlyzko & Wolfram (1984) call it "the simplest non-trivial cellular automaton",^[2] and it is described extensively in Stephen Wolfram's 2002 book A New Kind of Science.^[3]

When started from a single live cell, Rule 90 has a time-space diagram in the form of a Sierpiński triangle. The behavior of any other configuration can be explained as a superposition of copies of this pattern, combined using the exclusive or function. Any configuration with only finitely many nonzero cells becomes a replicator that eventually fills the array with copies of itself. When Rule 90 is started from a random initial configuration, its configuration remains random at each time step. Its time-space diagram forms many triangular "windows" of different sizes, patterns that form when a consecutive row of cells becomes simultaneously zero and then cells with value 1 gradually move into this row from both ends.

Some of the earliest studies of Rule 90 were made in connection with an unsolved problem in number theory, Gilbreath's conjecture, on the differences of consecutive prime numbers. This rule is also connected to number theory in a different way, via Gould's sequence. This sequence counts the number of nonzero cells in each time step after starting Rule 90 with a single live cell. Its values are powers of two, with exponents equal to the number of nonzero digits in the binary representation of the step number. Other applications of Rule 90 have included the design of tapestries.

Every configuration of Rule 90 has exactly four predecessors, other configurations that form the given configuration after a single step. Therefore, in contrast to many other cellular automata such as Conway's Game of Life, Rule 90 has no Garden of Eden, a configuration with no predecessors. It provides an example of a cellular automaton that is surjective (each configuration has a predecessor) but not injective (it has sets of more than one configuration with the same successor). It follows from the Garden of Eden theorem that Rule 90 is locally injective (all configurations with the same successor vary at an infinite number of cells).