Nand and Nor are the only 2-input functions universal in this sense. ( {Equal} can for example reproduce only functions {9, 10, 12, 15} , {Implies} only functions {10, 11, 12, 13, 14, 15} , and {Equal, Implies} only functions {8, 9, 10, 11, 12, 13, 14, 15} .)

The main issue—already mentioned at the beginning of this chapter —is that in this approach the only attribute of numbers that is usually considered significant is their size. … And at least if one looks only at the sizes of numbers, this seems rather mysterious. … For as the pictures at the top of the facing page show, the fact that the numbers which are used as initial conditions differ only by a very small amount in size just means that their first several digits are the same.

And this implies that in choosing initial conditions for a system like the shift map, one should therefore make no distinction between the exact number 1/2 and numbers that are sufficiently close in size to 1/2 . … But as I have discussed above, the only randomness that can actually come out of such a system is randomness that was explicitly put in through the details of its initial conditions. … And indeed—as I will discuss in Chapter 7 —if one looks only at systems like the shift map then it is not clear any new randomness can ever actually be generated.

consists of all configurations in which black cells occur only when they are surrounded on each side by at least one white cell. … At step 2 in the rule 255 example on the facing page , however, the network has only one loop—representing the fact that at this step the only sequences which can occur with this rule are ones that consist purely of black cells, just as we saw on the previous page . The case of rule 4 is slightly more complicated: at step 2, the possible sequences that can occur are now represented by a network with two nodes.

Yet what we saw in the previous section is that in cellular automata not only can the underlying rules be simple, but the initial conditions can also be simple—consisting say of just a single black cell—and still the behavior that is produced can be highly complex. … And the only reasonable way to do this is to expose ourselves to a large number of examples. We have seen so far only a few examples, all in cellular automata.

But so far as one can tell the only types of rules that were tried were ones associated with standard geometry and arithmetic. And using these kinds of rules, only rather simple behavior could be obtained—adequate to explain some of the regularities observed in astronomy, but unable to capture much of what is seen elsewhere in nature. … Needless to say, there were many phenomena that did not readily yield to this approach, but it was generally assumed that if only the necessary calculations could be done, then an explanation in terms of mathematical equations would eventually be found.

humans have historically developed ultimately covers only a tiny fraction of what is possible—notably leaving out the vast majority of systems that I have studied in this book. And if one identifies a feature—such as repetition or nesting—that is common to many possible systems, then it becomes inevitable that this feature will appear not only when intelligence or mathematics is involved, but also in all sorts of systems that just occur in nature. … But such a criterion relies on seeing not only a signal but also the mechanism by which the signal was produced.

In the past biology—with all its details of DNA, proteins, ribosomes and so on—has provided our only example of programmable construction on an atomic scale. … But in my experience there are so many different and unexpected things that can happen with simple programs that ultimately the only way to find what one wants is essentially just to do an exhaustive search of all possibilities. … And in some sense the only difference here is that in the abstract world of simple programs doing a search becomes much more systematic.

The register machine compressed evolution keeps only steps corresponding to every other time the third register gets incremented from zero.

The compressed picture on the left is made by evolving for a million steps, but showing only steps at which the string becomes longer than it has ever been before.