Notes

Chapter 11: The Notion of Computation

Section 5: Emulating Other Systems with Cellular Automata


RAM [emulated with cellular automata]

The rules for the cellular automaton shown here are

{{2, 4 | 8, 2 | 11, _, _} 2, {11 | 10, 4 | 8, 2 | 11, _, _} 11, {2, 4 | 8, _, _, _} 10, {11 | 10, 4 | 8, _, _, _} 2, {2, 0, _, _, _} 2, {11, 0, _, _, _} 11, {3 | 7 | 6, _, 10, _, _} 1, {x : (3 | 7 | 6), _, _, _, _} x, {_, _, 6, 4, 10} 5, {_, _, 6, 8, 10} 9, {_, 3, _, 10, _} 4, {_, 7, _, 10, _} 8, {_, _, 1, _, x : (5 | 9)} x, {1, _, _, _, _} 1, {_, _, 1, _, _} 1, {_, _, _, _, 1} 1, {_, _, x : (4 | 8 | 0), _, _} x}

The initial conditions are divided into two parts: instructions on the left and memory on the right. Given a list of 0 and 1 values for successive memory locations, the right-hand initial conditions are Flatten[list /. {1 {8, 1}, 0 {4, 1}}]. To access location n the left-hand initial conditions must contain Flatten[{0, i, IntegerDigits[n, 2] /. {1 {0, 11}, 0 {0, 2}}}] inserted in a repetitive {0, 1} background. If i is 7, a 1 will be written to location n; if it is 3, a 0 will be written; and if it is 6, the contents of location n will be read and sent back to the left.

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