Second-order cellular automaton

In each time step t, for each cell c of the automaton, this function is applied to the neighborhood of c to give a permutation σc.

In this way, every second-order cellular automaton (defined by a function from neighborhoods to permutations) corresponds uniquely to an ordinary (first-order) cellular automaton, defined by a function directly from neighborhoods to states.

[4] Two-state second-order automata are symmetric under time reversals: the time-reversed dynamics of the automaton can be simulated with the same rule as the original dynamics.

[1] The resulting second-order automaton, however, will generally bear little resemblance to the ordinary CA it was constructed from.

[3] Second-order automata may be used to simulate billiard-ball computers[1] and the Ising model of ferromagnetism in statistical mechanics.

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

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