Second-order cellular automaton

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.

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] Specifically, the neighborhood at time t − 1 is used to choose a function fn from some larger set of possible functions, that maps the state of the cell at time t − 2 to its state at time t. As long as each possible function fn 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 computing the exclusive or of what the ordinary rule would compute as the new state of each cell at time t with its past state at time t − 2.[4] In fact, all two-state second-order rules may be produced in this way.[1] 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 named by Stephen Wolfram by appending an "R" to the number or code of the base rule.[3]

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

  1. ↑ 1.0 1.1 1.2 Margolus, N. (1984), "Physics-like models of computation", Physica D 10: 81–95, 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 1, World Scientific, pp. 232–246.
  2. ↑ 2.0 2.1 Vichniac, G. (1984), "Simulating physics with cellular automata", Physica D 10: 96–115, doi:10.1016/0167-2789(84)90253-7.
  3. ↑ 3.0 3.1 Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media, pp. 437–440, 452, ISBN 1-57955-008-8.
  4. ↑ 4.0 4.1 Toffoli, Tommaso; Margolus, Norman (1990), "Invertible cellular automata", Physica D 45: 229–253, doi:10.1016/0167-2789(90)90185-r. 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.
  5. ↑ Chai, Zhenchuan; Cao, Zhenfu; Zhou, Yuan (2005), "Encryption based on reversible second-order cellular automata", Parallel and Distributed Processing and Applications (ISPA 2005 Workshops), Lecture Notes in Computer Science, Springer, pp. 350–358, doi:10.1007/11576259_39.