In the main text we considered changing just one square at a time. But one can also change larger numbers of squares, or, for example, interchange whole blocks of squares. … One approach is simulated annealing, in which one starts with this probability being large, and progressively decreases it.

Encodings [for universality] One can prevent an encoding from itself introducing universality by insisting, for example, that it be primitive recursive (see page 907 ) or always involve only a bounded number of steps. One can also do this—as in the rule 110 proof in the previous chapter—by having programs and data be encoded separately, and appear, say, as distinct parts of the initial conditions for the system one is studying.

The correct answer is normally assumed to be the one that in a sense allows the simplest description of all the data. … And I strongly suspect that if one were, for example, to construct similar questions using outputs from many of the simple programs I discuss in this book then unless one had studied almost exactly the cases of such programs used one would never manage to work out the answers.

Conditions for convergence [in string rewriting] One way to guarantee that there is convergence after one step is to require as in the previous section that blocks to be replaced cannot overlap with themselves or each other. … But there are also an additional 20 rules which allow some overlap but which nevertheless yield convergence after one step. … In general, one can consider convergence after any number of steps, requiring that any two strings which have a common ancestor must at some point also have a common successor.

The facing page and the one after show what happens when one chooses different values for the constant that is added.

For one might have assumed that any apparent randomness in the final shape of something like a crystal must always be a consequence of randomness in its original seed, or in the environment in which it grew. … And contrary to what has always been assumed, I suspect that this is actually how the apparent randomness that one sometimes sees in shapes formed by crystalline materials often comes about.

But what changes when one goes from one rule to another is the arrangement of lines entering the picture.

Tag systems [for rule 110] The discussion in the main text and the construction above require a cyclic tag system with blocks that are a multiple of 6 long, and in which at least one block is added at some point in each complete cycle. By inserting k = 6 Ceiling[Length[subs]/6] in the definition of TS1ToCT from page 1113 one can construct a cyclic tag system of this kind to emulate any one-element-dependence tag system.

Compositions of cellular automata One way to construct more complicated rules is from compositions of simpler rules. One can, for example, consider each step applying first one elementary cellular automaton rule, then another.

This system is an example of one that does not in any meaningful way obey the Second Law of Thermodynamics.