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]