Yet as of now we only know for certain about fairly few systems that are universal, albeit including ones like rule 110 that have remarkably simple rules. … So why else might systems like rule 30 fail to be universal? … And so we might wonder whether perhaps some other form of regularity could be present that would prevent systems like rule 30 from being universal.

So what about a case like rule 30? … But these structures Examples of localized structures in rule 73. … Examples of patterns produced by rule 30 with repetitive backgrounds.

And indeed, the pictures on the next two pages [ 202 , 203 ] show examples of what can happen if the rules are allowed to depend on the number of distinct nodes reached by following not just one but up to two successive connections from each node. … Examples of network systems with rules that cause different operations to be performed at different nodes. Each rule contains two cases, as shown above.

One way that we can now show this is to demonstrate that combinators can emulate rule 110. … Yet we saw in Chapter 3 that there are symbolic systems with rules even simpler than combinators that still show complex behavior. … A combinator expression that corresponds to the operation of doing one step of rule 110 evolution.

Indeed, the rules for this cellular automaton are in some respects much simpler than for even a rather basic linear congruential generator. … The point is that unlike the rule 30 cellular automaton that we discussed above, linear congruential generators are readily amenable to detailed mathematical analysis. … And indeed the existence of such simple rules is crucial in making it plausible that the general mechanism of intrinsic randomness generation can be widespread in nature.

But from the discoveries in this book we now know that even when the underlying rules for a system are simple, its overall behavior can still be immensely complex. … If the structures corresponding to different particles are isolated, then the underlying rules will make them persist. But if they somehow overlap, these same rules will usually make some different configuration of particles be produced.

And Chapter 6 showed that self-organization is actually extremely common even among systems with simple rules. … Yet it seemed that they needed highly complex rules—not unlike those found in actual living cells. … The same basic self-reproduction phenomenon occurs in elementary rule 90, as well as in essentially any other additive rule, in any number of dimensions.

The maximum repetition period for rule 90 is 2 (n - 1)/2 - 1 . For rule 30, the peak repetition periods are of order 2 0.63 n , while for rule 45, they are close to 2 n (for n = 29 , for example, the period is 463,347,935, which is 86% of the maximum possible). For rule 110, the peaks seem to increase roughly like n 3 .

But after searching through perhaps 50,000 rules, one finally comes across a rule of the kind shown below—in which the compressed pattern exhibits very much the same kind of apparent randomness that we saw in cellular automata like rule 30. … But after searching through a few million rules, I finally found the example shown on the facing page .

[No text on this page] More steps in the evolution of continuous cellular automata with the same kind of rules as on the previous page . … Note the presence of discrete localized structures even though the underlying rules for the system involve continuous gray levels.