For the most part, however, only Schönfinkel's specific rules were ever used, and only rather specific forms of behavior were investigated. In the 1970s and 1980s there was interest in using combinators as a basis for compilation of functional programming languages, but only fairly specific situations of immediate practical relevance were considered. … (One can always set up the analog of types by having rules only for expressions whose heads have particular structures.)

Yet as it turns out, few regularities have in fact been found, and often the results that have been established tend only to support the idea that the sequence has many features of randomness. … And indeed the only reasonable conclusion seems to be that just as in so many other systems in this book, such sequences of numbers exhibit complexity that somehow arises as a fundamental consequence of the rules by which the sequences are generated.

Cellular Automata The cellular automata that we have discussed so far in this book are all purely one-dimensional, so that at each step, they involve only a single line of cells. … Usually I consider so-called totalistic rules in which the new color of the center cell depends only on the average of the previous colors of its four neighbors, as well as on its own previous color.

For if the only way for intrinsic randomness generation to occur was through very complicated sets of rules, then one would expect that this mechanism would be seen in practice only in a few very special cases.

Indeed, the only way to do it seems to be to lay the balls down carefully one after another. … Typical behavior of two-dimensional cellular automata that leave only the pattern on the right invariant.

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. … And what we have found in this book is that programs are very much the same: some show highly complex behavior, while others show only rather simple behavior.

It is no longer true that their evolution leads only to simple transformations of the initial conditions. … Note that by allowing a total of four rather than two colors, a version of the rule that depends only on the immediately preceding step can be constructed.

But as a simple idealization one can assume that such cells in the end just respond to repeated versions of the basic 2×2 patterns. … In each case, one can think of the resulting patterns as being filtered versions of the original images in which only parts that exhibit particular features are kept. … The comparative sparsity of dark blocks is a consequence of the fact that at any given position a dark block can occur in only one of the 16 cases shown.

And the Principle of Computational Equivalence now implies that this will normally be possible only for rather special systems with simple behavior. … And this means that such systems are computationally irreducible—so that in effect the only way to find their behavior is to trace each of their steps, spending about as much computational effort as the systems themselves.

So far from universality being some rare and special property that exists only in systems that have carefully been built to exhibit it, the Principle of Computational Equivalence implies that instead this property should be extremely common. And among other things this means that universality can be expected to occur not only in many kinds of abstract systems but also in all sorts of systems in nature.