Un autómata celular de segundo orden es un tipo de autómata celular reversible (CA) inventado por Edward Fredkin [1] [2] donde el estado de una celda 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]
Técnica general
En general, la regla de evolución para un autómata de segundo orden puede describirse como una función f que mapea la vecindad de una celda a una permutación en los estados del autómata. En cada paso de tiempo t , para cada celda c del autómata, esta función se aplica a la vecindad de c para dar una permutación σ c . Entonces, esta permutación σ c se aplica al estado de la celda c en el tiempo t - 1 , y el resultado es el estado de la celda en el tiempo t + 1 . De esta forma, 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 celdas, y el paso de tiempo anterior a ese da los estados sobre los que operan estas permutaciones. . [4]
La dinámica de tiempo inverso de un autómata de segundo orden puede ser descrita por otro autómata de segundo orden con la misma vecindad, en la que la función g mapeando vecindades 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 la función f que se elija para determinar la regla del autómata. [4]
Para autómatas de dos estados
Si un autómata celular tiene solo dos estados, entonces también hay solo dos posibles permutaciones de estados: la permutación de 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 vecindarios a permutaciones) corresponde únicamente 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 de tiempo: la dinámica de inversión de 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 autómata ordinario y de segundo orden se puede describir simplemente: el estado de una celda del autómata de segundo orden en el tiempo t + 1 es el exclusivo o de su estado en el tiempo t - 1 con el estado que la regla de autómata celular ordinario calcularía para él. [4] De hecho, todas las reglas de segundo orden de dos estados pueden producirse de esta manera. [1] El autómata de segundo orden resultante, sin embargo, generalmente se parecerá poco al CA ordinario a partir del cual fue construido. Stephen Wolfram nombra las reglas de segundo orden construidas de esta manera agregando una "R" al número o código Wolfram de la regla base. [3]
Aplicaciones
Los autómatas de segundo orden se pueden utilizar para simular computadoras de bola de billar [1] y el modelo Ising de ferromagnetismo en mecánica estadística . [2] [4] También pueden usarse para criptografía . [5]
Referencias
- ^ a b c Margolus, N. (1984), "Modelos de computación similares a la física", Physica D , 10 : 81–95, doi : 10.1016 / 0167-2789 (84) 90252-5. Reimpreso en Wolfram, Stephen , ed. (1986), Teoría y aplicaciones de los autómatas celulares , Serie avanzada sobre sistemas complejos, 1 , World Scientific, págs. 232–246.
- ^ a b Vichniac, G. (1984), "Simulación de la física con autómatas celulares", 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, págs. 437–440, 452 , ISBN 1-57955-008-8.
- ^ a b c d e Toffoli, Tommaso ; Margolus, Norman (1990), "Autómatas celulares invertibles", Physica D , 45 : 229–253, doi : 10.1016 / 0167-2789 (90) 90185-r. Véase especialmente la sección 5.4 "Autómatas celulares de segundo orden", págs. 238-240. Este número de Physica D se reimprimió como Gutowitz, Howard, ed. (1991), Autómatas celulares: teoría y experimento , MIT / Holanda Septentrional.
- ^ Chai, Zhenchuan; Cao, Zhenfu; Zhou, Yuan (2005), "Cifrado basado en autómatas celulares reversibles de segundo orden", Procesamiento y aplicaciones paralelos y distribuidos (talleres ISPA 2005) , Lecture Notes in Computer Science, Springer, págs. 350–358, doi : 10.1007 / 11576259_39.