Abelian groups are one example. … But with the universal Turing machine from page 707 one gets a group with 14 generators and 52 relations. … Note that groups with just one relation were shown always to have decidable word problems by Wilhelm Magnus in 1932.

But in 1861 Hermann Grassmann showed that such facts could be deduced from more basic ones about successors and induction. … If any single one of the axioms given for reduced arithmetic is removed, universality is lost. … A form of arithmetic in which one allows induction but removes multiplication was considered by Mojzesz Presburger in 1929.

Rules 30 and 45 (as well as other one-sided additive rules) also have the property that all configurations that repeat must consist of a sequence of identical blocks. … In general for one-sided additive rules the number of such configurations increases for large p like k h tx p , where h tx is the spacetime entropy of page 960 . … For rules that do not show at least one-sided additivity there can be an infinite number of configurations that repeat with a given period.

One feature often found is that the average radius of "droplets" increases with time roughly like t 1/3 .

Simulating mobile automata Given a mobile automaton like the one from page 73 with rules in the form used on page 887 —and behavior of any complexity—the following will yield a causal-invariant substitution system that emulates it: Map[StringJoin, Map[{"AAABB", "ABABB", "ABAABB"} 〚 # + 1 〛 &, Map[Insert[# 〚 1 〛 , 2, 2]  Insert[# 〚 2, 1 〛 , 2, 2 + # 〚 2, 2 〛 ] &, rule], {2}], {2}]

Historical notes I have included extensive historical notes in this book in part out of respect for what has gone before, in part to provide context for ideas (and to see how current beliefs came to be as they are) and in part because the steps one goes through in understanding things may track steps that were gone through historically. … Looking at the historical notes in this book one striking feature is how often individuals of significant fame are mentioned—but not for the reason they are usually famous. And perhaps the explanation for this is in part that most of those who one can now see made contributions to the kinds of foundational issues I address were capable enough to have been successful at something—but without the whole context of this book they tended to view the types of results I discuss largely as curiosities, and so never tried to do much with them.

Using the method of page 672 one can construct a URM with 3 registers and 175 instructions (or 2 registers and 4694 instructions) that emulates the universal Turing machine on page 706 . Using work by Ivan Korec from the 1980s and 1990s one can also construct URMs which directly emulate other register machines. An example with 8 registers and 41 instructions is: or {d[4, 40], i[5], d[3, 9], i[3], d[7, 4], d[5, 14], i[6], d[3, 3], i[7], d[6, 2], i[6], d[5, 11], d[6, 3], d[4, 35], d[6, 15], i[4], d[8, 16], d[5, 21], i[1], d[3, 1], d[5, 25], i[2], d[3, 1], i[6], d[5, 32], d[1, 28], d[3, 1], d[4, 28], i[4], d[6, 29], d[3, 1], d[5, 24], d[2, 28], d[3, 1], i[8], i[6], d[5, 36], i[6], d[3, 3], d[6, 40], d[4, 3]} Given any register machine, one first applies the function RMToRM2 from page 1114 , then takes the resulting program and initial condition and finds an initial condition for the URM using R2ToURM[prog_, init_] := Join[init, With[ {n = Length[prog]}, {1 + LE[Reverse[prog] /.

Sometimes these constraints just relate the state of a system at one time to its state at a previous time. … But if the constraints relate different features of a system at one particular time, then they cannot be converted into evolution rules. … And at a formal level, the two cases are so similar that in studying partial differential equations one often starts with an equation, and only later tries to work out whether initial or boundary values are needed in order to get either any solution or a unique solution.

Symbolic systems [and operator systems] By introducing constants (0-argument operators) and interpreting ∘ as function application one can turn any symbolic system such as ℯ [x][y]  x[x[y]] from page 103 into an algebraic system such as ( ℯ ∘ a) ∘ b  a ∘ (a ∘ b) .

The importance of explicitness Looking through this book, one striking difference with most previous scientific accounts is the presence of so many explicit pictures that show how every element in a system behaves.