Thus, for example, in the rule 30 cellular automaton discussed above, every cell in effect actively contributes to the randomness we see. … And indeed unless the underlying rules for the system somehow explicitly prevent it, it turns out in the end that intrinsic randomness generation will almost inevitably occur—often producing so much randomness that it completely swamps any randomness that might be produced from either of the other two mechanisms.

One might think that the existence of such a discrete transition must somehow be associated with the discrete nature of the underlying cellular automaton rules. But it turns out that it is also possible to get such transitions in systems that have continuous underlying rules.

But what I strongly believe, as I discuss in the next chapter , is that in the end, much as in physical systems, only rather simple forms can actually be obtained in this way, and that when more complex forms are seen they once again tend to be associated not with constraints but rather with the effects of explicit evolution rules—mostly those governing the growth of an individual organism. … Traditional intuition might have made one assume that there must be a direct correspondence between the complexity of observed behavior and the complexity of underlying rules.

Instead, it would be a complete and precise representation of the actual operation of the universe—but all reduced to readily stated rules. … For as we have seen many times in this book, there is often a great distance between underlying rules and overall

almost inevitable consequence of having underlying rules that show causal invariance. … And the point is that causal invariance then implies that the same underlying rules can be used to update the network in all such cases.

The patterns can also be viewed as outputs from a single step in the evolution of two-dimensional block cellular automata in which the rules specify that a block becomes dark if it has the arrangement of cells shown, and becomes light otherwise. … The absence of any dark blocks in many of the cases shown can be viewed as a reflection of constraints introduced by the construction of the images from one-dimensional cellular automaton rules.

Both of the patterns shown on the previous page are rather special in that as well as being generated by substitution systems they can also be produced one row at a time by the evolution of one-dimensional cellular automata with simple additive rules. And in fact the approaches used above can be viewed as direct generalizations of such additive rules to the domain of ordinary numbers.

But one of the central discoveries of this book is that this is far from true—and that actually it is rather common for rules that have extremely simple descriptions to give rise to data that is highly complex, and that has no regularities that can be recognized by any of our standard methods. But as we discussed earlier in this chapter the fact that a simple rule can ultimately be responsible for such data means that at some level the data must contain regularities.

The top row shows how a particular non-deterministic Turing machine behaves with successive sequences of choices for rules to apply. … The left part of each cellular automaton configuration emulates the actual evolution of the Turing machine; a specification of which rules should be applied at each step is progressively fetched from the right and delivered to the position of the head.

IntegerDigits[m, 2, 8]] For rule 22, for example, this means that if the density at a particular step is p , then the density on the next step should be 3 p (1 - p) 2 , and the densities on subsequent steps should be obtained by iterating this function. … The actual density for rule 22 is however 0.35095. … (For rules 90 and 30 the functions obtained after one step are respectively 2 p (1 - p) and p (2 p 2 - 5 p + 3) , both of which turn out to imply correct final densities of 1/2 ).