[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.

Frequency of behavior [in multiway systems] Among multiway systems with randomly chosen rules, one finds about equal numbers that grow rapidly and die out completely.

Note that rules of the kind discussed on page 508 which involve replacing clusters of nodes can only apply when cycles in the cluster match those in the network.

One can also do this—as in the rule 110 proof in the previous chapter—by having programs and data be encoded separately, and appear, say, as distinct parts of the initial conditions for the system one is studying.

Undecidability [of cellular automaton classes] Almost any definite procedure for determining the class of a particular rule will have the feature that in borderline cases it can take arbitrarily long, often formally showing undecidability, as discussed on page 1138 .

One can take the original stem to extend from the point -1 to 0; the rule is then specified by the list b of complex numbers corresponding to the positions of the new tip obtained after one step.

History [of second-order cellular automata] The concept of getting reversibility in a cellular automaton by having a second-order rule was apparently first suggested by Edward Fredkin around 1970 in the context of 2D systems—on the basis of an analogy with second-order differential equations in physics.

But in the early 1980s the cellular automata that I studied I often characterized as being based on logical rules, rather than traditional mathematical ones. However, as we will see on page 806 , traditional logic is in fact in many ways very narrow compared to the whole range of rules based on simple programs that I actually consider in this book.

And even in a case like rule 30 I suspect that the period cannot be found much faster than by tracing nearly 2 n steps of evolution. … But even with an additive rule and nested behavior, the period depends on quantities like MultiplicativeOrder[2, n] , which probably take more like n steps to evaluate.

Note that the evolution rules are highly non-local, and are rather unlike those, say, in a cellular automaton.