Second order cellular automaton

From Wikipedia, the free encyclopedia

The past cells affecting the state of a cell at time t in a 2^nd order cellular automaton

Elementary CA rule 18 (left) and its 2^nd order counterpart (right). Time runs downwards. Note the up/down asymmetric triangles in the nonreversible rule.

A second order cellular automaton is a reversible cellular automaton (CA) where the state of a cell at time t depends not only on its neighborhood at time t-1, but also on its state at time t-2. Specifically, the neighborhood at t-1 is used to choose a function f_n that maps the state of the cell at time t-2 to its state at time t. As long as each function f_n is invertible, it follows that the resulting automaton is reversible, regardless of how the functions are chosen.

In particular, for two-state cellular automata, any ordinary CA rule can be turned into a second order rule by xor-ing the new state of each cell at time t with its past state at time t-2. In fact, all two-state second order rules may be produced in this way. The resulting second order automaton, however, will generally bear little resemblance to the ordinary CA it was constructed from. Second order rules constructed in this way are commonly denoted by appending an "R" to the number or code of the base rule.

Second order CA can be implemented quite easily and efficiently. The need to remember the state of cells at t-2 is not nearly as much of a burden as it may seem, since most conventional CA implementations must use some form of double buffering anyway. Converting a conventional CA implementation into a second order one may be as simple as replacing one assignment operation with an XOR.

[edit] References

• Wolfram, Stephen, 2002. A New Kind of Science, pp. 437-440, 452. Wolfram Media. ISBN 1-57955-008-8.