particles in physics one must consider structures on much more complicated and random backgrounds. … Yet at first one might think that such randomness would inevitably disrupt any kind of definite persistent structure. … And if one starts off with a network like the one in the bottom picture that can only be drawn with lines crossing, then what will happen is that the non-planarity of the network will be preserved.

But as soon as one tries to investigate behavior of any substantial complexity, the processes of perception and analysis that one needs to use are no longer so straightforward. And the results one gets can then depend on these processes. … But the point is that if one explicitly studies processes of perception and analysis, then it becomes possible to make quite definite and objective statements even in such cases.

And if one does this then one encounters the phenomenon of undecidability that was identified in the 1930s. … One can try to find out by running the system for a certain number of steps and seeing what happens. And indeed in example (a) this approach works well: in only 36 steps one finds that the pattern

Looking at most textbooks of science and mathematics, one might well conclude that they cannot. But what one must realize is that the systems discussed in these textbooks are usually ones that are specifically chosen to be amenable to fairly complete analysis, and whose behavior is therefore necessarily quite simple. And indeed, as we shall see in this chapter , if one ignores the need for analysis and instead just looks at the results of computer

At the outset one might have thought this would never work. … But one of the main discoveries of this book is that programs based on simple rules do not always produce simple behavior. … One way to get some idea of this is just to look at pictures of natural systems and compare them with pictures of simple programs.

The pictures on the next page show, for example, what happens if one looks at two-dimensional random walks on square and hexagonal lattices. One might expect that the different underlying forms of these lattices would lead to different shapes in overall distributions. … In case (a), each particle moves just one position to the left or right at each step.

One of the defining features of space as we normally experience it is a certain locality that leads most things that happen at some particular position to be able at first to affect only things very near them. … The rule effectively just sorts elements so that black ones come first, and yields the same causal network regardless of what updating scheme is used. Examples of patterns produced by cellular automata, illustrating the fact discussed in Chapter 6 that the edge of each pattern has a maximum slope equal to one cell per step, corresponding to an absolute upper limit on the rate of information transmission—similar to the speed of light in physics.

It is already an achievement to find a universal Turing machine as comparatively simple as the one on the facing page . And indeed in the forty years since this example was found, no significantly simpler one has been found. … But as one might expect from the discoveries in this book, this is far from correct.

With more complicated initial conditions the behavior one sees can sometimes be more complicated, at least for a while—as in the pictures below. … From the universality of rule 110 we know that if one just starts enumerating cellular automata in a particular order, then after going through at most 110 rules, one will definitely see universality. And from other results earlier in this chapter it seems likely that in fact one would tend to see universality even somewhat earlier—after going through only perhaps just ten or twenty rules.

So what happens if one allows more than four states for the head? It turns out that there is almost no change in the kind of behavior one sees. … Once again, it seems that there is a threshold for complex behavior—that is reached as soon as one has at least four states.