P completeness If one allows arbitrary initial conditions in a cellular automaton with nearest-neighbor rules, then to compute the color of a particular cell after t steps in general requires specifying as input the colors of all 2t + 1 initial cells up to distance t away (see page 960 ). And if one always does computations using systems that have only nearest-neighbor rules then just combining 2t + 1 bits of information can take up to t steps—even if the bits are combined in a way that is not computationally irreducible.

And as a result, the digit sequence obtained always repeats at most every q – 1 steps.

In class 1, the behavior is very simple, and almost all initial conditions lead to exactly the same uniform final state.

The number assigned is such that when written in base 2, it gives a sequence of 0's and 1's that correspond to the sequence of new colors chosen for each of the eight possible cases covered by the rule.

Various representations of numbers from 1 to 30.

Starting from a row of n black cells, 0 black cells survive if n is even, and 1 black cell survives if n is odd.

Even in the last case shown, the arrangement of stripes eventually becomes completely regular, with the n th new stripe being produced at step n 2 + 21n/2 - {6, 5, -4, 3} 〚 Mod[n, 4] + 1 〛 /2 .

The total number of statements on successive rows grows faster than exponentially; for the first few it is 1, 6, 91, 2180, 76138.

And in the first machine, the first register alternates between 0 and 1, while the second remains zero.

2D generalizations [of entropies] Above 1D no systematic method seems to exist for finding exact formulas for entropies (as expected from the discussion at the end of Chapter 5 ).