Second-order cellular automaton
A second-order cellular automaton is a type of reversible cellular automaton (CA) invented by Edward Fredkin[1][2] 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.[3]
General technique
In general, the evolution rule for a second-order automaton may be described as a function f that maps the neighborhood of a cell to a permutation on the states of the 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. Then, this permutation σc is applied to the state of cell c at time t − 1, and the result is the state of the cell at time t + 1. In this way, the configuration of the automaton at each time step is computed from two previous time steps: the immediately previous step determines the permutations that are applied to the cells, and the time step before that one gives the states on which these permutations operate.[4]
The reversed time dynamics of a second-order automaton may be described by another second-order automaton with the same neighborhood, in which the function g mapping neighborhoods to permutations gives the inverse permutation to f. That is, on each possible neighborhood N, f(N) and g(N) should be inverse permutations. With this reverse rule, the automaton described by function g correctly computes the configuration at time t − 1 from the configurations at time t and t + 1. Because every second-order automaton can be reversed in this way, it follows that they are all reversible cellular automata, regardless of which function f is chosen to determine the automaton rule.[4]
For two-state automata
If a cellular automaton has only two states, then there are also only two possible permutations of states: the
If we view the two states as
Applications
Second-order automata may be used to simulate billiard-ball computers[1] and the Ising model of ferromagnetism in statistical mechanics.[2][4] They may also be used for cryptography.[5]
References
- ^ doi:10.1016/0167-2789(84)90252-5. Reprinted in Wolfram, Stephen, ed. (1986), Theory and Applications of Cellular Automata, Advanced series on complex systems, vol. 1, World Scientific, pp. 232–246.
- ^ .
- ^ ISBN 1-57955-008-8.
- ^ . See especially section 5.4 "Second-order cellular automata", pp. 238–240. This issue of Physica D was reprinted as Gutowitz, Howard, ed. (1991), Cellular Automata: Theory and Experiment, MIT/North-Holland.
- .