For one might have assumed that any program based on simple rules would always lead to behavior that was much too simple to be relevant to most of what we see in nature. But one of the main discoveries of this book is that programs based on simple rules do not always produce simple behavior. And indeed in the past several chapters we have seen many examples where remarkably simple rules give rise to behavior of great complexity.

The picture below shows the rule 30 cellular automaton in which I first identified this mechanism for randomness. The basic rule for the system is very simple. … As we have discussed before, traditional intuition makes it hard to believe that such complexity could arise from such a simple The rule 30 cellular automaton from page 27 that was the first example I found of intrinsic randomness generation.

The pictures on the next page show two examples—the second corresponding to a rule that we saw in a different context at the end of the previous section . … The underlying rule allows four possible colors for each cell. The rule is set up so that whenever a region of black occurs to the left of a region of white, an expanding region of gray appears in between.

As an example, the first set of pictures below show how nested patterns with larger and larger features can be built up by starting with a single black cell, and then following simple additive cellular automaton rules. … Nested patterns built by the evolution of the rule 90 and rule 150 additive cellular automata starting from a single black cell.

But as a rough approximation one can perhaps assume that each element of a solid is either displaced or not, and that the displacements of neighboring elements interact by some definite rule—say a simple cellular automaton rule. … At each step, the color of each cell, which roughly represents the displacement of an element of the solid, is updated according to a cellular automaton rule.

And of the 256 elementary cellular automata with two colors and nearest-neighbor rules, only the six shown below turn out to be reversible. … There are a total of 7,625,597,484,987 cellular automata with three colors and nearest-neighbor rules, and searching through these one finds just 1800 that are reversible. … Examples of some of the 1800 reversible cellular automata with three colors and nearest-neighbor rules.

It turns out that using an extension of the argument above it is always possible to take the rules An example of how the color of any square in a nested pattern can be found from its coordinates by a fairly simple mathematical procedure. … The finite automaton at the bottom right gives a representation of this rule. … The nested pattern can be built up by a 2D substitution system with the rules shown.

And in fact, by using the universality of rule 110 it turns out to be possible to come up with the vastly simpler universal Turing machine shown below—with just 2 states and 5 possible colors. The rule for the simplest Turing machine currently known to be universal, based on discoveries in this book. … An example of how the Turing machine above manages to emulate rule 110.

Indeed, in about five out of every million rules of this kind, one gets patterns with features that seem in many respects random, as in the pictures on the next two pages [ 80 , 81 ]. … And just as in cellular automata, adding more complexity to the underlying rules does not yield behavior that is ultimately any more complex. … There are a total of 4096 rules of this kind.

then it seems that no rule ever gives behavior that is much more complicated than in the picture below. … But about once in every 10,000 randomly selected rules, rather different behavior is obtained. … A sequential substitution system whose rule involves two possible replacements.