And then by setting up appropriate rules and choosing initial conditions that contain only one darker cell, one can produce in the cellular automaton an exact emulation of every step in the evolution of a mobile automaton—as in the picture below.

That this must ultimately be the case one can see from the fact that the total number of elements in a substitution system can be multiplied by a factor from one step to the next, while in a cellular automaton the size of a pattern can only ever increase by a fixed amount at each step.

As one example the bottom picture shows how a cellular automaton can be set up to perform repeated multiplication by 3 of numbers in base 2. And the only real difficulty in this case is that carries generated in the process of multiplication may need to be propagated from one end of the number to the other. … Repeated multiplication by 3 in base 2 being performed by a cellular automaton with 11 colors.

At first one sees only simple repetitive behavior. … With initial condition 291 the n th new stripe on the right is produced at step 2n 2 +8n-9 . Even in the last case shown, the arrangement of stripes eventually becomes completely regular, with the n th new stripe being produced at step n 2 + 21n/2 - {6, 5, -4, 3} 〚 Mod[n, 4] + 1 〛 /2 .

and 2 colors. … And it turns out that at least among 2-state 2-color Turing machines this is the only one that computes the function it computes—so that at least if one wants to use a program this simple there is no faster way to do the computation. The three schemes for adding 1 to a number that are used by Turing machines with 2 states and 2 colors.

On each row only statements that have not appeared before are given.

But whenever there is neither just a single active data element nor an obvious sequence of independent execution steps—as for many of the programs in this book—my experience has always been that the only viable choice of interface is a computer language like Mathematica, based essentially on one-dimensional sequences of word-like constructs.

Logic operations and universality Knowing that the circuits in practical computers use only a small set of basic logic operations—often just Nand —it is sometimes assumed that if a particular system could be shown to emulate logic operations like Nand , then this would immediately establish its universality.

Cyclic tag systems [emulating tag systems] From a tag system which depends only on its first element, with rules given as in the note below, the following constructs a cyclic tag system emulating it: TS1ToCT[{n_, subs_}] := With[{k = Length[subs]}, Join[Map[v[Last[#], k] &, subs], Table[{}, {k(n - 1)}]]] u[i_, k_] := Table[If[j  i + 1, 1, 0], {j, k}] v[list_, k_] := Flatten[Map[u[#, k] &, list]] The initial condition for the tag system can be converted using v[list, k] .

One explanation advanced by Albert Einstein was that the only physical laws we can recognize are ones that are easy to express in our system of mathematics.