Un autómata celular reversible es un autómata celular en el que cada configuración tiene un predecesor único. Es decir, es una cuadrícula regular de celdas, cada una de las cuales contiene un estado extraído de un conjunto finito de estados, con una regla para actualizar todas las celdas simultáneamente en función de los estados de sus vecinos, de modo que el estado anterior de cualquier celda antes de una actualización se puede determinar de forma única a partir de los estados actualizados de todas las celdas. La dinámica inversa en el tiempo de un autómata celular reversible siempre puede describirse mediante otra regla de autómata celular, posiblemente en un vecindario mucho más grande.
Se conocen varios métodos para definir reglas de autómatas celulares que son reversibles; Estos incluyen el método del autómata celular de bloque , en el que cada actualización divide las celdas en bloques y aplica una función invertible por separado a cada bloque, y el método del autómata celular de segundo orden , en el que la regla de actualización combina estados de dos pasos anteriores del autómata. . Cuando un autómata no se define mediante uno de estos métodos, sino que se da como una tabla de reglas, el problema de probar si es reversible se puede resolver para los autómatas celulares de bloque y para los autómatas celulares unidimensionales, pero es indecidible para otros tipos de autómata celular.
Los autómatas celulares reversibles forman un modelo natural de computación reversible , una tecnología que podría conducir a dispositivos de computación de muy bajo consumo. A menudo se requiere que los autómatas celulares cuánticos , una forma de realizar cálculos utilizando los principios de la mecánica cuántica , sean reversibles. Además, muchos problemas en el modelado físico, como el movimiento de partículas en un gas ideal o el modelo de alineación de cargas magnéticas de Ising , son naturalmente reversibles y pueden simularse mediante autómatas celulares reversibles.
Las propiedades relacionadas con la reversibilidad también se pueden usar para estudiar autómatas celulares que no son reversibles en todo su espacio de configuración, pero que tienen un subconjunto del espacio de configuración como un atractor hacia el que convergen todas las configuraciones inicialmente aleatorias. Como escribe Stephen Wolfram , "una vez en un atractor, cualquier sistema, incluso si no tiene reglas subyacentes reversibles, debe en algún sentido mostrar una reversibilidad aproximada". [1]
Ejemplos de
Autómatas unidimensionales
Un autómata celular se define por sus celdas (a menudo una matriz unidimensional o bidimensional), un conjunto finito de valores o estados que pueden entrar en cada celda, una vecindad que asocia cada celda con un conjunto finito de celdas cercanas y una actualización. Regla según la cual los valores de todas las celdas se actualizan, simultáneamente, en función de los valores de sus celdas vecinas. Los autómatas celulares más simples posibles tienen una matriz unidimensional de celdas, cada una de las cuales puede contener un valor binario (0 o 1), y cada celda tiene una vecindad que consta solo de ella y sus dos celdas más cercanas a cada lado; estos se denominan autómatas celulares elementales . [2] Si la regla de actualización para dicho autómata hace que cada celda permanezca siempre en el mismo estado, entonces el autómata es reversible: el estado anterior de todas las celdas se puede recuperar de sus estados actuales, porque para cada celda el anterior y el actual los estados son los mismos. De manera similar, si la regla de actualización hace que cada celda cambie su estado de 0 a 1 y viceversa, o si hace que una celda copie el estado de una celda vecina fija, o si hace que copie un estado y luego invierta su estado. valor, es necesariamente reversible. [3] Toffoli y Margolus (1990) denominan "trivial" a estos tipos de autómatas celulares reversibles, en los que el estado de cada célula depende únicamente del estado previo de una célula vecina. A pesar de su simplicidad, la regla de actualización que hace que cada celda copie el estado de una celda vecina es importante en la teoría de la dinámica simbólica , donde se la conoce como mapa de cambios . [4]
De manera un poco menos trivial, suponga que las celdas nuevamente forman una matriz unidimensional, pero que cada estado es un par ordenado ( l , r ) que consta de una parte izquierda l y una parte derecha r , cada una extraída de un conjunto finito de posibles valores. Defina una función de transición que establezca que la parte izquierda de una celda sea la parte izquierda de su vecino izquierdo y la parte derecha de una celda como la parte derecha de su vecino derecho. Es decir, si el estado del vecino izquierdo es ( a , b ) y el estado del vecino derecho es ( c , d ) , el nuevo estado de una celda es el resultado de combinar estos estados usando una operación por pares × definida por la ecuación ( a , b ) × ( c , d ) = ( a , d ) . Un ejemplo de esta construcción se da en la ilustración, en la que la parte izquierda se representa gráficamente como una forma y la parte derecha se representa como un color; en este ejemplo, cada celda se actualiza con la forma de su vecino izquierdo y el color de su vecino derecho. Entonces este autómata es reversible: los valores del lado izquierdo de cada par migran hacia la derecha y los valores del lado derecho migran hacia la izquierda, por lo que el estado anterior de cada celda se puede recuperar buscando estos valores en las celdas vecinas. La operación × utilizada para combinar pares de estados en este autómata forma una estructura algebraica conocida como banda rectangular . [5]
La multiplicación de números decimales por dos o por cinco se puede realizar mediante un autómata celular reversible unidimensional con diez estados por celda (los diez dígitos decimales). Cada dígito del producto depende solo de una vecindad de dos dígitos en el número dado: el dígito en la misma posición y el dígito una posición a la derecha. De manera más general, la multiplicación o división de secuencias de dígitos doblemente infinitas en cualquier base b , por un multiplicador o divisor x cuyos factores primos también son factores primos de b , es una operación que forma un autómata celular porque depende solo de un número acotado de dígitos cercanos, y es reversible debido a la existencia de inversos multiplicativos . [6] La multiplicación por otros valores (por ejemplo, la multiplicación de números decimales por tres) sigue siendo reversible, pero no define un autómata celular, porque no hay un límite fijo en el número de dígitos en el valor inicial que se necesitan para determinar un un solo dígito en el resultado.
No existen autómatas celulares elementales reversibles no triviales. [7] Sin embargo, la Regla 90 y otros autómatas celulares elementales proporcionan un cuasi-fallo en función de la función o exclusiva . En la Regla 90, el estado de cada celda es el exclusivo o de los estados anteriores de sus dos vecinos. Este uso de la regla de transición exclusiva o hace que la regla de transición sea localmente invertible, en el sentido de que esta regla puede generar cualquier subsecuencia contigua de estados. La regla 90 no es una regla de autómata celular reversible, porque en la regla 90 cada asignación de estados al conjunto completo de células tiene exactamente cuatro posibles predecesores, mientras que las reglas reversibles deben tener exactamente un predecesor por configuración. [8]
Bichos
El Juego de la vida de Conway , una de las reglas de autómatas celulares más famosas, no es reversible: por ejemplo, tiene muchos patrones que se extinguen por completo, por lo que la configuración en la que todas las células están muertas tiene muchos predecesores, y también tiene Jardín del Edén. patrones sin predecesores. Sin embargo, otra regla llamada "Critters" por sus inventores, Tommaso Toffoli y Norman Margolus , es reversible y tiene un comportamiento dinámico similar a Life. [9]
La regla Critters es un autómata celular de bloque en el que, en cada paso, las celdas del autómata se dividen en bloques de 2 × 2 y cada bloque se actualiza independientemente de los otros bloques. Su función de transición cambia el estado de cada celda en un bloque que no tiene exactamente dos celdas vivas, y además gira 180 ° bloques con exactamente tres celdas vivas. Debido a que esta función es invertible, el autómata definido por estas reglas es un autómata celular reversible. [9]
Cuando se comienza con un campo más pequeño de células aleatorias centradas dentro de una región más grande de células muertas, muchos patrones pequeños similares al planeador de Life escapan del área aleatoria central e interactúan entre sí. La regla Critters también puede admitir naves espaciales más complejas de diferentes velocidades, así como osciladores con infinitos períodos diferentes. [9]
Construcciones
Se conocen varios métodos generales para construir reglas de autómatas celulares que son automáticamente reversibles.
Bloquear autómatas celulares
Un autómata celular de bloque es un autómata en el que, en cada paso de tiempo, las células del autómata se dividen en subconjuntos congruentes (llamados bloques), y la misma transformación se aplica independientemente a cada bloque. Normalmente, un autómata de este tipo utilizará más de una partición en bloques y rotará entre estas particiones en diferentes pasos de tiempo del sistema. [10] En una forma de este diseño de uso frecuente, llamada vecindad de Margolus, las celdas del autómata forman una cuadrícula cuadrada y se dividen en bloques cuadrados más grandes de 2 × 2 en cada paso. El centro de un bloque en un paso de tiempo se convierte en la esquina de cuatro bloques en el siguiente paso de tiempo y viceversa; de esta forma, las cuatro celdas de cada 2 × 2 pertenecen a cuatro cuadrados de 2 × 2 diferentes de la partición anterior. [11] La regla Critters discutida anteriormente es un ejemplo de este tipo de autómata.
Diseñar reglas reversibles para autómatas celulares en bloque y determinar si una regla dada es reversible es fácil: para que un autómata celular en bloque sea reversible es necesario y suficiente que la transformación aplicada a los bloques individuales en cada paso del autómata sea reversible en sí misma. . Cuando un autómata celular de bloque es reversible, la versión inversa de su dinámica también se puede describir como un autómata celular de bloque con la misma estructura de bloque, utilizando una secuencia de particiones de células en bloques invertida en el tiempo, y con la función de transición para siendo cada bloque la función inversa de la regla original. [10]
Simulación de autómatas irreversibles
Toffoli (1977) mostró cómo incrustar cualquier regla de autómata celular d- dimensional irreversible en una regla reversible ( d + 1) -dimensional. Cada segmento d- dimensional de la nueva regla reversible simula un solo paso de tiempo de la regla original. De esta manera, Toffoli demostró que muchas características de los autómatas celulares irreversibles, como la capacidad de simular máquinas de Turing arbitrarias , también podrían extenderse a los autómatas celulares reversibles.
Como Toffoli conjeturó y Hertling (1998) demostró, el aumento en la dimensión incurrido por el método de Toffoli es un pago necesario por su generalidad: bajo supuestos leves (como la traducción-invariancia de la incrustación), cualquier incrustación de un autómata celular que tiene una Garden of Eden en un autómata celular reversible debe aumentar la dimensión.
Morita (1995) describe otro tipo de simulación que no obedece a los supuestos de Hertling y no cambia la dimensión. El método de Morita puede simular las configuraciones finitas de cualquier autómata irreversible en el que hay un estado "inactivo" o "muerto", de modo que si una celda y todos sus vecinos están inactivos, la célula permanece inactiva en el siguiente paso. La simulación utiliza un autómata celular de bloque reversible de la misma dimensión que el autómata irreversible original. En cambio, la información que sería destruida por los pasos irreversibles del autómata simulado se envía desde la configuración a la región inactiva infinita del autómata simulado. Esta simulación no actualiza todas las celdas del autómata simulado simultáneamente; más bien, el tiempo para simular un solo paso es proporcional al tamaño de la configuración que se está simulando. Sin embargo, la simulación conserva con precisión el comportamiento del autómata simulado, como si todas sus celdas se estuvieran actualizando simultáneamente. Con este método es posible demostrar que incluso los autómatas celulares reversibles unidimensionales son capaces de realizar cálculos universales. [12]
Autómatas celulares de segundo orden
La técnica del autómata celular de segundo orden es un método para transformar cualquier autómata celular en un autómata celular reversible, inventado por Edward Fredkin y publicado por primera vez por varios otros autores en 1984. [13] En esta técnica, el estado de cada célula en el autómata en el tiempo t es una función tanto de su vecindad en el tiempo t - 1 como de su propio estado en el tiempo t - 2 . Específicamente, la función de transición del autómata mapea cada vecindario en el tiempo t - 1 a una permutación en el conjunto de estados, y luego aplica esa permutación al estado en el tiempo t - 2 . La dinámica inversa del autómata puede calcularse mapeando cada vecindad a la permutación inversa y procediendo de la misma manera. [14]
En el caso de los autómatas con estados con valores binarios (cero o uno), solo hay dos posibles permutaciones en los estados (la permutación de identidad y la permutación que intercambia los dos estados), que pueden representarse como el exclusivo o de un estado con un valor binario. De esta manera, cualquier autómata celular convencional de dos valores puede convertirse en una regla de autómata celular de segundo orden utilizando la función de transición del autómata convencional en los estados en el tiempo t - 1 , y luego calculando el exclusivo o de estos estados con los estados en el tiempo t - 2 para determinar los estados en el tiempo t . Sin embargo, el comportamiento del autómata celular reversible determinado de esta manera puede no tener ningún parecido con el comportamiento del autómata celular a partir del cual fue definido. [14]
Cualquier autómata de segundo orden puede transformarse en un autómata celular convencional, en el que la función de transición depende solo del único paso de tiempo anterior, combinando pares de estados de pasos de tiempo consecutivos del autómata de segundo orden en estados individuales de un autómata celular convencional. autómata. [14]
Paisaje conservado
Un autómata celular unidimensional encontrado por Patt (1971) utiliza una vecindad que consta de cuatro celdas contiguas. En este autómata, una celda cambia su estado cada vez que ocupa el "?" posición en el patrón "0? 10". No hay dos patrones de este tipo que puedan superponerse, por lo que el mismo "paisaje" que rodea la celda invertida sigue estando presente después de la transición. En el siguiente paso, la celda en el mismo "?" posición cambiará de nuevo, de nuevo a su estado original. Por lo tanto, este autómata es su propio inverso y es reversible. Patt realizó una búsqueda por fuerza bruta de todos los autómatas celulares unidimensionales de dos estados con barrios pequeños; esta búsqueda condujo al descubrimiento de este autómata, y mostró que era el autómata celular reversible de dos estados unidimensional no trivial más simple posible. No hay autómatas reversibles de dos estados con vecindarios de tres celdas, y todos los autómatas reversibles de dos estados con vecindarios de cuatro celdas son variantes simples del autómata de Patt. [15]
El autómata de Patt puede verse en retrospectiva como un ejemplo de la técnica del "paisaje conservado" para diseñar autómatas celulares reversibles. En esta técnica, un cambio en el estado de una celda se desencadena por un patrón entre un conjunto de vecinos que no cambian de estado. De esta manera, la existencia del mismo patrón se puede utilizar para desencadenar el cambio inverso en la dinámica de tiempo invertido del autómata. El autómata de Patt tiene una dinámica muy simple (todas las secuencias cíclicas de configuraciones tienen una longitud de dos), pero los autómatas que utilizan la misma técnica de paisaje conservado con más de un patrón de activación son capaces de comportamientos más complejos. En particular, pueden simular cualquier autómata celular de segundo orden. [15]
El modelo SALT de Miller & Fredkin (2005) es un caso especial de la técnica del paisaje conservado. En este modelo, las celdas de una cuadrícula de números enteros se dividen en subconjuntos pares e impares. En cada paso de tiempo, se intercambian ciertos pares de celdas de una paridad, según la configuración de celdas cercanas de la otra paridad. Las reglas que utilizan este modelo pueden simular la computadora de la bola de billar , [16] o admitir largas cadenas de células vivas que pueden moverse a muchas velocidades diferentes o vibrar a muchas frecuencias diferentes. [17]
Teoría
Un autómata celular consta de una matriz de celdas, cada una de las cuales tiene un número finito de estados posibles , junto con una regla para actualizar todas las celdas simultáneamente basándose solo en los estados de las celdas vecinas. Una configuración de un autómata celular es una asignación de un estado a cada célula del autómata; la regla de actualización de un autómata celular forma una función de configuraciones a configuraciones, con el requisito de que el valor actualizado de cualquier celda dependa solo de algún vecindario finito de la celda, y que la función sea invariante bajo las traslaciones de la matriz de entrada.
Con estas definiciones, un autómata celular es reversible cuando satisface cualquiera de las siguientes condiciones, todas las cuales son matemáticamente equivalentes entre sí: [18]
- Cada configuración del autómata tiene un predecesor único que se le asigna mediante la regla de actualización.
- La regla de actualización del autómata es una biyección ; es decir, una función que es tanto uno a uno como sobre .
- La regla de actualización es una función inyectiva , es decir, no hay dos configuraciones que se asignen a la misma configuración común. Obviamente, esta condición está implícita en el supuesto de que la regla de actualización es una biyección. En la otra dirección, el teorema del Jardín del Edén para los autómatas celulares implica que toda regla de actualización inyectiva es biyectiva. [19]
- La dinámica de tiempo invertido del autómata puede ser descrita por otro autómata celular. Claramente, para que esto sea posible, la regla de actualización debe ser biyectiva. En la otra dirección, si la regla de actualización es biyectiva, entonces tiene una función inversa que también es biyectiva. Esta función inversa debe ser una regla de autómata celular. La prueba de este hecho utiliza el teorema de Curtis-Hedlund-Lyndon , una caracterización topológica de las reglas de autómatas celulares como las funciones invariantes de traducción que son continuas con respecto a la topología de Cantor en el espacio de configuraciones. [20]
- La regla de actualización del autómata es un automorfismo del sistema dinámico de cambio definido por el espacio de estados y las traslaciones de la red de celdas. Es decir, es un homeomorfismo que conmuta con el mapa de desplazamiento, como implica el teorema de Curtis-Hedlund-Lyndon. [21]
Di Gregorio y Trautteur (1975) analizan varias definiciones alternativas de reversibilidad para autómatas celulares. La mayoría de estos resultan ser equivalentes a la inyectividad o la sobrejetividad de la función de transición del autómata; sin embargo, hay una alternativa más que no coincide con ninguna de estas dos definiciones. Se aplica a autómatas como el Juego de la vida que tienen un estado inactivo o muerto. En tal autómata, se puede definir una configuración como "finita" si sólo tiene un número finito de celdas no quiescentes, y se puede considerar la clase de autómatas para los que cada configuración finita tiene al menos un predecesor finito. Esta clase resulta ser distinta de los autómatas suprayectivos e inyectivos, y en algunas investigaciones posteriores, los autómatas con esta propiedad se han denominado autómatas finitos invertibles . [22]
Prueba de reversibilidad
Amoroso y Patt (1972) demostraron por primera vez que el problema de probar la reversibilidad de un autómata celular unidimensional dado tiene una solución algorítmica. Algoritmos alternativos basados en la teoría de autómatas y de gráficos de Bruijn fueron dadas por Culik (1987) y Sutner (1991) , respectivamente.
- Culik comienza con la observación de que un autómata celular tiene una función de transición inyectiva si y solo si la función de transición es inyectiva en los subconjuntos de configuraciones que son periódicas (repitiendo la misma subcadena infinitamente a menudo en ambas direcciones). Define un transductor de estado finito no determinista que realiza la regla de transición del autómata en cadenas periódicas. Este transductor funciona recordando la vecindad del autómata al comienzo de la cadena y entrando en un estado de aceptación cuando esa vecindad concatenada al final de la entrada causaría que sus transiciones elegidas de forma no determinista sean correctas. Culik luego intercambia la entrada y salida del transductor. El transductor resultante de este intercambio simula la dinámica inversa del autómata dado. Finalmente, Culik aplica algoritmos previamente conocidos para probar si el transductor intercambiado resultante asigna cada entrada a una única salida. [23]
- Sutner define un gráfico dirigido (un tipo de gráfico de Bruijn ) en el que cada vértice representa un par de asignaciones de estados para las celdas en una secuencia contigua de celdas. La longitud de esta secuencia se elige para que sea uno menos que el tamaño de la vecindad del autómata. Un borde en el gráfico de Sutner representa un par de secuencias de células que se superponen en todas menos una, de modo que la unión de las secuencias es una vecindad completa en el autómata celular. Cada uno de estos bordes se dirige desde la subsecuencia superpuesta de la izquierda a la subsecuencia de la derecha. Los bordes solo se incluyen en el gráfico cuando representan asignaciones de estados compatibles en las partes superpuestas de sus secuencias de celdas, y cuando la regla del autómata (aplicada a la vecindad determinada por el borde potencial) daría los mismos resultados para ambas asignaciones de estados. Al realizar un análisis de conectividad fuerte de tiempo lineal de este gráfico, es posible determinar cuáles de sus vértices pertenecen a ciclos. La regla de transición no es inyectiva si y solo si este gráfico contiene un ciclo dirigido en el que al menos un vértice tiene dos asignaciones de estado diferentes. [8]
Estos métodos toman un tiempo polinomial , proporcional al cuadrado del tamaño de la tabla de transición de estado del autómata de entrada. [24] Un algoritmo relacionado de Hillman (1991) determina si una regla dada es sobreyectiva cuando se aplica a matrices de celdas de longitud finita con condiciones de contorno periódicas, y si es así, para qué longitudes.
Para un autómata celular de bloque, probar la reversibilidad también es fácil: el autómata es reversible si y solo si la función de transición en los bloques del autómata es invertible, y en este caso el autómata inverso tiene la misma estructura de bloque con la función de transición inversa. [10]
Sin embargo, para los autómatas celulares con otros vecindarios en dos o más dimensiones, el problema de probar la reversibilidad es indecidible , lo que significa que no puede existir un algoritmo que siempre se detenga y siempre responda correctamente al problema. La prueba de este hecho por Kari (1990) se basa en la indecidibilidad previamente conocida de colocar el plano en baldosas de Wang , conjuntos de baldosas cuadradas con marcas en sus bordes que limitan qué pares de baldosas pueden encajar de borde a borde. Kari define un autómata celular a partir de un conjunto de mosaicos de Wang, de modo que el autómata deja de ser inyectivo si y solo si el conjunto de mosaicos dado puede recubrir todo el plano. Su construcción utiliza el barrio de von Neumann y celdas con un gran número de estados. En el mismo artículo, Kari también mostró que es indecidible probar si una determinada regla de autómata celular de dos o más dimensiones es sobreyectiva (es decir, si tiene un Jardín del Edén ).
Tamaño de vecindario inverso
En un autómata celular reversible unidimensional con n estados por celda, en el que la vecindad de una celda es un intervalo de m celdas, el autómata que representa la dinámica inversa tiene vecindades que constan como máximo de n m - 1 - m + 1 celdas . Se sabe que este límite es estrecho para m = 2 : existen autómatas celulares reversibles de n estados con vecindarios de dos celdas cuya dinámica inversa en el tiempo forma un autómata celular con un tamaño de vecindario exactamente n - 1 . [25]
Para cualquier entero m hay sólo un número finito de autómatas celulares bidimensionales reversibles en estado m con la vecindad de von Neumann. Por lo tanto, hay una función f ( m ) bien definida tal que todas las reversiones de los autómatas celulares de estado m con la vecindad de von Neumann usan una vecindad con radio como máximo f ( m ) : simplemente sea f ( m ) el máximo, entre todos los finitos numerosos autómatas celulares de estado m reversibles , del tamaño de vecindad necesario para representar la dinámica de tiempo invertido del autómata. Sin embargo, debido al resultado de indecidibilidad de Kari, no existe un algoritmo para calcular f ( m ) y los valores de esta función deben crecer muy rápidamente, más rápidamente que cualquier función computable . [12]
Clasificación de Wolfram
Una clasificación bien conocida de autómatas celulares de Stephen Wolfram estudia su comportamiento en condiciones iniciales aleatorias. Para un autómata celular reversible, si la configuración inicial se elige uniformemente al azar entre todas las configuraciones posibles, entonces esa misma aleatoriedad uniforme continúa siendo válida para todos los estados subsiguientes. Por tanto, parecería que la mayoría de los autómatas celulares reversibles pertenecen a la Clase 3 de Wolfram: autómatas en los que casi todas las configuraciones iniciales evolucionan de forma pseudoaleatoria o caótica. Sin embargo, todavía es posible distinguir entre diferentes autómatas celulares reversibles analizando el efecto de las perturbaciones locales sobre el comportamiento del autómata. Hacer un cambio en el estado inicial de un autómata celular reversible puede hacer que los cambios en estados posteriores permanezcan solo dentro de una región delimitada, se propaguen de manera irregular pero ilimitada, o se extiendan rápidamente, y Wolfram (1984) enumera las reglas de autómatas celulares reversibles unidimensionales exhibiendo estos tres tipos de comportamiento.
Un trabajo posterior de Wolfram identifica el autómata unidimensional de la Regla 37R como particularmente interesante a este respecto. Cuando se ejecuta en una matriz finita de celdas con condiciones de contorno periódicas, a partir de una pequeña semilla de celdas aleatorias centradas dentro de un vecindario vacío más grande, tiende a fluctuar entre estados ordenados y caóticos. Sin embargo, con las mismas condiciones iniciales en un conjunto ilimitado de células, sus configuraciones tienden a organizarse en varios tipos de partículas simples en movimiento. [26]
Álgebra abstracta
Otra forma de formalizar los autómatas celulares reversibles implica el álgebra abstracta , y esta formalización ha sido útil en el desarrollo de búsquedas computarizadas de reglas de autómatas celulares reversibles. Boykett (2004) define un bigroupoide semicentral como una estructura algebraica que consta de un conjunto S de elementos y dos operaciones → y ← sobre pares de elementos, satisfaciendo los dos axiomas ecuacionales:
- para todos los elementos de una , b , y c en S , ( un → b ) ← ( b → c ) = b , y
- para todos los elementos de una , b , y c en S , ( un ← b ) → ( b ← c ) = b .
Por ejemplo, esto es cierto para las dos operaciones en las que la operación → devuelve su argumento derecho y la operación ← devuelve su argumento izquierdo.
Como sostiene Boykett, cualquier autómata celular reversible unidimensional es equivalente a un autómata en forma rectangular , en el que las celdas están desplazadas media unidad en cada paso de tiempo, y en el que tanto la evolución hacia adelante como hacia atrás del autómata tienen vecindades con solo dos celdas, las celdas a media unidad de distancia en cada dirección. Si un autómata reversible tiene vecindarios mayores de dos celdas, puede ser simulado por un autómata reversible con vecindarios más pequeños y más estados por celda, en el que cada celda del autómata simulador simula un bloque contiguo de celdas en el autómata simulado. Los dos axiomas de un bigroupoide semicentral son exactamente las condiciones requeridas en las funciones de transición hacia adelante y hacia atrás de estos vecindarios de dos celdas para ser inversos entre sí. Es decir, todo bigroupoide semicentral define un autómata celular reversible en forma rectangular, en el que la función de transición del autómata utiliza la operación → para combinar las dos celdas de su vecindad, y en el que la operación ← define de manera similar la dinámica inversa del autómata. . Cada autómata celular reversible unidimensional es equivalente a uno en esta forma. [5]
Boykett utilizó esta formulación algebraica como base para algoritmos que enumeran exhaustivamente todos los posibles autómatas celulares reversibles desiguales. [27]
Leyes de conservación
Cuando los investigadores diseñan autómatas celulares reversibles para simular sistemas físicos, normalmente incorporan en el diseño las leyes de conservación del sistema; por ejemplo, un autómata celular que simula un gas ideal debería conservar el número de partículas de gas y su impulso total , porque de lo contrario no proporcionaría una simulación precisa. Sin embargo, también ha habido algunas investigaciones sobre las leyes de conservación que pueden tener los autómatas celulares reversibles, independientemente de cualquier diseño intencional. El tipo típico de cantidad conservada medida en estos estudios toma la forma de una suma, sobre todos los subconjuntos contiguos de k celdas del autómata, de alguna función numérica de los estados de las celdas en cada subconjunto. Tal cantidad se conserva si, siempre que toma un valor finito, ese valor permanece constante automáticamente a través de cada paso de tiempo del autómata, y en este caso se denomina invariante de k -ésimo orden del autómata. [28]
Por ejemplo, recuerde el autómata celular unidimensional definido como un ejemplo de una banda rectangular , en el que los estados de celda son pares de valores ( l , r ) extraídos de los conjuntos L y R de valores izquierdos y valores derechos, el valor izquierdo de cada celda se mueve hacia la derecha en cada paso de tiempo, y el valor correcto de cada celda se mueve hacia la izquierda. En este caso, para cada valor x izquierdo o derecho de la banda, se puede definir una cantidad conservada, el número total de celdas que tienen ese valor. Si hay valores de λ a la izquierda y valores de ρ a la derecha, entonces hay λ + ρ - 2 invariantes de primer orden independientes, y cualquier invariante de primer orden se puede representar como una combinación lineal de estos fundamentales. Las cantidades conservadas asociadas con los valores de la izquierda fluyen uniformemente hacia la derecha a una tasa constante: es decir, si el número de valores de la izquierda igual ax dentro de alguna región C de la línea toma un cierto valor en el tiempo 0 , entonces tomará el mismo valor. valor para la región desplazada C + t / 2 en el tiempo t . De manera similar, las cantidades conservadas asociadas con los valores de la derecha fluyen uniformemente hacia la izquierda. [29]
Cualquier autómata celular reversible unidimensional puede colocarse en forma rectangular, después de lo cual su regla de transición puede factorizarse en la acción de un bigroupoide semicentral idempotente (una regla reversible para la cual las regiones de células con un valor de estado único cambian solo en sus límites) junto con una permutación en el conjunto de estados. Los invariantes de primer orden para el levantamiento idempotente de la regla del autómata (la regla modificada formada al omitir la permutación) necesariamente se comportan como los de una banda rectangular: tienen una base de invariantes que fluyen hacia la izquierda o hacia la derecha a una tasa constante sin Interacción. Las invariantes de primer orden para el autómata general son entonces exactamente las invariantes para el levantamiento idempotente que dan el mismo peso a cada par de estados que pertenecen a la misma órbita de la permutación. Sin embargo, la permutación de estados en la regla puede hacer que estos invariantes se comporten de manera diferente al levantamiento idempotente, fluyendo de manera no uniforme y con interacciones. [29]
En los sistemas físicos, el teorema de Noether proporciona una equivalencia entre las leyes de conservación y las simetrías del sistema. Sin embargo, para los autómatas celulares este teorema no se aplica directamente, porque en lugar de estar gobernado por la energía del sistema, el comportamiento del autómata se codifica en sus reglas, y se garantiza que el autómata obedecerá ciertas simetrías (invariancia de traducción tanto en el espacio como en el tiempo) independientemente de las leyes de conservación que pudiera obedecer. Sin embargo, las cantidades conservadas de ciertos sistemas reversibles se comportan de manera similar a la energía en algunos aspectos. Por ejemplo, si diferentes regiones del autómata tienen diferentes valores promedio de alguna cantidad conservada, las reglas del autómata pueden hacer que esta cantidad se disipe, de modo que la distribución de la cantidad sea más uniforme en estados posteriores. El uso de estas cantidades conservadas como sustituto de la energía del sistema puede permitir su análisis utilizando métodos de la física clásica. [30]
Aplicaciones
Autómatas de gas de celosía
Un autómata de gas de celosía es un autómata celular diseñado para simular el movimiento de partículas en un fluido o un gas ideal . En tal sistema, las partículas de gas se mueven en línea recta con velocidad constante, hasta sufrir una colisión elástica con otras partículas. Los autómatas de gas de celosía simplifican estos modelos al permitir solo un número constante de velocidades (generalmente, solo una velocidad y cuatro o seis direcciones de movimiento) y al simplificar los tipos de colisión que son posibles. [31]
Específicamente, el modelo de gas reticular HPP consiste en partículas que se mueven a una velocidad unitaria en las direcciones paralelas de cuatro ejes. Cuando dos partículas se encuentran en la misma línea en direcciones opuestas, chocan y se envían hacia afuera desde el punto de colisión en la línea perpendicular. Este sistema obedece las leyes de conservación de los gases físicos y produce simulaciones cuya apariencia se asemeja al comportamiento de los gases físicos. Sin embargo, se encontró que obedecía leyes de conservación adicionales poco realistas. Por ejemplo, se conserva el impulso total dentro de una sola línea. Además, las diferencias entre las direcciones de eje paralelo y no eje paralelo en este modelo (su anisotropía ) son indeseablemente altas. El modelo de gas de celosía FHP mejora el modelo HPP al hacer que las partículas se muevan en seis direcciones diferentes, en ángulos de 60 grados entre sí, en lugar de solo cuatro direcciones. En cualquier colisión frontal, las dos partículas salientes se desvían en ángulos de 60 grados de las dos partículas entrantes. Las colisiones de tres vías también son posibles en el modelo FHP y se manejan de una manera que preserva el impulso total y evita las leyes de conservación agregadas no físicas del modelo HPP. [31]
Debido a que el movimiento de las partículas en estos sistemas es reversible, generalmente se implementan con autómatas celulares reversibles. En particular, tanto los autómatas de gas de celosía HPP como FHP pueden implementarse con un autómata celular de bloque de dos estados utilizando la vecindad de Margolus. [31]
Modelo de ising
El modelo de Ising se utiliza para modelar el comportamiento de los sistemas magnéticos. Consiste en una matriz de celdas, el estado de cada una de las cuales representa un giro , ya sea hacia arriba o hacia abajo . La energía del sistema se mide mediante una función que depende del número de pares de células vecinas que tienen el mismo giro entre sí. Por lo tanto, si una celda tiene el mismo número de vecinos en los dos estados, puede cambiar su propio estado sin cambiar la energía total. Sin embargo, tal cambio ahorra energía solo si no hay dos celdas adyacentes que se muevan al mismo tiempo. [32]
Los modelos de autómatas celulares de este sistema dividen la celosía cuadrada en dos subconjuntos alternos y realizan actualizaciones en uno de los dos subconjuntos a la vez. En cada actualización, todas las celdas que pueden voltear lo hacen. Esto define un autómata celular reversible que se puede utilizar para investigar el modelo de Ising. [32]
Computación de bolas de billar y computación de bajo consumo
Fredkin y Toffoli (1982) propusieron la computadora de bola de billar como parte de sus investigaciones sobre la computación reversible . Una computadora de bolas de billar consiste en un sistema de partículas sincronizadas (las bolas de billar) que se mueven en pistas y son guiadas por un conjunto fijo de obstáculos. Cuando las partículas chocan entre sí o con los obstáculos, sufren una colisión elástica muy similar a como lo harían las bolas de billar reales . La entrada a la computadora se codifica usando la presencia o ausencia de partículas en ciertas pistas de entrada, y su salida se codifica de manera similar usando la presencia o ausencia de partículas en las pistas de salida. Las pistas en sí pueden verse como cables y las partículas como señales booleanas transportadas por esos cables. Cuando una partícula choca contra un obstáculo, se refleja en él. Esta reflexión puede interpretarse como un cambio en la dirección del cable que sigue la partícula. Dos partículas en diferentes pistas pueden chocar, formando una puerta lógica en su punto de colisión. [33]
Como mostró Margolus (1984) , las computadoras de bola de billar pueden simularse usando un autómata celular de bloque reversible de dos estados con la vecindad de Margolus. En la regla de actualización de este autómata, los bloques con exactamente una celda activa giran 180 °, los bloques con dos celdas activas diagonalmente opuestas giran 90 ° y todos los demás bloques permanecen sin cambios. Estas reglas hacen que las células vivas aisladas se comporten como bolas de billar, moviéndose en trayectorias diagonales. Los grupos conectados de más de una célula viva se comportan en cambio como los obstáculos fijos de la computadora de bola de billar. En un apéndice, Margolus también mostró que un autómata celular de segundo orden de tres estados usando el vecindario bidimensional de Moore podría simular computadoras de bolas de billar.
¿Es todo autómata celular reversible tridimensional localmente reversible?
Una razón para estudiar modelos universales reversibles de computación, como el modelo de la bola de billar, es que teóricamente podrían conducir a sistemas informáticos reales que consuman cantidades muy bajas de energía. Según el principio de Landauer , los pasos computacionales irreversibles requieren una cierta cantidad mínima de energía por paso, pero los pasos reversibles se pueden realizar con una cantidad de energía por paso que sea arbitrariamente cercana a cero. [34] Sin embargo, para realizar el cálculo utilizando menos energía que el límite de Landauer, no es suficientemente bueno que un autómata celular tenga una función de transición que sea globalmente reversible: lo que se requiere es que el cálculo local de la función de transición también sea hecho de forma reversible. Por ejemplo, los autómatas celulares de bloques reversibles son siempre localmente reversibles: el comportamiento de cada bloque individual implica la aplicación de una función invertible con un número finito de entradas y salidas. Toffoli y Margolus (1990) fueron los primeros en preguntar si todo autómata celular reversible tiene una regla de actualización localmente reversible. Kari (1996) mostró que para los autómatas unidimensionales y bidimensionales la respuesta es positiva, y Durand-Lose (2001) mostró que cualquier autómata celular reversible podría ser simulado por un autómata celular localmente reversible (posiblemente diferente). Sin embargo, la cuestión de si cada función de transición reversible es localmente reversible permanece abierta para dimensiones superiores a dos. [35]
Sincronización
La regla "Tron" de Toffoli y Margolus es una regla celular de bloque reversible con el vecindario de Margolus. Cuando un bloque de celdas de 2 × 2 tienen el mismo estado, todas las celdas del bloque cambian de estado; en todos los demás casos, las celdas del bloque permanecen sin cambios. Como sostienen Toffoli y Margolus, la evolución de los patrones generados por esta regla puede usarse como un reloj para sincronizar cualquier otra regla en el vecindario de Margolus. Un autómata celular sincronizado de esta manera obedece a la misma dinámica que la regla estándar de vecindad de Margolus mientras se ejecuta en un autómata celular asincrónico . [36]
Cifrado
Kari (1990) propuso el uso de autómatas celulares multidimensionales reversibles como sistema de cifrado . En la propuesta de Kari, la regla del autómata celular sería la clave de cifrado. El cifrado se realizaría ejecutando la regla un paso hacia adelante y el descifrado se realizaría ejecutándola hacia atrás un paso. Kari sugiere que un sistema como este puede usarse como un criptosistema de clave pública . En principio, un atacante no podría determinar algorítmicamente la clave de descifrado (la regla inversa) a partir de una clave de cifrado determinada (regla de reenvío) debido a la indecidibilidad de probar la reversibilidad, por lo que la regla de reenvío podría hacerse pública sin comprometer la seguridad del sistema. Sin embargo, Kari no especificó qué tipos de autómatas celulares reversibles deberían usarse para tal sistema, ni mostró cómo un criptosistema que usa este enfoque podría generar pares de claves de cifrado / descifrado.
Chai, Cao y Zhou (2005) han propuesto un sistema de cifrado alternativo. En su sistema, la clave de cifrado determina la regla local para cada celda de un autómata celular unidimensional. Un autómata de segundo orden basado en esa regla se ejecuta durante varias rondas en una entrada para transformarla en una salida cifrada. La propiedad de reversibilidad del autómata asegura que cualquier mensaje cifrado pueda descifrarse ejecutando el mismo sistema a la inversa. En este sistema, las claves deben mantenerse en secreto, porque la misma clave se utiliza tanto para el cifrado como para el descifrado.
Computación cuántica
Los autómatas celulares cuánticos son conjuntos de autómatas cuyos estados y transiciones de estado obedecen a las leyes de la dinámica cuántica . Los autómatas celulares cuánticos fueron sugeridos como modelo de cálculo por Feynman (1982) y formalizados por primera vez por Watrous (1995) . Varias nociones en competencia de estos autómatas permanecen bajo investigación, muchas de las cuales requieren que los autómatas construidos de esta manera sean reversibles. [37]
Universalidad física
Janzing (2010) preguntó si era posible que un autómata celular fuera físicamente universal , lo que significa que, para cualquier región delimitada de las células del autómata, debería ser posible rodear esa región con células cuyos estados formen un andamiaje de soporte apropiado que provoque la autómata para implementar cualquier transformación arbitraria en conjuntos de estados dentro de la región. Tal autómata debe ser reversible, o al menos inyectable localmente, porque los autómatas sin esta propiedad tienen patrones del Jardín del Edén, y no es posible implementar una transformación que cree un Jardín del Edén.
Schaeffer (2015) construyó un autómata celular reversible que es físicamente universal en este sentido. El autómata de Schaeffer es un autómata celular de bloque con dos estados y el barrio de Margolis, estrechamente relacionado con los autómatas para el modelo de bola de billar y para el gas reticular HPP. Sin embargo, el modelo de bola de billar no es físicamente universal, ya que puede usarse para construir muros impenetrables que impidan que el estado dentro de alguna región sea leído y transformado. En el modelo de Schaeffer, cada patrón eventualmente se descompone en partículas que se mueven diagonalmente en cuatro direcciones. Por tanto, su autómata no es Turing completo . Sin embargo, Schaeffer demostró que es posible rodear cualquier configuración finita mediante un andamio que se descompone más lentamente que él. Después de que la configuración se descompone en partículas, el andamio intercepta esas partículas y las utiliza como entrada a un sistema de circuitos booleanos construidos dentro del andamio. Estos circuitos se pueden utilizar para calcular funciones arbitrarias de la configuración inicial. El andamio luego traduce la salida de los circuitos nuevamente en un sistema de partículas en movimiento, que convergen en la región inicial y chocan entre sí para construir una copia del estado transformado. De esta manera, el sistema de Schaeffer se puede utilizar para aplicar cualquier función a cualquier región delimitada del espacio de estados, mostrando que esta regla de autómata es físicamente universal. [38]
Notas
- ^ Wolfram (2002) , p. 1018 .
- ^ Schiff (2008) , p. 44.
- ^ Toffoli y Margolus (1990) .
- ^ Blanchard, Devaney y Keen (2004) , p. 38 : "El mapa de cambios es sin duda el objeto fundamental en la dinámica simbólica".
- ↑ a b Boykett (2004) .
- ^ Wolfram (2002) , p. 1093 .
- ^ Patt (1971) .
- ↑ a b Sutner (1991) .
- ↑ a b c Toffoli & Margolus (1987) , sección 12.8.2, "Critters", págs. 132-134; Margolus (1999) ; Marotta (2005) .
- ^ a b c Toffoli y Margolus (1987) , Sección 14.5, "Técnica de particionamiento", págs. 150-153; Schiff (2008) , Sección 4.2.1, "Partición de autómatas celulares", págs. 115-116.
- ^ Toffoli y Margolus (1987) , Capítulo 12, "El barrio de Margolus", págs. 119-138.
- ↑ a b Kari (2005) .
- ^ Margolus (1984) ; Vichniac (1984) ; Wolfram (1984) .
- ^ a b c Toffoli y Margolus (1987) , Sección 14.2, "Técnica de segundo orden", págs. 147-149. Wolfram (2002) , págs. 437 y siguientes . McIntosh (2009) .
- ↑ a b Toffoli & Margolus (1990) , sección 5.3, "Permutaciones de paisajes conservados", págs. 237-238.
- ^ Miller y Fredkin (2005) .
- ^ Miller y Fredkin (2012) .
- ↑ En el caso unidimensional, varias de estas equivalencias ya fueron presentadas, en el lenguaje de sistemas dinámicos más que en autómatas celulares, por Hedlund (1969) , Teorema 4.1. Para mayores dimensiones, ver Richardson (1972) y Di Gregorio & Trautteur (1975) .
- ^ Myhill (1963) .
- ^ Richardson (1972) .
- ^ Hedlund (1969) .
- ^ Moraal (2000) .
- ↑ Culik cita un libro de texto de teoría de autómatas de 1979 para este resultado, pero ver Béal et al. (2003) para conocer los desarrollos más recientes sobre la prueba eficiente de si un transductor define una función.
- ↑ Ni Amoroso & Patt (1972) ni Culik (1987) establecen explícitamente las complejidades temporales de sus algoritmos, pero Sutner (1991) sí, y este límite también se puede encontrar, por ejemplo, en Czeizler & Kari (2007) .
- ^ Kari (1992) ; Czeizler (2004) ; Czeizler y Kari (2007) .
- ^ Wolfram (2002) , págs. 454–457.
- ^ Boykett (2004) . Véase Hillman (1991) y Seck Tuoh Mora et al. (2005) para trabajos estrechamente relacionados sobre la enumeración de autómatas celulares reversibles de ancho 2.
- ^ Hattori y Takesue (1991) ; Fukś (2007) .
- ↑ a b Boykett, Kari y Taati (2008) .
- ^ Pomeau (1984) ; Takesue (1990) ; Capobianco y Toffoli (2011) .
- ^ a b c Toffoli y Margolus (1987) , Capítulo 16, "Dinámica de fluidos", págs. 172-184.
- ↑ a b Toffoli & Margolus (1987) , Capítulo 17.2, "Sistemas de Ising", págs. 186-190.
- ^ Durand-Lose (2002) .
- ^ Fredkin y Toffoli (1982) .
- ↑ Kari ( 2005 , 2009 )
- ^ Toffoli y Margolus (1987) , Sección 12.8.3, "Cálculo asincrónico", págs. 134-136.
- ^ Meyer (1996) ; Schumacher y Werner (2004) ; Shepherd, Franz y Werner (2006) ; Nagaj y Wocjan (2008) .
- ^ Véase también " Un autómata celular físicamente universal ", Shtetl-Optimized, Scott Aaronson , 26 de junio de 2014.
Referencias
- Amoroso, S .; Patt, YN (1972), "Procedimientos de decisión para sobrejetividad e inyectividad de mapas paralelos para estructuras de teselación", Journal of Computer and System Sciences , 6 (5): 448-464, doi : 10.1016 / S0022-0000 (72) 80013- 8 , MR 0317852.
- Béal, Marie-Pierre; Carton, Olivier; Prieur, Christophe; Sakarovitch, Jacques (2003), "Transductores de cuadratura: un procedimiento eficiente para decidir la funcionalidad y la secuencialidad", Informática teórica , 292 (1): 45–63, doi : 10.1016 / S0304-3975 (01) 00214-6 , MR 1964625.
- Blanchard, Paul; Devaney, Robert L .; Keen, Linda (2004), "Complex dynamics and symbolic dynamics", en Williams, Susan G. (ed.), Symbolic Dynamics and its Applications , Proceedings of Symposia in Applied Mathematics, 60 , Providence, RI: American Mathematical Society, págs. 37–60, doi : 10.1090 / psapm / 060/2078845 , MR 2078845.
- Boykett, Tim (2004), "Listados exhaustivos eficientes de autómatas celulares unidimensionales reversibles", Theoretical Computer Science , 325 (2): 215–247, doi : 10.1016 / j.tcs.2004.06.007 , MR 2086738.
- Boykett, Tim; Kari, Jarkko ; Taati, Siamak (2008), "Leyes de conservación en CA rectangular" (PDF) , Journal of Cellular Automata , 3 (2): 115-122, MR 2394641 , archivado desde el original (PDF) el 30 de septiembre de 2015.
- Capobianco, Silvio; Toffoli, Tommaso (2011), "¿Se puede salvar algo del teorema de Noether para sistemas dinámicos discretos?", Actas de la X Conferencia Internacional sobre Computación No Convencional (UC 2011) , Lecture Notes in Computer Science , 6714 , Springer-Verlag, págs. 77–88, arXiv : 1103.4785 , doi : 10.1007 / 978-3-642-21341-0_13.
- 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 , 3759 , Springer-Verlag, págs. 350–358, doi : 10.1007 / 11576259_39.
- Culik, Karel, II (1987), "Sobre autómatas celulares invertibles" (PDF) , Complex Systems , 1 (6): 1035-1044, MR 0931401.
- Czeizler, Eugen (2004), "Sobre el tamaño de las vecindades inversas para autómatas celulares reversibles unidimensionales", Informática teórica , 325 (2): 273-284, doi : 10.1016 / j.tcs.2004.06.009 , MR 2086740.
- Czeizler, Eugen; Kari, Jarkko (2007), "Un límite lineal estrecho en el retardo de sincronización de los autómatas biyectivos", Informática teórica , 380 (1–2): 23–36, doi : 10.1016 / j.tcs.2007.02.052 , MR 2330639.
- Di Gregorio, S .; Trautteur, G. (1975), "Sobre la reversibilidad en autómatas celulares", Journal of Computer and System Sciences , 11 (3): 382–391, doi : 10.1016 / S0022-0000 (75) 80059-6 , MR 0392201.
- Durand-Lose, Jérôme (2001), "Representación de autómatas celulares reversibles con autómatas celulares de bloques reversibles", Modelos discretos: combinatoria, computación y geometría (París, 2001) , Matemáticas discretas. Theor. Computación. Sci. Proc., AA, Maison Inform. Matemáticas. Discrèt. (MIMD), París, págs. 145-154, MR 1888769.
- Durand-Lose, Jérôme (2002), "Computación dentro del modelo de bola de billar", en Adamatzky, Andrew (ed.), Computación basada en colisiones , Springer-Verlag, págs. 135-160.
- Feynman, Richard P. (1982), "Simulando la física con computadoras", International Journal of Theoretical Physics , 21 (6–7): 467–488, Bibcode : 1982IJTP ... 21..467F , doi : 10.1007 / BF02650179 , Señor 0658311 , S2CID 124545445.
- Fredkin, Edward ; Toffoli, Tommaso (1982), "Lógica conservadora", International Journal of Theoretical Physics , 21 (3-4): 219-253, Bibcode : 1982IJTP ... 21..219F , doi : 10.1007 / BF01857727 , MR 0657156 , S2CID 37305161. Reimpreso en Adamatzky, Andrew , ed. (2002), Computación basada en colisiones , Springer-Verlag, págs. 47–82.
- Fukś, Henryk (2007), "Observaciones sobre el comportamiento crítico de los invariantes aditivos de segundo orden en autómatas celulares elementales", Fundamenta Informaticae , 78 (3): 329–341, arXiv : nlin / 0502037 , Bibcode : 2005nlin ..... .2037F , MR 2346870.
- Hattori, Tetsuya; Takesue, Shinji (1991), "Cantidades conservadas aditivas en sistemas dinámicos de celosía en tiempo discreto", Physica D: Nonlinear Phenomena , 49 (3): 295–322, Bibcode : 1991PhyD ... 49..295H , doi : 10.1016 / 0167-2789 (91) 90150-8 , MR 1115865.
- Hedlund, GA (1969), "Endomorfismos y automorfismos de los sistemas dinámicos de desplazamiento", Teoría de sistemas matemáticos , 3 (4): 320–375, doi : 10.1007 / BF01691062 , MR 0259881 , S2CID 21803927.
- Hertling, Peter (1998), "Incrustar autómatas celulares en autómatas reversibles", Modelos no convencionales de computación (Auckland, 1998) , Serie Springer en Matemáticas discretas y Ciencias de la computación teóricas, Springer-Verlag, págs. 243-256, MR 1653663.
- Hillman, David (1991), "La estructura de los autómatas celulares unidimensionales reversibles", Physica D: Nonlinear Phenomena , 52 (2-3): 277-292, Bibcode : 1991PhyD ... 52..277H , doi : 10.1016 / 0167-2789 (91) 90128-V , MR 1128996.
- Janzing, Dominik (2010), ¿Existe un autómata celular físicamente universal o hamiltoniano? , arXiv : 1009.1720 , Bibcode : 2010arXiv1009.1720J.
- Kari, Jarkko (1990), "La reversibilidad de los autómatas celulares 2D es indecidible", Autómatas celulares: teoría y experimento (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena , 45 (1-3): 379-385, Bibcode : 1990PhyD ... 45..379K , doi : 10.1016 / 0167-2789 (90) 90195-U , MR 1094882.
- Kari, Jarkko (1992), "En los vecindarios inversos de los autómatas celulares reversibles", Lindenmayer Systems: Impactos en la informática teórica, gráficos por computadora y biología del desarrollo , Springer-Verlag, págs. 477–495, MR 1226709.
- Kari, Jarkko (1996), "Representación de autómatas celulares reversibles con permutaciones de bloques", Teoría de sistemas matemáticos , 29 (1): 47–61, doi : 10.1007 / BF01201813 , MR 1360196 , S2CID 31986003.
- Kari, Jarkko (2005), "Autómatas celulares reversibles" (PDF) , Desarrollos en la teoría del lenguaje: 9ª Conferencia Internacional, DLT 2005, Palermo, Italia, 4 al 8 de julio de 2005, Actas , Lecture Notes in Computer Science , 3572 , Springer -Verlag, págs. 2–23, doi : 10.1007 / 11505877_5 , MR 2187250.
- Kari, Jarkko (2009), "Estructura de autómatas celulares reversibles", Computación no convencional: 8th International Conference, UC 2009, Ponta Delgada, Portugal, 7-11 de septiembre de 2009, Proceedings , Lecture Notes in Computer Science , 5715 , Springer-Verlag , pag. 6, código bibliográfico : 2009LNCS.5715 .... 6K , doi : 10.1007 / 978-3-642-03745-0_5 , MR 2539690.
- Margolus, Norman (1984), "Modelos de computación similares a la física", Physica D: Nonlinear Phenomena , 10 (1–2): 81–95, Bibcode : 1984PhyD ... 10 ... 81M , doi : 10.1016 / 0167 -2789 (84) 90252-5 , MR 0762656. Reimpreso en Wolfram, Stephen (1986), Teoría y aplicaciones de los autómatas celulares , Serie avanzada sobre sistemas complejos, 1 , World Scientific, págs. 232–246, y en Adamatzky, Andrew , ed. (2002), Computación basada en colisiones , Springer-Verlag, págs. 83-104.
- Margolus, Norman (1999), "Crystalline computation", en Hey, Anthony JG (ed.), Feynman and Computation , Perseus Books, págs. 267-305, arXiv : comp-gas / 9811002 , Bibcode : 1998comp.gas.11002M.
- Marotta, Sebastian M. (2005), "Living in Critters 'world" , Revista Ciências Exatas e Naturais , 7 (1), archivado desde el original el 19 de marzo de 2012.
- McIntosh, Harold V. (2009), "12. Autómatas celulares reversibles", Autómatas celulares unidimensionales , Luniver Press, págs. 205–246.
- Meyer, David A. (1996), "De los autómatas celulares cuánticos a los gases de la red cuántica", Journal of Statistical Physics , 85 (5-6): 551-574, arXiv : quant-ph / 9604003 , Bibcode : 1996JSP ... .85..551M , doi : 10.1007 / BF02199356 , MR 1418805 , S2CID 661940.
- Miller, Daniel B .; Fredkin, Edward (2005), "Autómatas celulares universales, reversibles y de dos estados en tres dimensiones", Actas de la Segunda Conferencia sobre Fronteras de la Computación (CF '05) , Nueva York, NY, EE. UU.: ACM, págs. 45–51 , arXiv : nlin / 0501022 , doi : 10.1145 / 1062261.1062271 , ISBN 1-59593-019-1, S2CID 14082792.
- Miller, Daniel B .; Fredkin, Edward (2012), Movimiento circular de cuerdas en autómatas celulares y otras sorpresas , arXiv : 1206.2060 , Bibcode : 2012arXiv1206.2060M.
- Moraal, Hendrik (2000), "Caracterización gráfica-teórica de autómatas celulares invertibles", Physica D: Nonlinear Phenomena , 141 (1–2): 1–18, Bibcode : 2000PhyD..141 .... 1M , doi : 10.1016 / S0167-2789 (00) 00020-8 , MR 1764165.
- Morita, Kenichi (1995), "Simulación reversible de autómatas celulares irreversibles unidimensionales", Informática teórica , 148 (1): 157-163, doi : 10.1016 / 0304-3975 (95) 00038-X , MR 1347674.
- Myhill, John (1963), "El inverso del teorema del Jardín del Edén de Moore", Proceedings of the American Mathematical Society , 14 (4): 685–686, doi : 10.2307 / 2034301 , JSTOR 2034301 , MR 0155764. Reimpreso en Burks, Arthur W. (1970), Ensayos sobre autómatas celulares , University of Illinois Press, págs. 204–205.
- Nagaj, Daniel; Wocjan, Pawel (2008), "Autómatas celulares cuánticos de Hamilton en una dimensión", Physical Review A , 78 (3): 032311, arXiv : 0802.0886 , Bibcode : 2008PhRvA..78c2311N , doi : 10.1103 / PhysRevA.78.032311 , S2CID 18879990.
- Patt, YN (1971), Inyecciones de tamaño de vecindad tres y cuatro en el conjunto de configuraciones de los autómatas de teselación unidimensional infinita de celdas de dos estados , Informe técnico ECON-N1-P-1, Ft. Monmouth, Nueva Jersey 07703. Como lo citan Amoroso y Patt (1972) y Toffoli y Margolus (1990) .
- Pomeau, Y. (1984), "Invariantes en autómatas celulares", Journal of Physics A: Mathematical and General , 17 (8): L415 – L418, Bibcode : 1984JPhA ... 17L.415P , doi : 10.1088 / 0305-4470 / 17/8/004 , MR 0750565.
- Richardson, D. (1972), "Teselaciones con transformaciones locales", Journal of Computer and System Sciences , 6 (5): 373–388, doi : 10.1016 / S0022-0000 (72) 80009-6 , MR 0319678.
- Schaeffer, Luke (2015), "Un autómata celular físicamente universal", Actas de la sexta Conferencia de Innovaciones en Ciencias de la Computación Teórica (ITCS 2015) , Association for Computing Machinery , págs. 237–246, doi : 10.1145 / 2688073.2688107 , S2CID 16903144 , ECCC TR14-084.
- Schiff, Joel L. (2008), Autómatas celulares: una visión discreta del mundo , Wiley, ISBN 978-0-470-16879-0.
- Schumacher, B .; Werner, RF (2004), Autómatas celulares cuánticos reversibles , arXiv : quant-ph / 0405174 , Bibcode : 2004quant.ph..5174S.
- Seck Tuoh Mora, Juan Carlos; Chapa Vergara, Sergio V .; Juárez Martínez, Genaro; McIntosh, Harold V. (2005), "Procedimientos para calcular autómatas celulares unidimensionales reversibles" (PDF) , Physica D: Nonlinear Phenomena , 202 (1–2): 134–141, Bibcode : 2005PhyD..202..134S , doi : 10.1016 / j.physd.2005.01.018 , MR 2131890.
- Pastor, DJ; Franz, T .; Werner, RF (2006), "Un autómata celular cuántico universalmente programable", Physical Review Letters , 97 (2): 020502, arXiv : quant-ph / 0512058 , Bibcode : 2006PhRvL..97b0502S , doi : 10.1103 / PhysRevLett.97.020502 , PMID 16907423 , S2CID 40900768.
- Sutner, Klaus (1991), "Gráficos de De Bruijn y autómatas celulares lineales" (PDF) , Complex Systems , 5 : 19–30, MR 1116419.
- Takesue, Shinji (1990), "Propiedades de relajación de los autómatas celulares reversibles elementales", Autómatas celulares: teoría y experimento (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena , 45 (1-3): 278-284, Bibcode : 1990PhyD ... 45..379K , doi : 10.1016 / 0167-2789 (90) 90195-U , MR 1094882.
- Toffoli, Tommaso (1977), "Computación y construcción universal de autómatas celulares reversibles", Journal of Computer and System Sciences , 15 (2): 213-231, doi : 10.1016 / S0022-0000 (77) 80007-X , MR 0462816.
- Toffoli, Tommaso ; Margolus, Norman (1987), Cellular Automata Machines: A New Environment for Modeling , MIT Press, ISBN 9780262200608.
- Toffoli, Tommaso ; Margolus, Norman (1990), "Autómatas celulares invertibles: una revisión", Physica D: Nonlinear Phenomena , 45 (1-3): 229-253, Bibcode : 1990PhyD ... 45..229T , doi : 10.1016 / 0167- 2789 (90) 90185-R , MR 1094877.
- Vichniac, Gérard Y. (1984), "Simulando la física con autómatas celulares", Physica D: Nonlinear Phenomena , 10 (1-2): 96-115, Bibcode : 1984PhyD ... 10 ... 96V , doi : 10.1016 / 0167-2789 (84) 90253-7 , MR 0762657.
- Watrous, John (1995), "Sobre autómatas celulares cuánticos unidimensionales", Actas del 36º Simposio anual sobre los fundamentos de la informática (Milwaukee, WI, 1995) , Los Alamitos, CA: IEEE Computer Society Press, págs. 528– 537, doi : 10.1109 / SFCS.1995.492583 , MR 1.619.103 , S2CID 7441203.
- Wolfram, Stephen (1984), "Autómatas celulares como modelos de complejidad" (PDF) , Nature , 311 (5985): 419–424, Bibcode : 1984Natur.311..419W , doi : 10.1038 / 311419a0 , S2CID 4237923.
- Wolfram, Stephen (2002), Un nuevo tipo de ciencia , Wolfram Media, ISBN 1-57955-008-8, MR 1920418