[No text on this page] The universal cellular automaton emulating rule 30. A total of 848 steps in the evolution of the universal cellular automaton are shown, corresponding to 16 steps in the evolution of rule 30.

Rules (a) and (b) act like neighbor-independent substitution systems of the type discussed on page 84 , and yield exponentially growing tree-like causal networks. The plots at the bottom show the growth rates of the patterns produced by rules (f) and (g). In the case of rule (f) the pattern turns out to be repetitive, with a period of 796 steps.

Traditional intuition suggests that to be able to do sophisticated computations one would inevitably need a system with complicated underlying rules. But what I have shown in this book is that this is not the case, and that in fact even systems with extremely simple rules—like the rule 110 cellular automaton—can often be universal, and thus be capable of doing computations as sophisticated as any other system. And the fact that the underlying rules can be so simple vastly expands the kinds of components that can realistically be used to implement them.

But for many rules—including a fair number of class 3 ones—the situation is different. … Rule 126 in general shows class 3 behavior, as on the left. But with the special initial condition on the right it acts like a simple class 2 rule.

And in each case that we have examined what we have found is that remarkably simple rules seem to suffice. Indeed, in most cases the basic rules actually seem to be somewhat simpler than those that operate in many non-biological systems. … But what we have discovered in this book is that when one uses rules that correspond to simple programs, rather than, say, traditional mathematical equations, it is very common to find that different rules lead to quite different—and often highly complex—patterns of behavior.

And if one did this what one would find is that many of the rules exhibit obviously simple repetitive or nested behavior. … And from the result in the previous chapter that rule 110 is universal it follows for example that any rule containing this one must also be universal. But if one is just given an arbitrary rule—

[No text on this page] Examples of three-color totalistic rules with highly complex behavior showing a mixture of regularity and irregularity. The partitioning into identifiable structures is similar to what we saw in rule 110 on page 32 .

With most rules, systems like cellular automata do not usually exhibit such conservation laws. But just as with reversibility, it turns out to be possible to find rules that for example conserve the total number of black cells appearing on each step. … The behavior of the rules shown here is simple enough that in each case it is fairly obvious how the number of black cells manages to stay the same on every step.

But with next-nearest-neighbor rules, more complicated examples become possible, as the pictures below demonstrate. … Examples of cellular automata with next-nearest-neighbor rules whose evolution conserves the total number of black cells. … Among the 4,294,967,296 possible next-neighbor rules, only 428 exhibit the kind of conservation property shown here.

And the picture below shows what happens if one just uses a simple geometrical rule to replace each black square by two smaller black squares. … The general idea of building up patterns by repeatedly applying geometrical rules is at the heart of so-called fractal geometry. … Note that in applying the rule to a particular square, one must take account of the orientation of that square.