In traditional science the notion of constraints is often introduced in an attempt to summarize the effects of evolution rules. Typically the idea is that after a sufficiently long time a system should be found only in states that are invariant under the application of its evolution rules. … But if one starts these rules from random initial conditions, one typically never gets the pattern of page 211 .

Among the various kinds of underlying systems that I have studied in this book many have no particular locality in their basic rules. … One might choose to consider systems like these just because it seems easier to specify their rules. … In the case of substitution systems for strings, locality of underlying replacement rules immediately implies overall locality of effects in the system.

[Universal] totalistic rules It is straightforward to show that totalistic cellular automata can be universal. Explicit simple candidates include k = 2 , r = 2 rules with codes 20 and 52, as well as the various k = 3 , r = 1 class 4 rules shown in Chapter 3 .

With 3 states and 2 colors, the maximum period is 24, and about 0.37% of rules yield non-repetitive behavior, always nested. (Usually I have not found more complicated behavior in such rules even with initial conditions in which there are both black and white cells, though see page 761 .) With 2 states and 3 colors, the maximum repetition period is again 24, about 0.65% of rules yield non-repetitive behavior, and the 14 rules discussed on page 709 yield more complex behavior.

[Rules implementing] other functions The first three pictures below show rules that yield 3n (no k = 3 rules yield 4n , 5n or n 2 ), and the last picture 2n - 2 (corresponding to doubling with initial conditions analogous to page 639 ).

Apparent simplicity [of laws] Given any rules it is always possible to develop a form of description in which these rules will be considered simple. But what is interesting to ask is whether the underlying rules of the universe will seem simple—or special, say in their elegance or symmetry—with respect to forms of description that we as humans currently use.

If one has shown that various simple rules are universal, then it follows that rules which generalize these must also be universal. But even from this I do not know, for example, how to prove that the density of universal rules cannot decrease when rules become more complicated.

If the rules for a one-element-dependence tag system are given in the form {2, {{0, 1}, {0, 1, 1}}} (compare page 1114 ), the initial conditions for the Turing machine are TagToMTM[{2, rule_}, init_] := With[{b = FoldList[Plus, 1, Map[Length, rule] + 1]}, Drop[Flatten[{Reverse[Flatten[{1, Map[{Map[ {1, 0, Table[0, {b 〚 # + 1 〛 }]} &, #], 1} &, rule], 1}]], 0, 0, Map[{Table[2, {b 〚 # + 1 〛 }], 3} &, init]}], -1]] surrounded by 0 's, with the head on the leftmost 2 , in state 1 . … The different cases in the rules for the tag system are laid out on the left in the Turing machine. … Note that although the Turing machine can emulate any number of colors in the tag system, it can only emulate directly rules that delete exactly 2 elements at each step.

For rule 90 the combination c can be specified as {{1, 0, 1}} , while for rule 150R it can be specified as {{0, 1, 0}, {1, 1, 1}} . All generalized additive rules ultimately yield nested patterns. … Just as for ordinary additive rules on page 1091 , an algebraic analysis for generalized additive rules can be given.

Number of [Turing machine] rules With k possible colors for each cell and s possible states, there are a total of (2 s k) s k possible Turing machine rules. Often many of these rules are immediately equivalent, or can show only very simple behavior (see page 1120 ).