And from this one might be led to conclude that sequential substitution systems could never produce behavior of any substantial complexity. But having now seen complexity in many other kinds of systems, one might suspect that it should also be possible in sequential substitution systems. And it turns out that if one allows more than two possible replacements then one can indeed immediately get more complex behavior.

So what about other class 4 cellular automata—like the ones I showed at the beginning of this section ? … The structures shown were found by a systematic method similar to the one used to find all sequences that satisfy the constraints on page 268 .

one expects that during the growth of a particular snowflake there should be alternation between tree-like and faceted shapes, as new branches grow but then collide with each other. And if one looks at real snowflakes, there is every indication that this is exactly what happens. … The evolution of a cellular automaton in which each cell on a hexagonal grid becomes black whenever exactly one of its neighbors was black on the step before.

In the top row of pictures—as well as picture (a)—all one sees is a collection of discrete particles bouncing around. But if one zooms out, and looks at average motion of increasingly large blocks of particles—as in pictures (b) and (c)—then what begins to emerge is behavior that seems smooth and continuous—just like one expects to see in a fluid.

one-dimensional blocks. … For even though this pattern is produced by a simple one-dimensional cellular automaton rule, and even though one can see by eye that it contains at least some small-scale regularities, none of the schemes we have discussed up till now have succeeded in compressing it at all.

And indeed the previous page shows that if one looks at the evolution of a one-dimensional slice through each two-dimensional pattern the results one gets are strikingly similar to what we have seen in ordinary one-dimensional cellular automata. … The pictures on pages 179 – 181 show one rule, for example, that does not. … In order to get any kind of growth with this rule one must start with at least three black cells.

So by looking at how these heights grow across the page, one can see whether there is a correspondence with the r d - 1 form that one expects for ordinary d -dimensional space. And indeed in case (g), for example, one sees exactly r 1 linear growth, reflecting dimension 2. Similarly, in case (d) one sees r 0 growth, reflecting dimension 1, while in case (h) one sees r 2 growth, reflecting dimension 3.

And given a particular supposed purpose one potential criterion to use is that the system in a sense not appear to do too much that is extraneous to that purpose. … So what this might suggest is that perhaps one could tell that a system was set up for a given purpose if the system turns out to be in a sense the minimal one that achieves that purpose. … Case (a) in the picture on the next page is a cellular automaton one might construct for this purpose by using ideas from traditional engineering.

But in a system that is based on constraints, there is no such direct procedure, and instead one must in effect always go outside of the system to work out what patterns can occur. … One might think that to demonstrate this would effectively require examining every conceivable pattern on the infinite grid of cells. … In the vast majority of cases, simple repetitive patterns, or mixtures of such patterns, are the only ones that are needed.

If there is no randomness, then the overall forms that one sees tend to reflect the discreteness of the underlying components. … If one starts off with several particles, then at any particular time, each particle will be at a definite discrete position. But what happens if one looks not at the position of each individual particle, but rather at the overall distribution of all particles?