Such systems in general take a string of elements and at each step replace blocks of these elements with other elements according to some definite rule. … The substitution system works by replacing blocks of elements at each step according to the rule shown. … In the case shown here, all the replacements found to fit in a left-to-right scan are carried out at each step.

Growth of Plants and Animals Looking at all the elaborate forms of plants and animals one might at first assume that the underlying rules for their growth must be highly complex. … It is usually only at the tip of a stem that growth can occur, and much of the time all that ever happens is that the stem just gets progressively longer. … At each step every growing stem is replaced by a collection of three new stems according to the rules shown.

Indeed, away from the right-hand edge, all the elements effectively behave as if they were lying on a regular grid, with the color of each element depending only on the previous color of that element and the element immediately to its right. … The substitution systems that we discussed in the previous section work by replacing each element in such a string by a new sequence of elements—so that in a sense these systems operate in parallel on all the elements that exist in the string at each step. … And this setup is now directly analogous to the search-and-replace function of a typical text editor.

If 2r is less than q , the digit generated at that step is 0, and r is replaced by 2r . Otherwise, r is replaced by 2r – q . … In fact, so far as one can tell, all whole numbers other than perfect squares have square roots whose digit sequences appear completely random.

For all one ever need do is to work out the remainder from dividing the position of a particular square by the size of the basic repeating block, and this then immediately tells one how to look up the color one wants. … And in the case shown on the next page the rules for this system are such that they replace each square at each step by a 2×2 block of new squares. … With the particular rules shown, the new squares always have the same color as the old one, except in one specific case: when a black square is replaced, the new square that appears in the upper right is always white.

But what all the rules have in common is that they involve replacing one black square by two or more smaller black squares. And with this kind of setup, it is ultimately inevitable that all the patterns produced must have a completely regular nested structure. … And the result of this has been that in traditional fractal geometry the idea of interaction between elements is not considered—so that all patterns that are produced have a purely nested form.

And at a fundamental level all that matters for such transformations is the structure of expressions. … A rule like a_ ∧ (b_ ∨ ¬ b_)  a can then immediately be applied to part of an expression using Replace . … But in predicate logic rules can be applied only to whole expressions, always in effect using Replace[expr, rules] .

The repetitive structure of picture (a) implies that to reproduce this picture all we need do is to specify the colors in a 49×2 block, and then say that this block should be repeated an appropriate number of times. Similarly, the nested structure of picture (b) implies that to reproduce this picture, all we need do is to specify the colors in a 3×3 block, and then say that as in a two-dimensional substitution system each black cell should repeatedly be replaced by this block. … But the fact that no short description can be found by our usual processes of perception and analysis does not in any sense mean that no such description exists at all.

In the past biology—with all its details of DNA, proteins, ribosomes and so on—has provided our only example of programmable construction on an atomic scale. … And indeed my guess is that the essential features of all sorts of intricate structures that are seen in living systems can actually be reproduced with remarkably simple rules—making it for example possible to use technology to repair or replace a whole new range of functions of biological tissues and organs. … The traditional engineering approach—if it works at all—will almost inevitably give rules that are in effect at least as complicated as the behavior one is trying to get.

New expressions are also created by replacing each possible variable with x ⊼ y , where x and y are new variables, and by setting every possible pair of variables equal in turn. … Pages 818 and 1175 discuss the sequence of all Nand theorems listed in order of increasing complexity.