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. … As we will see on page 225 some cellular automata evolve to invariant configurations from any initial conditions, but most do not.

Surjectivity and injectivity [of cellular automaton maps] One can think of a cellular automaton rule as a mapping (endomorphism) from the space of possible states of the cellular automaton to itself. … Even when a cellular automaton mapping is surjective, it is still often many-to-one, in the sense that several input states can yield the same output state. … And in such a case the cellular automaton mapping is one-to-one or bijective (an automorphism).

Examples of one-dimensional cellular automata which exhibit a symmetry between space and time. Each picture can be generated by starting from initial conditions at the top, and then just evolving down the page repeatedly applying the cellular automaton rule.

And in Mathematica—ever since it was first released— Random[Integer] has generated 0's and 1's using exactly the rule 30 cellular automaton. The way this works is that every time Random[Integer] is called, another step in the cellular automaton evolution is performed, and the value of the cell in the center is returned. … Another issue is that if one always ran the cellular automaton from page 315 with the particular initial condition shown there, then one would always get exactly the same sequence of 0's and 1's.

But what I have shown in this book is that this is not the case, and that in fact even systems with extremely simple rules—like the rule 110 cellular automaton—can often be universal, and thus be capable of doing computations as sophisticated as any other system. … For while it is quite implausible that some simple chemical process could successfully assemble a traditional computer out of atoms, it seems quite plausible that this could be done for something like a rule 110 cellular automaton. Indeed, it seems likely that a system could be set up in which just one or a few atoms would correspond to a cell in a system like a cellular automaton.

Audio representation [of cellular automata] A step in the evolution of a cellular automaton can be represented as a sound by treating each cell like a key on a piano, with the key taken to be pressed if the cell is black. This yields a chord such as Play[Evaluate[Apply[Plus, Flatten[Map[Sin[1000 # t] &, N[2 1/12 ]^Position[list, 1]]]]], {t, 0, 0.2}] A sequence of such chords can sometimes provide a useful representation of cellular automaton evolution.

Maximum periods [in cellular automata] A cellular automaton with n cells and k colors has k n possible states, but if the system has cyclic boundary conditions, then the maximum repetition period is smaller than k n . The reason is that different states of the cellular automaton have different symmetry properties, and thus cannot be on the same cycle. In particular, if a state of a cellular automaton has a certain spatial period, given by the minimum positive m for which RotateLeft[list, m]  list , then this state can never evolve to one with a larger spatial period.

The second set of pictures below show examples of other cellular automata that exhibit the same basic phenomenon. … The facing page shows cellular automata that exhibit slightly more complicated behavior. … A cellular automaton that evolves to a simple uniform state when started from any random initial condition.

Note (h) for Cellular Automata…In general, there is no need for individual cells in a cellular automaton to have the same orientation. … Note that even though individual cells are pentagonal, large-scale cellular automaton patterns usually have 2-, 4- or 8-fold symmetry.) … (Large-scale cellular automaton patterns here can have 5-fold symmetry.)

Cellular Automata…Successive steps in the evolution of a two-dimensional cellular automaton whose rule specifies that a particular cell should become black if any of its neighbors were black on the previous step. … Steps in the evolution of a two-dimensional cellular automaton whose rule specifies that a particular cell should become black if exactly one or all four of its neighbors were black on the previous step, but should otherwise stay the same color.