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]