By replacing the addition and multiplication that appear in the first picture by other operations one can then get other representations for numbers. … But for π , as well as for cube roots, fourth roots, and so on, the continued fraction representations one gets seem essentially random. … At some level, one can always use symbolic expressions like √ 2 +  √ 3 to represent numbers.

And if one runs the cellular automaton for more steps, as in the picture below, then a rather intricate pattern emerges. But one can now see that this pattern has very definite regularity. For even though it is intricate, one can see that it actually consists of many nested triangular pieces that all have exactly the same form.

investigate what happens if at every step one randomly perturbs the gray level of each cell by a small amount. … What one sees is that when the perturbations are sufficiently large, the sequence of colors of the center cell does indeed change. … And the reason this is important is that in any real experiment, there are inevitably perturbations on the system one is looking at.

But as one goes on, one sees that the rate of improvement gets slower and slower. … The top picture shows one particular run of this procedure.

But it seems likely that as one increases t , no ordinary Turing machine or cellular automaton will ever be able to guarantee to solve the problem in a number of steps that grows only like some power of t . … And for example one might imagine that this would be possible if one were able to use exponentially small components.

Ignoring machines which cannot escape from one of their possible states or which yield motion in only one direction or cells of only one color leaves a total of 237 cases. If one now ignores machines that do not allow the head to move more than one step in one of the two directions, that always yield the same color when moving in a particular direction, or that always leave the tape unchanged, one is finally left with just 25 distinct cases.

One might have thought that after maybe a thousand steps the behavior would eventually resolve into something simple. … Yet given the simplicity of the underlying rule, one would expect vastly more regularities. … For example, one can look at the sequence of colors directly below the initial black cell.

One might have thought—as at first I certainly did—that if the rules for a program were simple then this would mean that its behavior must also be correspondingly simple. … I did what is in a sense one of the most elementary imaginable computer experiments: I took a sequence of simple programs and then systematically ran them to see how they behaved. … But in fact one of the most striking features of the natural world is that

Typical of what happens is what one sees when water flows around a solid object. … But every time one eddy breaks off, another starts to form, so that in the end a whole street of eddies are seen in the wake behind the object. … But this is just one example of the very widespread phenomenon of fluid turbulence.

One circumstantial piece of evidence is that one already sees considerable complexity even in very early fossil organisms. … Whether one looks at fishes, butterflies, molluscs or practically any other kind of organism, it is common to find that across species or even within species organisms that live in the same environment and have essentially the same internal structure can nevertheless exhibit radically different pigmentation patterns. … Two sections from now I will discuss a rather striking potential example of this: if one looks at molluscs of various types, then it turns out that the range of pigmentation patterns on their shells corresponds remarkably closely with the range of patterns that are produced by simple randomly chosen programs based on cellular automata.