For even a one-dimensional cellular automaton can be viewed as updating an infinite sequence of cells at every step in its evolution.

So what about more complex patterns, like the rule 30 cellular automaton pattern at the bottom of the page ?

And in a class 4 cellular automaton such as rule 110 one can readily shortcut the process of evolution for at least a limited number of steps in places where there happen to be only a few well-separated localized structures present.

But for such patterns to yield meaningful examples of computational reducibility it must also be possible to produce them by some process of evolution—say by repeated application of a cellular automaton rule.

The picture on the facing page shows that one can construct an integer equation whose solutions represent the behavior of a system like a cellular automaton.

My own work on cellular automata in 1981 emerged in part from thinking about self-gravitating systems (see page 880 ) where it seemed conceivable that there might be very basic rules quite different from those usually studied in statistical mechanics. And when I first generated pictures of the behavior of arbitrary cellular automaton rules, what struck me most was the order that emerged even from random initial conditions. But while it was immediately clear that most cellular automata do not have the kind of reversible underlying rules assumed in traditional statistical mechanics, it still seemed initially very surprising that their overall behavior could be so elaborate—and so far from the complete orderlessness one might expect on the basis of traditional ideas of entropy maximization.

(Any cellular automaton rule with an n -cell neighborhood corresponds to such a function; digit sequences in rule numbers correspond to explicit tables of values.)

Note (d) for Computations in Cellular Automata…[Rules for the] primes cellular automaton The rules are {{13, 3, 13}  12, {6, _, 4}  15, {10, _, 3 | 11}  15, {13, 7, _}  8, {13, 8, 7}  13, {15, 8, _}  1, {8, _, _}  7, {15, 1, _}  2, {_, 1, _}  1, {1, _, _}  8, {2 | 4 | 5, _, _}  13, {15, 2, _}  4, {_, 4, 8}  4, {_, 4, _}  5, {_, 5, _}  3, {15, 3, _}  12, {_, x : (2 | 3 | 8), _}  x, {_, x : (11 | 12), _}  x - 1, {11, _, _}  13, {13, _, 1 | 2 | 3 | 5 | 6 | 10 | 11}  15, {13, 0, 8}  15, {14, _, 6 | 10}  15, {10, 0 | 9 | 13, 6 | 10}  15, {6, _, 6}  0, {_, _, 10}  9, {6 | 10, 15, 9}  14, {_, 6 | 10, 9 | 14 | 15}  10, {_,6|10,_}  6, {6 | 10, 15, _}  13, {13 | 14, _, 9 | 15}  14, {13 | 14, _, _}  13, {_, _, 15}  15, {_, _, 9 | 14}  9, {_, _, _}  0} and the initial conditions consist of {10, 0, 4, 8} surrounded by 0 's.

And in a system like a cellular automaton a halting problem can be set up by asking whether a cell at a particular position ever turns a particular color, or whether, more globally, the complete state of the system ever reaches a fixed point and no longer changes.

The S-box that implements each substitution works much like a single step of a cellular automaton. … My cellular automaton cryptographic system is one of the very few fundamentally different systems to have been introduced in recent years.