And if one does this, one immediately gets all sorts of fairly complicated patterns that are often not just purely nested—as illustrated in the pictures on the next page . In Chapter 3 we discussed both ordinary one-dimensional substitution systems, in which every element is replaced at each step, and sequential substitution systems, in which just a single block of elements are replaced at each step. … The details of each pattern are different, but in all cases the patterns have a nested overall structure.

And in addition, one cannot have replacements Network evolution in which each node is replaced at each step by a fixed cluster of nodes. … Examples of rules that involve replacing clusters of nodes in a network by other clusters of nodes. All these rules preserve the planarity of a network.

[No text on this page] Examples of network evolution according to the same basic underlying rules as on page 511 , but now with all possible clusters of nodes that do not overlap being replaced at each step.

Indeed, just like patterns produced by one-dimensional substitution systems on page 83 , all the patterns shown here ultimately have a simple nested structure. … The basic reason is that at every step the rules for the substitution system simply replace each black square with several smaller black squares. And on subsequent steps, each of these new black squares is then in turn replaced in exactly the A two-dimensional substitution system in which each square is replaced by four smaller squares at every step according to the rule shown on the left.

Substitution Systems One of the features that cellular automata, mobile automata and Turing machines all have in common is that at the lowest level they consist of a fixed array of cells. … In the cases on the facing page , I start from a single element represented by a long box going all the way across the picture. … Examples of substitution systems with two possible kinds of elements, in which at every step each kind of element is replaced by a fixed block of new elements.

In all cases, the systems are started from the initial string BAB . The black dots indicate the elements that are replaced at each step.

The reason for this is that the basic rules we used specify that every single element should be replaced by at least one new element. … What I do here is simply to divide the whole width of the picture equally among all elements that appear at each step. Note that on every step the rightmost element is always dropped, since no rule is given for how to replace it.

And with this setup, if the underlying rules replace each block by one that contains the same number of black cells, it is inevitable that the system as a whole will conserve the total number of black cells. … The system works by partitioning the sequence of cells that exists at each step into pairs, then replacing these pairs by other pairs according to the rule shown. … It so happens that all but the second of the rules shown here not only conserve the total number of black cells but also turn out to be reversible.

For all of them are ultimately set up just to evolve progressively from one state to the next. … In multiway systems, however, A very simple multiway system in which one element in each sequence is replaced at each step by either one or two elements. The main feature of multiway systems is that all the distinct sequences that result are kept.

At each step it compares the values of r and s , and if r is larger than s it replaces r and s by 4r – 4s – 1 and 2s + 1 respectively; otherwise it replaces them just by 4r and 2s . … Despite their simple definition, all these sequences seem for practical purposes random.