respects they seem far more random than patterns produced by systems like rule 110 that we already know are universal. … For I was quite certain that even though I saw behavior that seemed to me complex the simplicity of the underlying rules must somehow ultimately lead to great regularity in it. … Explaining the Phenomenon of Complexity Early in this book I described the remarkable discovery that even systems with extremely simple underlying rules can produce behavior that seems to us immensely complex.

At first we might assume that our brains and mathematical methods would always be capable of vastly greater computational sophistication than systems based on simple rules—and that as a result the behavior of such systems would inevitably seem to us fairly simple. … So this means that even though a system may have simple underlying rules its process of evolution can still computationally be just as sophisticated as any of the processes we use for perception and analysis. And this is the fundamental reason that systems with simple rules are able to show behavior that seems to us complex.

But it seems likely that the individual steps in each train of thought follow quite definite underlying rules. And the crucial point is then that I suspect that the computation performed by applying these rules is often sophisticated enough to be computationally irreducible—with the result that it must intrinsically produce behavior that seems to us free of obvious laws. … In the past it has normally been assumed that these phenomena occur only in quite special systems, and not, for example, in typical systems with simple rules or of the kind that might be seen in nature.

[Circularity in] other rules The pictures below show patterns generated after 10,000 steps with several rules, starting respectively from rows of 7, 6, 7 and 11 cells (compare pages 177 and 181 ). … In the second rule shown, the interior of the pattern always continues to change; in the others it remains essentially fixed.

Rule 150 This rule can be viewed as an analog of rule 90 in which the values of three cells, rather than two, are added modulo 2. Corresponding to the result on page 870 for rule 90, the number of black cells at row t in the pattern from rule 150 is given by Apply[Times, Map[(2 # + 2 - (-1) # + 2 )/3 &, Cases[Split[IntegerDigits[t, 2]], k:{1 ..}  Length[k]]]] There are a total of 2 m Fibonacci[m+2] black cells in the pattern obtained up to step 2 m , implying fractal dimension Log[2, 1 + Sqrt[5]] .

Additive [cellular automaton] rules Of the 256 elementary cellular automata 8 are additive: {0, 60, 90, 102, 150, 170, 204, 240} . All of these are either trivial or essentially equivalent to rules 90 or 150. … As discussed on page 955 , any rule based on addition modulo k must yield a nested pattern, and it therefore follows that any rule that is additive must give a nested pattern, as in the examples below.

Indeed, for period p , the length of blocks required is at most 2 2p (or 2 2 p r for range r rules). … In rule 90 (as well as other additive rules such as 60 and 150) any period can occur, but all configurations that repeat must consist of a sequence of identical blocks. … Rules 30 and 45 (as well as other one-sided additive rules) also have the property that all configurations that repeat must consist of a sequence of identical blocks.

Map[Reverse, rules] . … In most cases, however, introducing these kinds of slightly more complicated encodings does not fundamentally seem to expand the set of rules that a given rule can emulate. … And so, for example, with the setup shown in the main text, rule 54 can emulate rule 0 only with blocks of length b = 6 .

(The rule numbers here follow the scheme on page 927 with offsets {{-1, 0}, {0, -1}, {0, 1}, {1, 0}} ). Note that even though the underlying rule involves randomness definite geometrical shapes can be produced. An extreme case is rule 2, where only a single neighborhood with a single black cell is allowed, so that growth occurs along a single line.

[No text on this page] Continuous cellular automata with the same kind of rules as on the previous page, but with a variety of different constants being added.