So can one in fact construct systems in which there is absolutely no such discreteness? … But how does one give rules for the evolution of such a system? Having no explicit time steps to work with, one must instead just specify the rate at which the gray level changes with time at every point in space.

consists of all configurations in which black cells occur only when they are surrounded on each side by at least one white cell. … For one-dimensional cellular automata, it turns out that there is a rather compact way to summarize all the possible sequences of black and white cells that can occur at any given step in their evolution. … 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 .

For one of the consequences of a program being short is that it has little room for inessential elements. … As a very simple idealization of biological evolution, one can consider a sequence of cellular automaton programs in which each successive program is obtained from the previous one by a random mutation that adds or modifies a single element. … If one starts from extremely short programs, the behavior one gets is at first quite simple.

However certain one might be that simple programs could never do more than produce simple behavior, the pictures on the past few pages [ 32 , 33 , 34 , 35 , 36 , 37 , 38 ] should forever disabuse one of that notion. … Some of them, for example, are part of the regular background, while others are part of one or another localized structure. … Looking just at the original cellular automaton rule one would have no realistic way to foresee all of this.

This kind of self-organization is quite opposite to what one would expect from the Second Law. … To go backwards one would need to set things up so that one absorbs exactly the sequence of structures that were emitted going forwards. If, however, one just lets the emitted structures escape, and never absorbs any other structures, then one is effectively losing information.

There is, as I mentioned above, nothing in principle that requires one to use a computer to study cellular automata. … But the point is that one would be very unlikely to discover the kinds of fundamental phenomena discussed in this chapter just by looking at one or two pictures. … If one already has a clear idea about the basic features of a particular phenomenon, then one can often get more details by doing fairly specific experiments.

In case (a), all networks are allowed except for ones in which a node is connected directly to itself. … With templates that involve nodes out to distance one there are a total of 11 distinct non-trivial cases. … In order to have a meaningful model for the universe, however, what must presumably happen is that essentially just one network can satisfy whatever constraints there are, and this one network must then represent all of the complex spacetime history of our universe.

For one can think of successive slices through a causal network as corresponding to states at successive moments in time. But for there to be something one can reasonably think of as space one has to be able to identify some background features that stay more or less the same—which means that the causal network must yield consistent similarities between states it generates at successive moments in time. One might have thought that if one just had an underlying system which did not change on successive steps then this would immediately yield a fixed structure for space.

But as soon as one allows more than two possible colors, or allows dependence on more than just nearest neighbors, one immediately finds all sorts of further examples of class 4 behavior. … Returning to one dimension, one can ask whether among the 256 elementary cellular automata there are any apart from rule 110 that show even signs of class 4 behavior. As we will see in the next section , one possibility is rule 54.

But what if one somehow restricts oneself to a domain where some particular system seems continuous? Can one even at this level perform more sophisticated computations than in a discrete system? My guess is that for all practical purposes one cannot.