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]

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]

La dinámica temporal inversa de un autómata de segundo orden puede describirse mediante otro autómata de segundo orden con el mismo vecindario, en el que la función g que asigna vecindarios a permutaciones proporciona la permutación inversa a f . Es decir, en cada vecindario posible N , f ( N ) y g ( N ) deben ser permutaciones inversas. Con esta regla inversa, el autómata descrito por la función g calcula correctamente la configuración en el instante t − 1 a partir de las configuraciones en los instantes t y t + 1. Dado que todo autómata de segundo orden puede invertirse de esta manera, se deduce que todos son autómatas celulares reversibles , independientemente de la función f que se elija para determinar la regla del autómata. ^{[ 4 ]}

Si un autómata celular tiene solo dos estados, entonces también hay solo dos permutaciones posibles de estados: la permutación identidad que asigna cada estado a sí mismo, y la permutación que asigna cada estado al otro estado. Podemos identificar estas dos permutaciones con los dos estados del autómata. De esta manera, todo autómata celular de segundo orden (definido por una función de vecindarios a permutaciones) corresponde de forma única a un autómata celular ordinario (de primer orden), definido por una función directamente de vecindarios a estados. ^{[ 4 ]} Los autómatas de segundo orden de dos estados son simétricos bajo inversiones temporales: la dinámica del autómata con el tiempo invertido puede simularse con la misma regla que la dinámica original.

Si consideramos los dos estados como valores booleanos , esta correspondencia entre el autómata ordinario y el de segundo orden puede describirse de forma sencilla: el estado de una celda del autómata de segundo orden en el instante t + 1 es la disyunción exclusiva de su estado en el instante t − 1 con el estado que la regla del autómata celular ordinario calcularía para ella. ^{[ 4 ]} De hecho, todas las reglas de segundo orden de dos estados pueden producirse de esta manera. ^{[ 1 ]} Sin embargo, el autómata de segundo orden resultante generalmente tendrá poca semejanza con el autómata celular ordinario del que se construyó. Las reglas de segundo orden construidas de esta manera son nombradas por Stephen Wolfram añadiendo una "R" al número o código Wolfram de la regla base. ^{[ 3 ]}

Los autómatas de segundo orden pueden usarse para simular computadoras de bolas de billar ^{[ 1 ]} y el modelo de Ising del ferromagnetismo en mecánica estadística . ^{[ 2 ] [ 4 ]} También pueden usarse para criptografía . ^{[ 5 ]}