For the top picture the pattern is what would be generated by an additive cellular automaton following rule 90; for the bottom picture it is what would be generated by one following rule 150.

Other models [of mutation] Sequential substitution systems are probably more realistic than cellular automata as models of genetic programs, since elements can explicitly be added to their rules at will. As a rather different approach, one can consider a fixed underlying rule—say a class 4 cellular automaton—with modifications in initial conditions.

Note (f) for More Cellular Automata…Algebraic forms [for cellular automaton rules] The rules here can be expressed in algebraic terms (see page 869 ) as follows: • Rule 30: Mod[p + q + r + q r, 2] • Rule 45: Mod[1 + p + r + q r, 2] • Rule 73: Mod[1 + p + q + r + p r + p q r, 2]

And thus for example the first picture below shows that it can take t 2 steps for a Turing machine that updates just one cell at each step to build up the same pattern as a one-dimensional cellular automaton builds up in t steps by updating every cell in parallel. … But the celebrated P=NP question in computational complexity theory asks whether in general there is some To emulate t steps in the evolution of the cellular automaton takes the Turing machine 2t 2 + 5t - 6 steps.

So what happens in systems like cellular automata? … But in a cellular automaton, every possible arrangement of black and white cells corresponds to a possible state of the system. … The pictures on the next page show the actual repetition periods for various cellular automata.

Implementation [of conserved quantity test] Whether a k -color cellular automaton with range r conserves total cell value can be determined from Catch[Do[ (If[Apply[Plus, CAStep[rule, #] - #] ≠ 0, Throw[False]] &)[ IntegerDigits[i, k, m]], {m, w}, {i, 0, k m - 1}]; True] where w can be taken to be k 2r , and perhaps smaller. Among the 256 elementary cellular automata just 5 conserve total cell value.

In most cellular automata, the behavior obtained after a long time is either largely independent of the initial density, or varies quite smoothly with it. But the special feature of the cellular automata shown on the facing page is that they have two very different stable states—either all white or all black—and when one changes the initial density a discrete transition occurs between these two states. One might think that the existence of such a discrete transition must somehow be associated with the discrete nature of the underlying cellular automaton rules.

So if such processes can correspond to the evolution of systems like cellular automata, then it follows at least formally that differential equations should be able to do in finite time computations that would take a discrete system like a cellular automaton an infinite time to do. But just as it is difficult to make an analog computer faithfully reproduce many steps in a discrete computation, so also it seems likely that it will be difficult to set up differential equations that for arbitrarily long times successfully manage to emulate the precise behavior of systems like cellular automata.

But while we found that such behavior is quite common in cellular automata, what we have seen in this section indicates that it is rather rare in mobile automata. … And this is part of why complex behavior is so much more common in cellular automata than in mobile automata. A generalized mobile automaton in which any number of cells can be active at a time.

Note (d) for Emulating Other Systems with Cellular Automata…Substitution systems [from cellular automata] Given a substitution system with rules in the form such as {1  {0}, 0  {0, 1}} used on page 889 , the rules for a cellular automaton which emulates it are obtained from SSToCA[rules_] := {{b, b, p[x_, _]}  s[x], {_, s[v : (0 | 1)], p[x_, _]}  p[v, x], {_, p[_, y_], _}  s[y], {_, s[v : (0 | 1)], _m}  m[v], {s[0 | 1], m[v : (0 | 1)], _}  s[v], {b, m[v : (0 | 1)], _}  r[v], {_, r[v : (0 | 1)], _}  (Replace[v, rules] /. {{x_}  s[x], {x_, y_}  p[x, y]}), {_r, s[v : (0 | 1)], _}  r[v], {_r, b, _}  m[b], {s[0 | 1], m[b], _}  b, {_, v_, _}  v} where specific values for cells can be obtained from {b  0, s[0]  1, m[0]  2, p[0, 0]  3, r[0]  4, p[0, 1]  5, p[1, 0]  6, r[1]  7, p[1, 1]  8, m[1]  9, m[b]  10, s[1]  11} An initial condition consisting of a single element with color i in the substitution system is represented by m[i] surrounded by b 's in the cellular automaton.