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

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


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