particular rule, then one will always eventually be able to find a set of localized structures that is rich enough to support universality.

Part (c) shows the instructions that are executed for the first 400 times that one of the registers is decreased to zero. … If one value is n , then the next value is 3n/2 if n is even, and (3n+1)/2 if n is odd.

Mathematical Constants The last few sections [ 2 , 3 , 4 ] have shown that one can set up all sorts of systems based on numbers in which great complexity can occur. … One might suppose that at some level it must be quite simple and regular.

But what all the rules have in common is that they involve replacing one black square by two or more smaller black squares. … The basic answer, much as we saw in one-dimensional substitution systems on page 85 , is some form of interaction between different elements—so that the replacement for a particular element at a given step can depend not only on the characteristics of that element itself, but also on the characteristics of other neighboring elements.

But the key idea that I had nearly twenty years ago—and that eventually led to the whole new kind of science in this book—was to ask what happens if one instead just looks at simple arbitrarily chosen programs, created without any specific task in mind. … For all one need do is just set up a sequence of possible simple programs, and then run them and see how they behave.

In each case there is a dot that can be in one of six possible positions. … A simple system that contains a single dot which can be in one of six possible positions.

Randomness in Class 3 Systems When one looks at class 3 systems the most obvious feature of their behavior is its apparent randomness. … The pictures below now compare what happens in the rule 30 cellular automaton from page 27 if one starts from random initial conditions and from initial conditions involving just a single black cell.

And the way to tell this is that for small repetition periods there is a systematic procedure that allows one to find absolutely all structures with a given period. … And for all repetition periods up to 10—with the exception of 7—at least one fixed or moving structure ultimately turns out to exist.

And so long as the boundaries of the regions do not get stuck—as happens in many one-dimensional cellular automata—the result is that whichever color was initially more common eventually takes over the whole system. A one-dimensional cellular automaton in which the density of black cells obtained after a large number of steps changes discretely when the initial density of black cells is continuously increased.

below, is that some process can start at one point in space and then progressively spread, doing the same thing at every point it reaches. … Homogenous growth from a single point is one straightforward way that uniformity in space can be produced, here illustrated in a mobile automaton and a cellular automaton.