Un autómata celular de segundo orden es un tipo de autómata celular reversible (AC) inventado por Edward Fredkin [1] [2] donde el estado de una célula en el tiempo t depende no solo de su vecindad en el tiempo t − 1 , sino también de su estado en el tiempo t − 2 . [3]
En general, la regla de evolución para un autómata de segundo orden puede describirse como una función f que asigna la vecindad de una célula a una permutación de los estados del autómata. En cada paso de tiempo t , para cada célula c del autómata, esta función se aplica a la vecindad de c para dar una permutación σ c . Luego, esta permutación σ c se aplica al estado de la célula c en el tiempo t − 1 , y el resultado es el estado de la célula en el tiempo t + 1 . De esta manera, la configuración del autómata en cada paso de tiempo se calcula a partir de dos pasos de tiempo anteriores: el paso inmediatamente anterior determina las permutaciones que se aplican a las células, y el paso de tiempo anterior a ese da los estados en los que operan estas permutaciones. [4]
La dinámica temporal inversa de un autómata de segundo orden puede ser descrita por otro autómata de segundo orden con el mismo vecindario, en el que la función g que asigna vecindarios a permutaciones da la permutación inversa a f . Es decir, en cada posible vecindario 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 tiempo t − 1 a partir de las configuraciones en el tiempo t y t + 1 . Debido a que cada autómata de segundo orden puede invertirse de esta manera, se deduce que todos son autómatas celulares reversibles , independientemente de qué función f se elija para determinar la regla del autómata. [4]
Si un autómata celular tiene sólo dos estados, entonces también hay sólo dos posibles permutaciones 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, cada autómata celular de segundo orden (definido por una función de vecindades a permutaciones) corresponde únicamente a un autómata celular ordinario (de primer orden), definido por una función directamente de vecindades a estados. [4] Los autómatas de segundo orden de dos estados son simétricos bajo inversiones temporales: la dinámica invertida en el tiempo del autómata se puede simular 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 se puede describir de forma sencilla: el estado de una célula del autómata de segundo orden en el tiempo t + 1 es el o exclusivo de su estado en el tiempo t − 1 con el estado que la regla del autómata celular ordinario calcularía para él. [4] De hecho, todas las reglas de segundo orden de dos estados se pueden producir de esta manera. [1] Sin embargo, el autómata de segundo orden resultante generalmente tendrá poca semejanza con el CA ordinario a partir del cual 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 utilizarse 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 utilizarse para criptografía . [5]