Chapter 5: Two Dimensions and Beyond

Section 7: Systems Based on Constraints

1D cellular automata

In a cellular automaton with k colors and r neighbors, configurations that are left invariant after t steps of evolution according to the cellular automaton rule are exactly the ones which contain only those length 2r + 1 blocks in which the center cell is the same before and after the evolution. Such configurations therefore obey constraints of the kind discussed in the main text. As we will see on page 225 some cellular automata evolve to invariant configurations from any initial conditions, but most do not. (See page 954.)

From Stephen Wolfram: A New Kind of Science [citation]