[Converting from CAs with] more colors Given a rule that involves three colors and nearest neighbors, the following converts each case of the rule to a collection of cases for a rule with two colors: CA3ToCA2[{a_, b_, c_}  d_] := Union[Flatten[Table[Thread[ Partition[Flatten[{l, a, b, c, r} /. coding], 11, 1] 〚 {2, 3, 4} 〛  (d /. coding)], {l, 0, 2}, {r, 0, 2}], 2]] coding = {0  {0, 0, 0}, 1  {0, 0, 1}, 2  {0, 1, 1}} The problem of encoding cells with several colors by blocks of black and white cells is related to standard problems in coding theory (see page 560 ). … Note that the original rule with k colors and r neighbors involves Log[2, k k 2 r + 1 ] bits of information; the two-color rule that emulates it involves Log[2, 2 2 2 s + 1 ] bits.

Self-similarity of additive [cellular automaton] rules The fact that rule 90 can emulate itself can be seen fairly easily from a symbolic description of the rule. Given three cells {a 1 , a 2 , a 3 } the rule specifies that the new value of the center cell will be Mod[a 1 + a 3 , 2] . … It turns out that this argument generalizes (by interspersing k - 1 0's and going for k steps) to any additive rule based on reduction modulo k (see page 952 ) so long as k is prime.

The cellular automaton rule then corresponds to a continuous mapping of this Cantor set to itself (continuity follows from the locality of the rule). … The pictures above show representations of the mappings corresponding to various rules, obtained by plotting Sum[a[t + 1, i] 2 -i , {i, -n, n}] against Sum[a[t, i] 2 -i , {i, -n, n}] for all possible choices of the a[t, i] . … Rule 170 is the classic shift map which shifts all cell values one position to the left without changing them.

Relation to 1D cellular automata A picture that shows the evolution of a 1D cellular automaton can be thought of as a 2D array of cells in which the color of each cell satisfies a constraint that relates it to the cells above according to the cellular automaton rule. … Below this line there would then be a unique pattern corresponding to the application of the cellular automaton rule. But above the line, except for reversible rules, there is no guarantee that any pattern satisfying the constraints can exist.

[State networks for] additive rules The pictures below show networks obtained for the additive cellular automata with rules 60 and 90. … When n is even, the structure is a balanced tree of depth 2^IntegerExponent[n, 2] and degree 2 for rule 60, and depth 2^IntegerExponent[n/2, 2] and degree 4 for rule 90.

A crucial feature of these rules, however, is that they make the system behave in a way that depends sensitively on the details of its initial conditions. In the particular case shown, the rules are simply set up to shift every color one position to the left at each step. … In general, the rules can be more complicated than those shown in the example on the previous page .

Quite possibly there will sometimes be at least some correspondence between the lengths and angles that appear in the rules for overall growth and for the growth of leaves. But in general the details of all these rules will no doubt depend on very specific characteristics of individual plants. … But what the pictures on the previous pages [ 400 , 402 ] demonstrate is that in fact a high degree of complexity can arise in a sense quite effortlessly just as a consequence of following certain simple rules of growth.

Why These Discoveries Were Not Made Before The main result of this chapter —that programs based on simple rules can produce behavior of great complexity—seems so fundamental that one might assume it must have been discovered long ago. … And in fact, to do so requires absolutely no sophisticated ideas from mathematics or elsewhere: all it takes is an understanding of how to apply simple rules repeatedly. … And perhaps one day some Babylonian artifact created using the rule 30 cellular automaton from page 27 will be unearthed.

The result is that the evolution one sees can be intrinsically not reversible, so that all of the various forms of self-organization that we saw earlier in this book in cellular automata that do not have reversible rules can potentially occur. … The result is that it is possible for regions of the universe to become progressively more organized, despite the Second Law, and despite the reversibility of their underlying rules. … But what the pictures on the facing page demonstrate is that even in a completely closed system, where no information at all is allowed to escape, a system like rule 37R still does not follow the uniform trend towards increasing randomness that is suggested by the Second Law.

As an example of what can happen when simple processes are applied to data, the pictures on the facing page show the results of evolution according to various cellular automaton rules, with initial conditions given by the sequences from page 594 . … With these sequences none of the simple cellular automaton rules shown here yield behavior that can readily be distinguished from what is typical. … So from this we must conclude that—just as with all the other methods of perception and analysis discussed in this chapter —statistical analysis, even with some generalization, cannot readily recognize that sequences like (g) and (h) are anything but completely random—even though at an underlying level these sequences were generated by quite simple rules.