In the lattice version in physics one typically considers what happens to averages over all possible configurations of a system if one does a so-called blocking transformation that replaces blocks of elements by individual elements. … What I do in the main text can be thought of as carrying out blocking transformations on cellular automata. But only rarely do such transformations yield cellular automata whose rules are of the same type one started from.

Do they also end up having complicated sets of possible persistent structures?

Although their basic rules are more complicated, the cellular automata shown here do not seem to have fundamentally more complicated behavior than the two-color cellular automata shown on previous pages.

The sequential limit [in generalized substitution systems] Even when the order of applying rules does not matter, using the scheme of a sequential substitution system will often give different results. If there is a tree of possible replacements (as in "A"  "AA" ), then the sequential substitution system in a sense does depth-first recursion in the infinite tree, never returning from the single path it takes.

And one immediate slight difference from other class 4 rules that we have discussed is that structures in rule 110 do not exist on a blank background: instead, they appear as disruptions in a regular repetitive pattern that consists of blocks of 14 cells repeating every 7 steps. … But if one looks at blocks of width 41, then such structures do eventually show up, as the picture on page 293 demonstrates. So how do the various structures in rule 110 interact?

In studying basic processes of proof multiway systems seem to do well as minimal idealizations. … For all one need do, as in the pictures at the top of the next page , is to evaluate the expressions for all possible values of each variable, and then to see whether the patterns of results one gets are the same. … But the crucial idea that underlies the traditional approach to mathematical proof is that one should also be able to deduce such results just by manipulating expressions in purely symbolic form, using the rules of an axiom system, without ever having to do anything like filling in explicit values of variables.

So to make this book as broadly accessible as possible what I mostly do is in the main text to discuss ideas as directly as I can—but then in these notes to outline their historical context. Occasionally in the main text I do mention existing ideas—though I try hard to avoid fads that I expect will not be widely remembered within a few years. … No doubt this book will draw the ire of some of those with whose ideas its results do not agree, but much as I might like to do so, I cannot realistically avoid this just by the way I present what I have discovered.

Multiway Systems The network systems that we discussed in the previous section do not have any underlying grid of elements in space. … But in sequential substitution systems the idea was to do just one replacement at each step.

And the behavior obtained never seems to repeat, nor do the networks produced exhibit any kind of obvious nested form. … The pictures on the facing page show what happens if at each step one allows not just a single replacement, but all replacements that do not overlap.

And indeed, this is a first indication of an important general phenomenon: that at least beyond a certain point, adding complexity to the underlying rules for a system does not ultimately lead to more complex overall behavior. … Using more complicated rules may be convenient if one wants, say, to reproduce the details of particular natural systems, but it does not add fundamentally new features.