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]
The past cells affecting the state of a cell at time t in a 2nd-order cellular automatonElementary 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.
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 automataedit
If a cellular automaton has only two states, then there are also only two possible permutations of states: the identity permutation that maps each state to itself, and the permutation that maps each state to the other state. We may identify these two permutations with the two states of the automaton. 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.
If we view the two states as Boolean values, this correspondence between ordinary and second-order automaton can be described simply: the state of a cell of the second-order automaton at time t + 1 is the exclusive or of its state at time t − 1 with the state that the ordinary cellular automaton rule would compute for it.[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 Wolfram code of the base rule.[3]
^ abcMargolus, 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, vol. 1, World Scientific, pp. 232–246.
^ abVichniac, G. (1984), "Simulating physics with cellular automata", Physica D, 10: 96–115, doi:10.1016/0167-2789(84)90253-7.
^ abcdeToffoli, 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.
^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.
January 01, 1970
second, order, cellular, automaton, second, order, cellular, automaton, type, reversible, cellular, automaton, invented, edward, fredkin, where, state, cell, time, depends, only, neighborhood, time, also, state, time, past, cells, affecting, state, cell, time,. 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 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 Contents 1 General technique 2 For two state automata 3 Applications 4 ReferencesGeneral technique editIn 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 sc Then this permutation sc 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 editIf a cellular automaton has only two states then there are also only two possible permutations of states the identity permutation that maps each state to itself and the permutation that maps each state to the other state We may identify these two permutations with the two states of the automaton 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 If we view the two states as Boolean values this correspondence between ordinary and second order automaton can be described simply the state of a cell of the second order automaton at time t 1 is the exclusive or of its state at time t 1 with the state that the ordinary cellular automaton rule would compute for it 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 Wolfram code of the base rule 3 Applications editSecond 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 edit a b c 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 vol 1 World Scientific pp 232 246 a b Vichniac G 1984 Simulating physics with cellular automata Physica D 10 96 115 doi 10 1016 0167 2789 84 90253 7 a b Wolfram Stephen 2002 A New Kind of Science Wolfram Media pp 437 440 452 ISBN 1 57955 008 8 a b c d e 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 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 Retrieved from https en wikipedia org w index php title Second order cellular automaton amp oldid 1217575977, wikipedia, wiki, book, books, library,
