In each case knowing the final outcome is equivalent to deciding what will eventually happen to the pattern generated by the cellular automaton evolution.

[No text on this page] Universality in arithmetic, illustrated by an integer equation whose solutions in effect emulate the rule 110 universal cellular automaton from Chapter 11 .

Computer experiments on various cellular automata and related systems were given as examples of how this might work. … This is a k = 8 2D cellular automaton in which toppling of sand above a critical slope is captured by updating an array of relative sand heights s according to the rule SandStep[s_]:= s + ListConvolve[ {{0, 1, 0}, {1, -4, 1}, {0, 1, 0}}, UnitStep[s - 4], 2, 0] Starting from any initial condition, the rule eventually yields a fixed configuration with all values less than 4, as in the picture below. … The system can be generalized to d dimensions as a k = 4d cellular automaton with 2d final values.

Cellular automaton [Boolean] formulas See page 869 .

[Turing] machine 596440 For any list of initial colors init , it turns out that successive rows in the first t steps of the compressed evolution pattern turn out to be given by NestList[Join[{0}, Mod[1 + Rest[FoldList[Plus, 0, #]], 2], {{0}, {1, 1, 0}} 〚 Mod[Apply[Plus, #], 2] + 1] 〛 &, init, t] Inside the right-hand part of this pattern the cell values can then be obtained from an upside-down version of the rule 60 additive cellular automaton, and starting from a sequence of 1 's the picture below shows that a typical rule 60 nested pattern can be produced, at least in a limited region.

(Examples include evaluating standard mathematical functions and simulating the evolution of cellular automata and Turing machines.) • NP (non-deterministic polynomial time): solutions can be checked in polynomial time. (Examples include many problems based on constraints as well as simulating the evolution of multiway systems and finding initial conditions that lead to given behavior in a cellular automaton.) • PSPACE (polynomial space): can be solved with an amount of memory that increases like a polynomial in the input size.

But if one assumes sufficient randomness in microscopic molecular processes they can also be derived from molecular dynamics, as done in the early 1900s, as well as from cellular automata of the kind shown on page 378 , as I did in 1985 (see below ). … One of the key advantages of my cellular automaton approach to fluids is precisely that it does not require any such approximations. … Nevertheless, in the case of cellular automaton fluids, I was able in 1985 to work out the rather complicated next order corrections to the Navier–Stokes equations.

In fact, it turns out that in any cellular automaton it is inevitable that initial conditions which consist just of a fixed block of cells repeated forever will lead to simple repetitive behavior.

The pictures at the top of the next page show a simple example based on a one-dimensional cellular automaton.

At first one might think that one could set up some kind of analog of a cellular automaton and just replace all relevant clusters of nodes at once.