Autómata celular reversible

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 ir en cada celda, una vecindad que asocia cada celda con un conjunto finito de celdas cercanas, y una regla de actualización 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 consiste solo en 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 a partir de sus estados actuales, porque para cada celda los estados anterior y actual 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 valor, es necesariamente reversible. ^{[ 3 ]} Toffoli y Margolus (1990) llaman a este tipo de autómatas celulares reversibles, en los que el estado de cada celda depende solo del estado anterior de una celda vecina, "triviales". 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 el mapa de desplazamiento . ^{[ 4 ]}

De forma un poco menos trivial, supongamos que las celdas forman nuevamente 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 valores posibles. Definamos una función de transición que establece la parte izquierda de una celda como la parte izquierda de su vecina izquierda y la parte derecha de una celda como la parte derecha de su vecina derecha. Es decir, si el estado de la vecina izquierda es ( a , b ) y el estado de la vecina derecha es ( c , d ) , el nuevo estado de una celda es el resultado de combinar estos estados mediante una operación de pares × definida por la ecuación ( a , b ) × ( c , d ) = ( a , d ) . Un ejemplo de esta construcción se muestra en la ilustración, en la que la parte izquierda se representa gráficamente como una forma y la parte derecha como un color; en este ejemplo, cada celda se actualiza con la forma de su vecina izquierda y el color de su vecina derecha. Este autómata es reversible: los valores del lado izquierdo de cada par migran hacia la derecha y los del lado derecho hacia la izquierda, de modo 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 puede realizarse mediante un autómata celular reversible unidimensional con diez estados por celda (los diez dígitos decimales). Cada dígito del producto depende únicamente de un vecindario 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 únicamente de un número limitado 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 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 basados ​​en la función "o exclusivo" proporcionan una aproximación . En la Regla 90, el estado de cada celda es el "o exclusivo" de los estados anteriores de sus dos vecinas. Este uso del "o exclusivo" hace que la regla de transición sea localmente invertible, en el sentido de que cualquier subsecuencia contigua de estados puede generarse mediante esta regla. 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 celdas tiene exactamente cuatro predecesores posibles, mientras que las reglas reversibles requieren tener exactamente un predecesor por configuración. ^{[ 8 ]}

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 desaparecen por completo, por lo que la configuración en la que todas las células están muertas tiene muchos precedentes, y también tiene patrones del Jardín del Edén sin precedentes. Sin embargo, otra regla llamada "Critters" por sus inventores, Tommaso Toffoli y Norman Margolus , es reversible y tiene un comportamiento dinámico similar al de la Vida. ^{[ 9 ]}

La regla de Critters es un autómata celular de bloques 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 demás. Su función de transición invierte el estado de cada celda en un bloque que no tenga exactamente dos celdas vivas y, además, rota 180° los 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 parte de un campo más pequeño de células aleatorias centrado 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 de Critters también puede admitir naves espaciales más complejas de velocidades variables, así como osciladores con infinitos períodos diferentes. ^{[ 9 ]}

Un autómata celular de bloques es un autómata en el que, en cada paso de tiempo, las celdas del autómata se dividen en subconjuntos congruentes (llamados bloques), y se aplica la misma transformación de forma independiente a cada bloque. Normalmente, dicho autómata 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 frecuentemente utilizada de este diseño, llamada vecindario 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 manera, las cuatro celdas en cada 2  ×  2 pertenecen a cuatro cuadrados diferentes de 2  ×  2 de la partición anterior. ^{[ 11 ]} La regla de Critters discutida anteriormente es un ejemplo de este tipo de autómata.

Diseñar reglas reversibles para autómatas celulares de bloques y determinar si una regla dada es reversible es sencillo: para que un autómata celular de bloques sea reversible, es necesario y suficiente que la transformación aplicada a los bloques individuales en cada paso del autómata sea reversible. Cuando un autómata celular de bloques es reversible, la versión invertida de su dinámica también puede describirse como un autómata celular de bloques con la misma estructura de bloques, utilizando una secuencia invertida de particiones de celdas en bloques, y con la función de transición para cada bloque siendo la función inversa de la regla original. ^{[ 10 ]}

Toffoli (1977) demostró cómo integrar cualquier regla irreversible de un autómata celular d -dimensional en una regla reversible ( d +1) -dimensional. Cada segmento d -dimensional de la nueva regla reversible simula un único paso temporal de la regla original. De esta forma, Toffoli demostró que muchas características de los autómatas celulares irreversibles, como la capacidad de simular máquinas de Turing arbitrarias , también podían extenderse a los autómatas celulares reversibles.

Como Toffoli conjeturó y Hertling (1998) demostró, el aumento de dimensión que conlleva el método de Toffoli es un precio necesario por su generalidad: bajo supuestos suaves (como la invariancia de traslación de la incrustación), cualquier incrustación de un autómata celular que tenga un Jardín del Edén en un autómata celular reversible debe aumentar la dimensión.

Morita (1995) describe otro tipo de simulación que no obedece a las suposiciones 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 exista un estado "inactivo" o "muerto", de modo que si una celda y todas sus vecinas están inactivas, la celda permanece inactiva en el siguiente paso. La simulación utiliza un autómata celular de bloques reversible de la misma dimensión que el autómata irreversible original. La información que se destruiría con los pasos irreversibles del autómata simulado se envía, en cambio, fuera de la configuración hacia la región inactiva infinita del autómata que simula. 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 simula. Sin embargo, la simulación conserva con precisión el comportamiento del autómata simulado, como si todas sus celdas se actualizaran simultáneamente. Mediante este método es posible demostrar que incluso los autómatas celulares reversibles unidimensionales son capaces de realizar computación universal. ^{[ 12 ]}

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 autores en 1984. ^{[ 13 ]} En esta técnica, el estado de cada celda del autómata en el instante t es una función tanto de su vecindario en el instante t − 1 como de su propio estado en el instante t − 2 . Específicamente, la función de transición del autómata asigna a cada vecindario en el instante t − 1 una permutación del conjunto de estados y luego aplica esa permutación al estado en el instante t − 2 . La dinámica inversa del autómata se puede calcular asignando a cada vecindario la permutación inversa y procediendo de la misma manera. ^{[ 14 ]}

En el caso de autómatas con estados binarios (cero o uno), solo existen dos permutaciones posibles de los estados (la permutación identidad y la permutación que intercambia los dos estados), las cuales pueden representarse como la disyunción exclusiva 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 instante t − 1 , y luego calculando la disyunción exclusiva de estos estados con los estados en el instante t − 2 para determinar los estados en el instante t . Sin embargo, el comportamiento del autómata celular reversible determinado de esta manera puede no tener ninguna semejanza con el comportamiento del autómata celular del que se definió. ^{[ 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 únicamente del 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. ^{[ 14 ]}

Un autómata celular unidimensional hallado por Patt (1971) utiliza un vecindario formado por cuatro celdas contiguas. En este autómata, una celda cambia de estado cuando ocupa la posición "?" en el patrón "0?10". No puede haber dos patrones de este tipo superpuestos, por lo que el mismo "paisaje" que rodea a la celda cambiada permanece presente tras la transición. En el siguiente paso, la celda en la misma posición "?" volverá a cambiar de estado, regresando a su estado original. Por lo tanto, este autómata es su propio inverso y es reversible. Patt realizó una búsqueda exhaustiva de todos los autómatas celulares unidimensionales de dos estados con vecindarios pequeños; esta búsqueda condujo al descubrimiento de este autómata y demostró que era el autómata celular reversible unidimensional de dos estados no trivial más simple posible. No existen autómatas reversibles de dos estados no triviales 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 considerarse, en retrospectiva, como un ejemplo de la técnica del "paisaje conservado" para el diseño de 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 vecinas que no cambian de estado. De esta forma, la existencia del mismo patrón puede utilizarse para desencadenar el cambio inverso en la dinámica temporal invertida del autómata. El autómata de Patt tiene una dinámica muy simple (todas las secuencias cíclicas de configuraciones tienen longitud dos), pero los autómatas que utilizan la misma técnica del paisaje conservado con más de un patrón desencadenante son capaces de un comportamiento más complejo. En particular, pueden simular cualquier autómata celular de segundo orden. ^{[ 15 ]}

El modelo SALT de Miller y Fredkin (2005) es un caso especial de la técnica del paisaje conservado. En este modelo, las celdas de una cuadrícula entera se dividen en subconjuntos pares e impares. En cada paso de tiempo, ciertos pares de celdas de una paridad se intercambian, según la configuración de las celdas cercanas de la otra paridad. Las reglas que utilizan este modelo pueden simular la computadora de bolas de billar ^{[ 16 ]} o admitir largas cadenas de celdas vivas que pueden moverse a diferentes velocidades o vibrar a diferentes frecuencias ^{[ 17 ] .}

Amoroso y Patt (1972) demostraron por primera vez que el problema de comprobar la reversibilidad de un autómata celular unidimensional dado tiene una solución algorítmica. Culik (1987) y Sutner (1991) propusieron algoritmos alternativos basados ​​en la teoría de autómatas y en grafos de De Bruijn , 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 dicha función es inyectiva en los subconjuntos de configuraciones periódicas (que repiten la misma subcadena infinitamente en ambas direcciones). Define un transductor no determinista de estados finitos que realiza la regla de transición del autómata en cadenas periódicas. Este transductor funciona memorizando la vecindad del autómata al inicio de la cadena y entrando en un estado de aceptación cuando dicha vecindad, concatenada al final de la entrada, haría que sus transiciones, elegidas de forma no determinista, fueran correctas. A continuación, Culik intercambia la entrada y la 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 comprobar si el transductor resultante, tras el intercambio, asigna cada entrada a una única salida. ^{[ 23 ]}
• Sutner define un grafo dirigido (un tipo de grafo de De Bruijn ) en el que cada vértice representa un par de asignaciones de estados para las células en una secuencia contigua de células. La longitud de esta secuencia se elige de forma que sea una unidad menor que el tamaño del vecindario del autómata. Una arista en el grafo de Sutner representa un par de secuencias de células que se superponen en todas menos en una, de modo que la unión de las secuencias constituye un vecindario completo en el autómata celular. Cada arista de este tipo está dirigida desde la subsecuencia superpuesta de la izquierda a la subsecuencia de la derecha. Las aristas solo se incluyen en el grafo cuando representan asignaciones de estado compatibles en las partes superpuestas de sus secuencias de células, y cuando la regla del autómata (aplicada al vecindario determinado por la arista potencial) daría los mismos resultados para ambas asignaciones de estados. Al realizar un análisis de conectividad fuerte en tiempo lineal de este grafo, 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 grafo 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 estados del autómata de entrada. ^{[ 24 ]} Un algoritmo relacionado de Hillman (1991) determina si una regla dada es sobreyectiva cuando se aplica a arreglos de longitud finita de celdas con condiciones de contorno periódicas y, de ser así, para qué longitudes.

Para un autómata celular de bloques, 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 bloques con la función de transición inversa. ^{[ 10 ]}

Sin embargo, para 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 del recubrimiento del plano con teselas de Wang , conjuntos de teselas cuadradas con marcas en sus bordes que restringen qué pares de teselas pueden encajar borde con borde. Kari define un autómata celular a partir de un conjunto de teselas de Wang, de tal manera que el autómata no es inyectivo si y solo si el conjunto de teselas dado puede recubrir todo el plano. Su construcción utiliza el vecindario de von Neumann y celdas con un gran número de estados. En el mismo artículo, Kari también demostró que es indecidible probar si una regla de autómata celular dada de dos o más dimensiones es sobreyectiva (es decir, si tiene un Jardín del Edén ).

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 de como máximo n ^{m − 1} − m + 1 celdas. Se sabe que este límite es estricto para m = 2 : existen autómatas celulares reversibles de n estados con vecindades de dos celdas cuya dinámica invertida en el tiempo forma un autómata celular con un tamaño de vecindad exactamente n − 1. ^{[ 25 ]}

Para cualquier entero m, solo existen un número finito de autómatas celulares reversibles bidimensionales de m estados con la vecindad de von Neumann. Por lo tanto, existe una función bien definida f ( m ) tal que todas las reversas de los autómatas celulares de m estados con la vecindad de von Neumann utilizan una vecindad con radio como máximo f ( m ) : simplemente sea f ( m ) el máximo, entre todos los autómatas celulares reversibles de m estados finitos, del tamaño de vecindad necesario para representar la dinámica del autómata invertida en el tiempo. 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 ]}

Una conocida clasificación de autómatas celulares propuesta por 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, esa misma aleatoriedad uniforme se mantiene para todos los estados subsiguientes. Por lo 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, aún es posible distinguir entre diferentes autómatas celulares reversibles analizando el efecto de las perturbaciones locales en el comportamiento del autómata. Modificar el estado inicial de un autómata celular reversible puede provocar que los cambios en estados posteriores permanezcan dentro de una región delimitada, se propaguen de forma irregular pero ilimitada, o se extiendan rápidamente. Wolfram (1984) enumera reglas de autómatas celulares reversibles unidimensionales que exhiben estos tres tipos de comportamiento.

Trabajos posteriores de Wolfram identifican el autómata unidimensional de la Regla 37R como particularmente interesante en este sentido. Al ejecutarse en una matriz finita de celdas con condiciones de contorno periódicas, partiendo de una pequeña semilla de celdas aleatorias centradas en un vecindario vacío más amplio, tiende a fluctuar entre estados ordenados y caóticos. Sin embargo, con las mismas condiciones iniciales en un conjunto ilimitado de celdas, sus configuraciones tienden a organizarse en varios tipos de partículas simples en movimiento. ^{[ 26 ]}

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 bigrupoide semicentral como una estructura algebraica que consiste en un conjunto S de elementos y dos operaciones → y ← sobre pares de elementos, que satisfacen los dos axiomas de igualdad:

• para todos los elementos a , b y c en S , ( a → b ) ← ( b → c ) = b , y
• para todos los elementos a , b y c en S , ( a ← 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. Estos axiomas generalizan el axioma definitorio (para una única operación binaria ) de un grupoide central . ^{[ 5 ]}

Como argumenta Boykett, cualquier autómata celular reversible unidimensional es equivalente a un autómata en forma rectangular , en el que las celdas se desplazan media unidad en cada paso de tiempo, y en el que tanto la evolución hacia adelante como la inversa del autómata tienen vecindarios de solo dos celdas, separadas media unidad en cada dirección. Si un autómata reversible tiene vecindarios de más de dos celdas, puede simularse mediante 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 bigrupoide semicentral son precisamente las condiciones requeridas para que las funciones de transición hacia adelante y hacia atrás de estos vecindarios de dos celdas sean inversas entre sí. Es decir, cada bigrupoide 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. Todo autómata celular reversible unidimensional es equivalente a uno de esta forma. ^{[ 5 ]}

Boykett utilizó esta formulación algebraica como base para algoritmos que enumeran exhaustivamente todos los posibles autómatas celulares reversibles no equivalentes. ^{[ 27 ]}

Cuando los investigadores diseñan autómatas celulares reversibles para simular sistemas físicos, suelen incorporar en el diseño las leyes de conservación del sistema; por ejemplo, un autómata celular que simula un gas ideal debe conservar el número de partículas de gas y su momento total , ya que de lo contrario no proporcionaría una simulación precisa. Sin embargo, también se han realizado 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 magnitud conservada que se mide 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. Dicha magnitud se conserva si, siempre que toma un valor finito, ese valor permanece automáticamente constante en cada paso de tiempo del autómata, y en este caso se denomina invariante de orden k del autómata. ^{[ 28 ]}

Por ejemplo, recordemos el autómata celular unidimensional definido como ejemplo de una banda rectangular , en la que los estados de las celdas son pares de valores ( l , r ) extraídos de los conjuntos L y R de valores izquierdos y derechos, el valor izquierdo de cada celda se mueve hacia la derecha en cada paso de tiempo, y el valor derecho de cada celda se mueve hacia la izquierda. En este caso, para cada valor izquierdo o derecho x de la banda, se puede definir una cantidad conservada, el número total de celdas que tienen ese valor. Si hay λ valores izquierdos y ρ valores derechos, entonces hay λ + ρ − 2 invariantes de primer orden independientes, y cualquier invariante de primer orden puede representarse como una combinación lineal de estos fundamentales. Las cantidades conservadas asociadas con los valores izquierdos fluyen uniformemente hacia la derecha a una tasa constante: es decir, si el número de valores izquierdos iguales a x dentro de alguna región C de la línea toma un cierto valor en el tiempo 0 , entonces tomará el mismo 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, tras lo cual su regla de transición puede factorizarse en la acción de un bigrupoide semicentral idempotente (una regla reversible para la cual las regiones de celdas con un único valor de estado 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) se comportan necesariamente 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. Los invariantes de primer orden para el autómata global son entonces exactamente los invariantes para el levantamiento idempotente que dan igual 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 a como lo hacen en el levantamiento idempotente, fluyendo de forma no uniforme y con interacciones. ^{[ 29 ]}

En los sistemas físicos, el teorema de Noether establece 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, ya que, en lugar de estar gobernado por la energía del sistema, el comportamiento del autómata está codificado en sus reglas, y se garantiza que el autómata obedezca ciertas simetrías (invariancia traslacional tanto en el espacio como en el tiempo) independientemente de las leyes de conservación que pueda obedecer. No obstante, las cantidades conservadas de ciertos sistemas reversibles se comportan de forma 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 provocar 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 permite analizarlo mediante métodos de la física clásica. ^{[ 30 ]}

Un autómata de gas reticular es un autómata celular diseñado para simular el movimiento de partículas en un fluido o un gas ideal . En dicho sistema, las partículas de gas se mueven en línea recta con velocidad constante hasta que experimentan una colisión elástica con otras partículas. Los autómatas de gas reticular simplifican estos modelos al permitir solo un número constante de velocidades (normalmente, una sola velocidad y cuatro o seis direcciones de movimiento) y al simplificar los tipos de colisión posibles. ^{[ 31 ]}

Específicamente, el modelo de gas reticular HPP consiste en partículas que se mueven a velocidad unitaria en las cuatro direcciones paralelas a los ejes. Cuando dos partículas se encuentran en la misma línea en direcciones opuestas, colisionan y se desplazan 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 cuyo comportamiento se asemeja al de los gases físicos. Sin embargo, se descubrió que obedece leyes de conservación adicionales poco realistas. Por ejemplo, el momento total dentro de cualquier línea se conserva. Además, la diferencia entre las direcciones paralelas y no paralelas a los ejes en este modelo (su anisotropía ) es excesivamente alta. El modelo de gas reticular FHP mejora el modelo HPP al tener partículas que se mueven en seis direcciones diferentes, con á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 con ángulos de 60 grados con respecto a las dos partículas entrantes. Las colisiones triples también son posibles en el modelo FHP y se manejan de manera que se preserve el momento total y se eviten las leyes de conservación adicionales 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 el autómata de gas reticular HPP como el FHP pueden implementarse con un autómata celular de bloques de dos estados utilizando el vecindario de Margolus. ^{[ 31 ]}

El modelo de Ising se utiliza para modelar el comportamiento de los sistemas magnéticos. Consiste en una matriz de celdas, cuyo estado representa un espín , 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 celdas vecinas con el mismo espín. Por lo tanto, si una celda tiene el mismo número de vecinas en ambos estados, puede cambiar su estado sin modificar la energía total. Sin embargo, este cambio solo conserva la energía si no hay dos celdas adyacentes que cambien de estado simultáneamente. ^{[ 32 ]}

Los modelos de autómatas celulares de este sistema dividen la red cuadrada en dos subconjuntos alternos y realizan actualizaciones en uno de los dos subconjuntos a la vez. En cada actualización, cada celda que puede cambiar de estado lo hace. Esto define un autómata celular reversible que puede utilizarse para investigar el modelo de Ising. ^{[ 32 ]}

Fredkin y Toffoli (1982) propusieron la computadora de bolas de billar como parte de sus investigaciones sobre 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, experimentan una colisión elástica, similar a la que se produce con las bolas de billar reales . La entrada a la computadora se codifica mediante la presencia o ausencia de partículas en ciertas pistas de entrada, y su salida se codifica de manera similar mediante la presencia o ausencia de partículas en las pistas de salida. Las pistas pueden visualizarse como cables, y las partículas como señales booleanas transportadas por esos cables. Cuando una partícula choca con 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 pistas diferentes pueden colisionar, formando una puerta lógica en su punto de colisión. ^{[ 33 ]}

Como demostró Margolus (1984) , las computadoras de bolas de billar pueden simularse mediante un autómata celular de bloques reversible de dos estados con el vecindario de Margolus. En la regla de actualización de este autómata, los bloques con exactamente una célula activa giran 180°, los bloques con dos células activas diagonalmente opuestas giran 90°, y todos los demás bloques permanecen inalterados. Estas reglas hacen que las células activas aisladas se comporten como bolas de billar, moviéndose en trayectorias diagonales. Los grupos conectados de más de una célula activa se comportan, en cambio, como los obstáculos fijos de la computadora de bolas de billar. En un apéndice, Margolus también demostró que un autómata celular de segundo orden de tres estados, utilizando el vecindario de Moore bidimensional , podría simular computadoras de bolas de billar.

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 pueden realizarse con una cantidad de energía por paso que es arbitrariamente cercana a cero. ^{[ 34 ]} Sin embargo, para realizar la computación utilizando menos energía que el límite de Landauer, no es suficiente 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 se realice de manera 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 preguntarse si todo autómata celular reversible tiene una regla de actualización localmente reversible. Kari (1996) demostró que para autómatas unidimensionales y bidimensionales la respuesta es afirmativa, y Durand-Lose (2001) demostró que cualquier autómata celular reversible podría simularse mediante un autómata celular localmente reversible (posiblemente diferente). Sin embargo, la cuestión de si toda función de transición reversible es localmente reversible permanece abierta para dimensiones superiores a dos. ^{[ 35 ]}

La regla "Tron" de Toffoli y Margolus es una regla celular de bloques reversible con el vecindario de Margolus. Cuando un bloque de 2  ×  2 celdas tiene todas el mismo estado, todas las celdas del bloque cambian de estado; en todos los demás casos, las celdas del bloque permanecen inalteradas. Como argumentan 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 la misma dinámica que la regla estándar del vecindario de Margolus mientras se ejecuta en un autómata celular asíncrono . ^{[ 36 ]}

Kari (1990) propuso el uso de autómatas celulares reversibles multidimensionales como sistema de cifrado . En su propuesta, 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, un paso hacia atrás. Kari sugiere que un sistema de este tipo podría utilizarse como 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 dada (la regla directa) debido a la indecidibilidad de la prueba de reversibilidad, por lo que la regla directa 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 utilizarse para dicho sistema, ni mostró cómo un criptosistema que utilizara este enfoque podría generar pares de claves de cifrado/descifrado.

Chai, Cao y Zhou (2005) propusieron 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 dicha regla, se ejecuta varias veces sobre una entrada para transformarla en una salida cifrada. La propiedad de reversibilidad del autómata garantiza que cualquier mensaje cifrado pueda descifrarse ejecutando el mismo sistema en sentido inverso. En este sistema, las claves deben mantenerse en secreto, ya que se utiliza la misma clave tanto para el cifrado como para el descifrado.

Los autómatas celulares cuánticos son conjuntos de autómatas cuyos estados y transiciones de estado obedecen las leyes de la dinámica cuántica . Feynman (1982) propuso los autómatas celulares cuánticos como modelo de computación, y Watrous (1995) los formalizó por primera vez . Varias nociones contrapuestas de estos autómatas siguen en investigación, muchas de las cuales requieren que los autómatas construidos de esta manera sean reversibles. ^{[ 37 ]}

Janzing (2010) se preguntó si era posible que un autómata celular fuera físicamente universal , es decir, que, para cualquier región delimitada de las celdas del autómata, debería ser posible rodear esa región con celdas cuyos estados formen un andamiaje de soporte adecuado que permita al autómata implementar cualquier transformación arbitraria sobre conjuntos de estados dentro de la región. Dicho autómata debe ser reversible, o al menos localmente inyectivo, porque los autómatas que carecen de esta propiedad presentan patrones de 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 bloques con dos estados y la vecindad de Margolis, estrechamente relacionado con los autómatas del modelo de bolas de billar y del gas reticular HPP. Sin embargo, el modelo de bolas de billar no es físicamente universal, ya que puede utilizarse para construir paredes impenetrables que impiden la lectura y transformación del estado dentro de ciertas regiones. En el modelo de Schaeffer, cada patrón se descompone finalmente en partículas que se mueven diagonalmente en cuatro direcciones. Por lo tanto, su autómata no es Turing completo . No obstante, Schaeffer demostró que es posible rodear cualquier configuración finita con un andamiaje que se descompone más lentamente que ella. Después de que la configuración se descompone en partículas, el andamiaje intercepta dichas partículas y las utiliza como entrada para un sistema de circuitos booleanos construidos dentro del andamiaje. Estos circuitos pueden utilizarse para calcular funciones arbitrarias de la configuración inicial. El andamiaje luego traduce la salida de los circuitos de nuevo en un sistema de partículas en movimiento, que convergen en la región inicial y colisionan entre sí para construir una copia del estado transformado. De esta manera, el sistema de Schaeffer puede usarse para aplicar cualquier función a cualquier región acotada del espacio de estados, lo que demuestra que esta regla del autómata es físicamente universal. ^{[ 38 ]}