Symbolic systems [emulating cellular automata]

Given the rules for an elementary cellular automaton in the form used on page 867 (with {0, 0, 0}  0), the following will construct a symbolic system which emulates it:

Flatten[{Array[(p[x_][#1][#2][#3]  p[x[{##} /. rules]][#2][#3]) &, {2, 2, 2}, 0] /. {0  p, 1  q}, {r[x_]  p[r[p][p]][x], p[x_][p][p][r]  x[p][p][r]}}]

The initial condition for the symbolic system is given by

Fold[#1[#2] &, r[p][p], init /. {0  p, 1  q}][p][p][r]

Step t in the cellular automaton corresponds to step t (t + Length[init] + 3) in the symbolic system.

Note that the succession of states shown here depends on the detailed order in which rules are applied (see page 898). It is also possible to construct symbolic systems with the so-called confluence property, in which results from any fixed number of steps of cellular automaton evolution can be found by applying rules in any possible order (see page 1036).