Notes

Chapter 11: The Notion of Computation

Section 4: 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

Universal cellular automaton image 1

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, {22 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 22 r + 1 cases in the rule to be emulated; each block in the universal cellular automaton is 2 (22 r + 1 + r + 1) cells wide, and each step in the rule to be emulated corresponds to (3 r + 2) 22 r + 1 + 3 r2 + 7 r + 3 steps in the evolution of the universal cellular automaton.



Image Source Notebooks:

From Stephen Wolfram: A New Kind of Science [citation]