Notes

Chapter 11: The Notion of Computation

Section 5: Emulating Other Systems with Cellular Automata


Logic circuits [from cellular automata]

The rules for the cellular automaton shown here are

{{0, 1, 1 | 3} -> 1, {0, 3, 3} -> 3, {1, 0, 0 | 1 | 3} -> 1, {1, 1, 3} -> 4,{1, 3, 0} -> 3, {1, 3, 3} -> 2, {2, 1, 3} -> 3, {2, 3, 0} -> 2,{2, 0, _} -> 4, {3, 3, 0} -> 3, {4, 0, 0 | 1 | 2 | 4} -> 2, {4, 3, 3} ->3, {4, 1, 3} -> 1, {4, 3, 0} -> 4, {_, _, _} -> 0}

The initial conditions are given by

Flatten[Block[{And, Or}, Map[{0, 2 (# + 1)}&, expr, {-1}] //. {!x_ :> {0,x,0}, And[x__] :> {0,0,1,0,x,1,3,0,0}, Or[x__] :> {0,0,1,0,x,0,1,3,0}}]]

and in terms of these initial conditions the cellular automaton must be run for Length[list //. {0, x__} -> {x}] - 1 steps in order to find the result.

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