The idea of this model is to build up a cluster of black cells by adding just one new cell at each step. … And despite such changes Patterns produced by generalized aggregation models in which a new cell is added only if (a) it would have only one immediate neighbor (out of four), or (b) it would have either one or four neighbors.

At first one might have thought this must be some kind of temporary issue, that could be overcome with sufficient cleverness. But from the discoveries in this book I have come to the conclusion that in fact it is not, and that instead it is one of the consequences of a very fundamental phenomenon that follows from the Principle of Computational Equivalence and that I call computational irreducibility. If one views the evolution of a system as a computation, then each step in this evolution can be thought of as taking a certain amount of computational effort on the part of the system.

In general one tends to talk of purpose only when doing so allows one to give a simpler description of some aspect of behavior than just describing the behavior directly. But whether one can give a simple description can depend greatly on the framework in which one is operating. … And what this means is that if one saw a system that had the property of generating the digits of π one would be unlikely to think that this could represent a meaningful purpose—unless one happened to be operating in traditional mathematics.

But one example where there is no such direct analogy is a register machine. And at the outset one might not imagine that such a system could ever readily be emulated by a cellular automaton.

To begin the first example, consider what happens if one multiplies by 3/2 , or 1.5, at each step. Starting with 1, the successive numbers that one obtains in this way are 1, 3/2 = 1.5 , 9/4 = 2.25 , 27/8 = 3.375 , 81/16 = 5.0625 , 243/32 = 7.59375 , 729/64 = 11.390625 , ... … Multiplication by 2 turns out to correspond just to shifting all digits in base 2 one position to the left, so that the overall pattern produced in this case is very simple.

Indeed, it seems that the best approach is essentially just to search through many different partial differential equations, looking for ones that turn out to show complex behavior. … Nevertheless, by representing formulas as symbolic expressions with discrete sets of possible components, one can devise at least some schemes for sampling partial differential equations. … Indeed, for a very large fraction of randomly chosen partial differential equations what one finds is that after just a small amount of time, the gray level one gets either becomes infinitely large or starts to vary infinitely quickly in space or time.

And so the picture below shows what one cellular automaton does over the course of ten steps. … But modifying the rule just slightly one can immediately get a different pattern. … The top row in each box gives one of the possible combinations of colors for a cell and its immediate neighbors.

And as a result, the block evolves just like one of the systems of limited size that we discussed on page 255 . … But if one wants a short repetition period, then there is a question of whether there is a block of any size which can produce it. … But for many rules—including a fair number of class 3 ones—the situation is different.

And as a result, the system one is looking at will be subjected to at least some level of random perturbations from the environment. … And what this means is that when intrinsic randomness generation is the dominant mechanism it is indeed realistic to expect at least some level of repeatability in the random behavior one sees in real experiments. … So in all of these cases the randomness one sees cannot reasonably be attributed to randomness that is introduced from the environment—either continually or through initial conditions.

able to exhibit the same level of complexity that one observes for example in many systems in physics. … And one of the important consequences of this is that it suggests that it might be possible to develop a rather general predictive theory of biology that would tell one, for example, what basic forms are and are not likely to occur in biological systems. One might have thought that the traditional idea that organisms are selected to be optimal for their environment would already long ago have led to some kind of predictive theory.