The Threshold of Universality in Cellular Automata…So given a particular elementary cellular automaton one can then ask what other elementary cellular automata it can emulate using blocks up to a certain length. … From the proof of universality that we gave it follows that rule 110 must be able to emulate any other elementary cellular automaton with blocks of some size—but with the actual construction we discussed this size will be quite astronomical. … But although it seems somewhat difficult to emulate the complete evolution of one cellular automaton with another, it turns out to be much easier to emulate fragments of evolution for limited numbers of steps.

And indeed when I first saw class 3 cellular automata I assumed that this was the basic origin of their randomness. … The pictures below now compare what happens in the rule 30 cellular automaton from page 27 if one starts from random initial conditions and from initial conditions involving just a single black cell. Comparison of the patterns produced by the rule 30 cellular automaton starting from random initial conditions and from simple initial conditions involving just a single black cell.

Note (b) for Emulating Other Systems with Cellular Automata…Mobile automata [from cellular automata] Given a mobile automaton with rules in the form used on page 887 , a cellular automaton which emulates it can be constructed using MAToCA[rules_] := Append[Flatten[Map[g, rules]], {_, _, x_, _, _}  x] g[{a_, b_, c_}  {d_, e_}] := {{_, a, b + 2, c, _}  d, If[e  1, {a, b + 2, c, _, _}  c + 2, {_, _, a, b + 2, c}  a + 2]} This specific definition assumes that the mobile automaton has two possible colors for each cell; it yields a cellular automaton with four possible colors for each cell. An initial condition with a single 2 surrounded by 0's corresponds to all cells being white in the mobile automaton.

[No text on this page] More steps in the evolution of the reversible cellular automaton with rule 37R.

The color of any particular square can also be found by feeding the digit sequences of its y and x coordinates to the finite automaton shown. The first example shown corresponds to cellular automaton rule 60; the last two examples correspond respectively to rules 90 and 150. In the top row of examples, the initial condition for the substitution system is a single black square, and the start state for the finite automaton is also its black state.

So how can one find out what these structures are for a particular cellular automaton? … And taking the code 20 cellular automaton from the top of the next page , the page that follows shows what happens in this system with each of the first couple of hundred possible initial conditions. … But having now seen the structure obtained with initial condition 187, we might assume that all subsequent structures that arise in the code 20 cellular automaton must be at least as complicated.

With intrinsic randomness generation, however, there is no such limit: in the cellular automaton above, for example, all one need do to get a longer random sequence is to run the cellular automaton for more steps. … Thus, for example, in the rule 30 cellular automaton discussed above, every cell in effect actively contributes to the randomness we see.

It would have been one thing if we had found an example of a cellular automaton with say four or five colors that turned out to be universal. But what in fact we have seen is that a cellular automaton with one of the very simplest possible 256 rules manages to be universal. … For if one knew only about practical computers and about systems like the universal cellular automaton discussed early in this chapter , then one would probably assume that universality would rarely if ever be seen outside of systems that were specifically constructed to exhibit it.

The idea is to set up an arithmetic statement that can be proved true if the evolution of a cellular automaton from a given initial condition makes a given cell be a given color at a given step, and can be proved false if it does not. By changing numbers in this arithmetic statement one can then in effect sample different aspects of the cellular automaton evolution. And with the cellular automaton being a universal one such as rule 110 this implies that the axioms of arithmetic can support universality.

3n+1 problem as cellular automaton If one writes the digits of n in base 6, then the rule for updating the digit sequence is a cellular automaton with 7 possible colors (color 6 works as an end marker that appears to the left and right of the actual digit sequence): {a_, b_, c_}  If[b  6, If[EvenQ[a], 6, 4], 3 Mod[a, 2] + Quotient[b, 2] /. 0  6 /; a  6] The 3n+1 problem can then be viewed as a question about the existence of persistent structure in this cellular automaton.