A Universal Cellular Automaton…[No text on this page] Details of how the universal cellular automaton emulates rule 90.

A Universal Cellular Automaton…[No text on this page] Details of how the universal cellular automaton emulates rule 30.

The Rule 110 Cellular Automaton…The Rule 110 Cellular Automaton In previous sections [ 4 , 5 , 6 ] I have shown that a wide variety of different kinds of systems can in principle be made to exhibit the phenomenon of universality. … But this cellular automaton was specifically constructed so as to make its operation easy to understand. … Fairly straightforward modifications to the universal cellular automaton shown earlier in this chapter allow one to reduce the number

The Rule 110 Cellular Automaton…The leading candidate was what I called rule 110—a cellular automaton that we have in fact discussed several times before in this book. … The underlying rules for the rule 110 cellular automaton discussed in this section . … Despite the extreme simplicity of its underlying rules, what this section will demonstrate is that the rule 110 cellular automaton is in fact universal, and is thus in a sense capable of arbitrarily complex behavior.

The Rule 110 Cellular Automaton…In the universal cellular automaton that we discussed earlier in this chapter , each of the various kinds of components involved in its operation had properties that were explicitly built into the underlying rules.

The Rule 110 Cellular Automaton…But the problem with this approach is that it is typically very difficult to see how the various structures that happen to occur in a particular cellular automaton can be assembled into useful components. … But finally it has turned out to be possible to show that the rule 110 cellular automaton is in fact universal.

Note (d) for More Cellular Automata…Common framework [for cellular automaton rules] The Mathematica built-in function CellularAutomaton discussed on page 867 handles general and totalistic rules in the same framework by using ListConvolve[w, a, r + 1] and taking the weights w to be respectively k^Table[i - 1, {i, 2r + 1}] and Table[1, {2r + 1}] .

Note (b) for A Universal Cellular Automaton…Universal cellular automaton The rules for the universal cellular automaton are {{_, 3, 7, 18, _}  12, {_, 5, 7 | 8, 0, _}  12, {_, 3, 10, 18, _}  16, {_, 5, 10 | 11, 0, _}  16, {_, 5, 8, 18, _}  7, {_, 5, 14, 0 | 18, _}  12, {_, _, 8, 5, _}  7, {_, _, 14, 5, _}  12, {_, 5, 11, 18, _}  10, {_, 5, 17, 0 | 18, _}  16, {_, _, x : (11 | 17), 5, _}  x - 1, {_, 0 | 9 | 18, x : (7 | 10 | 16), 3, _}  x + 1, {_, 0 | 9 | 18, 12, 3, _}  14, {_, _, 0 | 9 | 18, 7 | 10 | 12 | 16, x : (3 | 5)}  8 - x, {_, _, _, 8 | 11 | 14 | 17, x : (3 | 5)}  8 - x, {_, 13, 4, _, x : (0 | 18)}  x, {18, _, 4, _, _}  18, {_, _, 18, _, 4}  18, {0, _,4, _, _}  0, {_, _, 0, _, 4}  0, {4, _, 0 | 18, 1, _}  3, {4, _, _, _, _}  4, {_, _, 4, _, _}  9, {_, 4, 12, _, _}  7, {_, 4, 16, _, _}  10, {x : (0 | 18), _, 6, _, _}  x, {_, 2, 6, 15, x : (0 | 18)}  x, {_, 12 | 16, 6, 7, _}  0, {_, 12 | 16, 6, 10, _}  18, {_, 9, 10, 6, _}  16, {_, 9, 7, 6, _}  12, {9, 15, 6, 7, 9}  0, {9, 15, 6, 10, 9}  18, {9, _, 6, _, _}  9, {_, 6, 7, 9, 12 | 16}  12, {_, 6, 10, 9, 12 | 16}  16, {12 | 16, 6, 7, 9, _}  12, {12 | 16, 6, 10, 9, _}  16, {6, 13, _, _, _}  9, {6, _, _, _, _}  6, {_, _, 9, 13, 3}  9, {_, 9, 13, 3, _}  15, {_, _, _, 15, 3}  3, {_, 3, 15, 0 | 18, _}  13, {_, 13, 3, _, 0 | 18}  6, {x : (0 | 18), 15, 9, _, _}  x, {_, 6, 13, _, _}  15, {_, 4, 15, _, _}  13, {_, _, _, 15, 6}  6, {_, _, 2, 6, 15}  1, {_, _, 1, 6, _}  2, {_, 1, 6, _, _}  9, {_, 3, 2, _, _}  1, {3, 2, _, _, _}  3, {_, _, 3, 2, _}  3, {_, 1, 9, 1, 6}  6, {_, _, 9, 1, 6}  4, {_, 4, 2, _, _}  1, {_, _, _, _, x : (3 | 5)}  x, {_, _, 3 | 5, _, x : (0 | 18)}  x, {_, _, x : (1 | 2 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17), _, _}  x, {_, _, 18, 7 | 10, 18}  18, {_, _, 0, 7 | 10, 0}  0, {_, _, 0 | 18, _, _}  9, {_, _, x_, _, _}  x} where the numbers correspond to the icons shown in the main text according to The block in the initial conditions for the universal cellular automaton corresponding to a cell with color a is given by Flatten[{Transpose[{Join[{4, 18(1 - a), 6}, Table[9, {2 2 r + 1 - 3}]], 10 - 3 rtab}], Table[{9, 1}, {r}], 9, 13}] where r is the range of the rule to be emulated ( r = 1 for elementary rules) and rtab is the list of outcomes for that rule (starting with the outcome for {1, 1, (1) ...} ). In general, there are 2 2 r + 1 cases in the rule to be emulated; each block in the universal cellular automaton is 2 (2 2 r + 1 + r + 1) cells wide, and each step in the rule to be emulated corresponds to (3 r + 2) 2 2 r + 1 + 3 r 2 + 7 r + 3 steps in the evolution of the universal cellular automaton.

Note (c) for The Rule 110 Cellular Automaton…History [of universality in 1D cellular automata] The fact that 1D cellular automata can be universal was discussed by Alvy Ray Smith in 1970—who set up an 18-color nearest-neighbor cellular automaton rule capable of emulating Marvin Minsky 's 7-state 4-color universal Turing machine (see page 706 ). ( Roger Banks also mentioned in 1970 a 17-color cellular automaton that he believed was universal.) … In 1989 Kristian Lindgren and Mats Nordahl constructed a 7-color nearest-neighbor cellular automaton that could emulate Minsky's 7,4 universal Turing machine, and showed that in general a rule with s + k + 2 colors could emulate an s -state k -color Turing machine (compare page 658 ). Following my ideas about class 4 cellular automata I had come by 1985 to suspect that rule 110 must be universal.

The Rule 110 Cellular Automaton