Autómata celular reversible

Un autómata celular reversible unidimensional con nueve estados. En cada paso, cada célula copia la forma de su izquierda y el color de su derecha.

Un autómata celular reversible, es un autómata celular en el que cada configuración tiene un predecesor único. Es una cuadrícula regular de celdas, cada una de las cuales contiene un estado dibujado a partir de un conjunto finito de estados. Esta cuadrícula tiene 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 únicamente a partir de los estados actualizados de todas las celdas.

Autómata Finito

Un autómata finito, es una máquina abstracta que cambia de estado dependiendo de la entrada que reciba, y su salida, algunas veces, puede estar formada por otra cadena. Los autómatas finitos son utilizados, generalmente, para reconocer lenguajes regulares, es decir, una palabra se podrá considerar válida, sólo si pertenece a un lenguaje determinado. Estos son utilizados para modelar el comportamiento de dispositivos mecánicos o de sistemas naturales, sistemas cuyo comportamiento actual depende del pasado.

Un autómata finito (AF) se define como una tupla

AF = (Q,,,Q0,F)

Donde:

1. Q = {q0,q1,...,qn}, el conjunto (finito) de los estados internos de la unidad de control.
2. Un alfabeto Σ, llamado alfabeto de entrada o alfabeto de cinta. Todas las cadenas que procesa AF pertenecen a Σ∗.
3. La función δ de transición del autómata

δ : Q×Σ → Q (q,s)

δ → δ(q,s)

1. Q0∈ Q, estado inicial.
2. F ⊆ Q, conjunto de estados finales o de aceptación. F debe ser distinto de ∅; es decir, debe haber por lo menos un estado de aceptación.

El autómata recibe una cadena de entrada M. Cuando el autómata recibe el primer símbolo de M este se encuentra en el estado inicial o Q0. La función de transición δ, también llamada dinámica del autómata, es la lista de instrucciones que utiliza AF para procesar todas las entradas. Dependiendo de la entrada, el autómata cambia de estado según la función de transición. Una vez el autómata haya escaneado uno de los símbolos este no puede retornar a este o sobreescribirlo, cuando el autómata recibe el último de los símbolos este finalizara el proceso y dependiendo si el lenguaje de la cadena pertenece al lenguaje reconocido por el autómata, este se detendrá en un estado de aceptación o rechazo.

Si para los estados p,q existe x ∈ *, tal que δ(p,x)→q, se dice que q es alcanzable desde p. AF es conexo si existe un estado q existe un x ∈ * tal que  δ(Q0,x)= q. Se dice que p y q son fuertemente conexos si p es alcanzable desde q y viceversa, AF es fuertemente conexo si para cada par de estados de AF son fuertemente conexos.

Existen 2 tipos de autómatas finitos, los deterministas y los no deterministas los cuales serán definidos a continuación.

Autómata finito determinista

Un autómata finito determinista (AFD) tiene para cada estado q y para cada sımbolo s ∈ Σ, la función de transición δ(q,s) siempre está definida y es un único estado. Esto implica que cualquier cadena de entrada se procesa completamente y de manera única.

Autómata finito no determinista

Un autómata finito no determinista (AFN) se diferencia de un AFD por la posibilidad de que una entrada se pueda procesar de varias formas o que haya procesamientos abortados.

Un AFN puede ser definido como una tupla, que a excepción de la función de transición ∆, el resto de componentes tienen el mismo significado que en un autómata finito.

AFN = (Q,,∆,Q0,F)

La función ∆ de transición del autómata ∆ está definida como :

∆: Q×Σ → ℘(Q)

(q,s) 7→ ∆(q,s) = {Q_i1,Q_i2,...,Q_ik}

donde ℘(Q) es el conjunto de subconjunto de Q.

Si bien esto implicaría que solo los autómatas deterministas pueden ser reversibles, debido a que solo estos pueden tener en sus estados una relación uno a uno con sus sucesores.

Máquina de Turing

La máquina de Turing, presentada por Alan Turing en 1936, es el modelo matemático de un dispositivo que se comporta como un autómata finito y que dispone de una cinta de longitud infinita en la que se pueden leer, escribir o borrar símbolos.

Existen otras versiones con varias cintas, deterministas o no, etc., pero todas son equivalentes (respecto a los lenguajes que aceptan).

Uno de los teoremas más importantes sobre las máquinas de Turing es que pueden simular el comportamiento de una computadora (almacenamiento y unidad de control). Por ello, si un problema no puede ser resuelto por una de estas máquinas, entonces tampoco puede ser resuelto por una computadora (problema indecidible, NP).La notación de las máquinas de Turing es sencilla y exacta, por lo que es más cómodo trabajar con ellas a la hora de estudiar qué problemas son decidibles (P) y cuáles indecidibles (NP).

Por el momento la relación de inclusión entre P y NP está por demostrar, aunque sí sabemos que

P⊆NP

Además, diremos que los lenguajes aceptados por los Autómatas Finitos (Deterministas o no, con o sin transiciones-ε, con o sin pila...) pueden ser aceptados también por alguna máquina de Turing.

Definición de la Máquina de Turing

Llamamos Máquina de Turing (ó MT) a

M=(Q,Σ,T,δ,q0,B,F)

donde

• Q es el conjunto finito de estados que denotaremos por

q0,q1,q2,...

• Σ es el alfabeto, que es el conjunto finito de símbolos de entrada.
• Τ es el conjunto de símbolos de cinta, El alfabeto es un subconjunto de Τ.
• q₀ es el estado inicial, es el estado en el que se encuentra inicialmente la MT.
• B es un elemento de Σ, es el símbolo en blanco. Se encuentra en todas las casillas de la cinta que no tienen un símbolo de entrada.
• F es el conjunto de estados finales.
• δ es la función de transiciones.

La expresión

δ(q,X)=(p,Y,D)

indica que en el estado q, si la cabeza de la MT señala al símbolo de cinta X, entonces la MT escribe el símbolo de cinta Y en la casilla actual (cambia X por Y ) y mueve la cabeza una casilla hacia D (D puede ser derecha, R; o izquierda, L) y pasa al estado p.

La cinta de la MT está formada por infinitas casillas. Inicialmente, la palabra de entrada (una concatenación de símbolos del alfabeto) se encuentra escrita en casillas consecutivas de la cinta y la cabeza señala al primer símbolo de la palabra. Todas las otras casillas (hacia la izquierda y la derecha) contienen el símbolo en blanco.

Lenguaje de una Máquina de Turing

El lenguaje de una Máquina de Turing

M=(Q,Σ,T,δ,q0,B,F)

es

L(M):={w∈Σ∗ : q0w⊢∗ αpβ,p∈F,α,β∈T∗}

Es decir, las w de Σ^* tales que la máquina de Turing alcanza un estado de aceptación.

Autómatas Celulares

Los Autómatas Celulares surgen con la necesidad del matemático húngaro John von Neumann, que intentaba modelar una máquina que fuera capaz de autorreplicarse llegando a un modelo matemático sobre una red rectangular.

El modelo inicial fue interpretado en sus principios como un conjunto de células que crecen, se reproducen y mueren a medida que pasa el tiempo, a esta similitud se le debe el nombre de Autómata Celular.

Un Autómata Celular es un modelo matemático para un sistema dinámico compuesto por un conjunto de celdas o células que adquieren distintos estados o valores; Estos estados son alterados de un instante a otro en unidades de tiempo discretas, es decir que se puede cuantificar con valores enteros. de esta manera este conjunto de células logran una evolución según una determinada expresión matemática, que es sensible a los estados de las células vecinas, la cual se conoce como regla de transición local.

El aspecto fundamental de estos autómatas son su capacidad de lograr una serie de propiedades que surgen de la propia dinámica local a través del paso del tiempo y no desde un inicio, dependiendo esta de única y exclusivamente la configuración inicial del sistema.

Elementos de un Autómata Celular

La definición de un Autómata Celular requiere mencionar sus elementos básicos:

• Arreglo Regular:

Ya sea un plano de 2 dimensiones o un espacio-dimensional, este es el espacio de evoluciones, y cada división homogénea de arreglo es llamada célula.

• Conjunto de Estados:

Es finito, y cada elemento o célula del arreglo toma un valor de este conjunto de estados. También se denomina alfabeto.Puede ser expresado en valores o colores.

• Configuración Inicial:

Consiste en asignar un estado a cada una de las células del espacio de evolución inicial del sistema.

• Vecindades:

Define el conjunto contiguo de células y posición relativa respecto a cada una de ellas. A cada vecindad diferente corresponde un elemento del conjunto de estados.

• Función Local:

Es la regla de evolución que determina el comportamiento del Autómata Celular. Se conforma de una célula central y sus vecindades.Define cómo debe cambiar de estado cada célula, dependiendo de los estados anteriores de sus vecindades. Puede ser una expresión algebraica o un grupo de ecuaciones.

Tipos de Vecindades

Para los Autómatas Celulares, el concepto de vecindad es indispensable, puesto que sin él, la función de transición o función de evolución carece de sentido, puesto  que esta depende del estado de las células vecinas. Dos tipos de vecindades más comúnmente utilizadas son:

• Vecindad de Moore:

Se define como el conjunto de las ocho celdas que rodean una celda central en un enrejado cuadrado.

• Vecindad de Von Neumann:

Se define como el conjunto de las cuatro celdas que rodean ortogonalmente a una celda central en un enrejado cuadrado bidimensional.

Aplicaciones

Los Autómatas Celulares tienen una complejidad bastante elevada dependiendo directamente de las reglas planteadas para su evolución. Al ser estos sistemas dinámicos, son bastante relevantes en el estudio y representación de estos mismos, como lo pueden ser la propagación de enfermedades al estar en contacto con tus vecinos, la regulación del tránsito en tu ciudad, el comportamiento de distintas especies dentro de una reacción química, e inclusive a visualizar como es el comportamiento y la velocidad a la que se esparce un rumor. Un ejemplo claro y conciso sobre el funcionamiento y capacidad de procesamiento de un Autómata Celular, es “El Juego de la Vida” que con solo un par de reglas logra crear una cantidad inmensa de posibilidades como configuraciones que sin importar el paso del tiempo de quedan sin ningún cambio, algunas otras que tienen ciclos, es decir, a partir de una serie de pasos (periodo) desde una configuración inicial, vuelven a llegar a esta misma configuración inicial y este ciclo continúa, este sistema es tan interesante que múltiples matemáticos lo han analizado y terminaron demostrando que este sistema tiene tanta capacidad expresiva como cualquier computador, cualquier cálculo que este pueda hacer, el juego de la vida lo puede representar con configuraciones iniciales adecuadas, ya que este (teóricamente hablando) es equivalente a una máquina universal de turing, es decir, todo lo que se puede computar algorítmicamente se puede computar en el juego de la vida.

La regla 30 (Rule 30) es una regla de un AC unidimensional introducido en el 83 por Stephen Wolfram, lo interesante de Rule 30 es que produce patrones aleatorios a partir de unas reglas muy bien definidas, su uso principal es el de generar números de manera aleatoria y se propuso como un posible cifrado para la criptografía.

El juego de la vida

Véase también: Juego de la vida

Fue diseñado por el matemático británico John Horton Conway en 1970 y publicado por primera vez en la revista Scientific American. El juego se tornó en centro de estudio por la comunidad científica, dado que es equivalente a una Máquina universal de Turing, es decir, que todo lo que se puede computar algorítmicamente se puede computar en el Juego de la vida.

El juego se basa en un Autómata celular simple con una cuadrícula de dos dimensiones donde las células pueden tener dos estados posibles: viva o muerta, que se pueden representar con booleanos como  1 o 0. La función de evolución está dada por las siguientes reglas:

• Para una célula muerta con exactamente tres células vecinas vivas, su estado pasa de muerta a viva para el siguiente turno, representando que la célula ha “nacido”.
• Una célula viva con 2 o 3 células vecinas vivas sigue viva, en otro caso muere.

El juego comenzó como un desafío matemático y con connotaciones significativas en el ámbito de las ciencias de la computación, pero pronto pasó a ser el eje central de la comunidad científica debido a la cantidad de patrones y desarrollos o “evoluciones” que tenían unos sistemas dependiendo única y exclusivamente de la configuración inicial de este Autómata Celular.

La versatilidad de la cual disponen estos autómatas nos permite considerar el estudio de muchos sistemas dinámicos en la vida tanto natural como cotidiana del planeta y de la humanidad, para encontrar soluciones relevantes a problemas actuales, o simplemente para ayudarnos a comprender un poco más el mundo que nos rodea. Un caso particular interesante para el estudio de sistemas basados en termodinámica general y física de partículas es el concepto de invertibilidad, a lo cual asociaremos una clase particular de Autómatas llamados Autómatas Celulares Invertibles.

Reversibilidad o Invertibilidad

Para poder hablar de autómatas celulares reversibles primero se tiene que hablar del concepto de reversibilidad y su relación con los autómatas.

Definimos reversibilidad como la cualidad de un sistema de ir a través de una serie de cambios ya sea hacia “adelante” o hacia “atrás” sin presentar alteraciones en estos sistemas, es decir, la cualidad de regresar o avanzar hacia etapas que previamente ya se habían visitado sin que estas presenten cambios.

En concreto hablando de la reversibilidad de una forma matemática tenemos una función inyectiva, o uno a uno, en donde cada entrada solo tiene una salida  y viceversa siendo de la forma y=f(x).

Un ejemplo  de reversibilidad es el operador lógico NEGACIÓN, y = ¬x, en donde “y” es nuestra salida y “x” nuestra entrada. Tenemos que para una entrada inicial de I nuestra salida será 0 y para una entrada de 0 tendremos una salida de I, volviendo así al estado inicial. Por el lado contrario tenemos operadores lógicos tales con “OR”(O) que para una misma salida tienen múltiples entradas lo que lo descarta como una función inyectiva y por ende no es reversible; así en un OR con dos entradas y una salida I, habrá tres posibles entradas, siendo estas (I,I)(I,0)(0,I). A partir de estos ejemplos podemos extraer información útil para identificar cuando una función es reversible como por ejemplo tener el mismo número de entradas y salidas.

Autómatas Celulares Reversibles

Se conocen varios métodos para definir reglas de autómatas celulares que son reversibles, de los cuales enumeramos y explicamos algunos a continuación.

Autómata Celular de Bloque

Un autómata celular de bloque es aquel que, con el paso del tiempo, sus celdas se van dividiendo en bloques, y esta misma transformación se va aplicando a cada uno de dichos bloques de forma independiente. Típicamente, tal autómata usa más de una partición en bloques, y rota entre las mismas.

Para que un autómata celular de bloque 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 bloque es reversible, la versión de su dinámica invertida en el tiempo también se puede describir como un autómata celular de bloque con la misma estructura, utilizando una secuencia de particiones de celdas invertida en el tiempo en bloques, y con la función de transición para cada bloque siendo la función inversa de la regla original.

Simulación de Autómata Reversible

Toffoli mostró cómo incrustar cualquier regla autómata celular d- dimensional irreversible en una regla -dimensional reversible ( d + 1) . Cada porción de dimensión d 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.

Morita describe otro tipo de simulació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 celda 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. La información que sería destruida por los pasos irreversibles del autómata simulado se envía de la configuración a la región inactiva infinita del autómata simulador. 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 preserva con precisión el comportamiento del autómata simulado, como si todas sus celdas se estuvieran actualizando simultáneamente.

Autómata Celular 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. En esta técnica, el estado de cada celda en el autómata. en el momento 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 vecindad 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 se puede calcular mediante el mapeo de cada vecindario a la permutación inversa y proceder de la misma manera.

Paisaje Conservado

Un autómata celular unidimensional encontrado por Patt (1971) usa un vecindario que consta de cuatro celdas contiguas. En este autómata, una célula cambia su estado cada vez que ocupa la 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 a la celda volteada continúa presente después de la transición. En el siguiente paso, la celda en la misma posición "?" cambiará de nuevo, volviendo a su estado original. Por lo tanto, este autómata es su propio inverso, y es reversible.

Condiciones de Reversibilidad

Un autómata celular es reversible cuando satisface cualquiera de las siguientes condiciones, todas las cuales son matemáticamente equivalentes entre sí:

• Cada configuración del autómata tiene un predecesor único que se asigna a ella por la regla de actualización.
• La regla de actualización del autómata es una biyección.
• 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. Esta condición obviamente está implícita por 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 cada regla de actualización inyectiva es biyectiva.
• La dinámica invertida en el tiempo 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 regla de actualización del autómata es un automorfismo del sistema dinámico de desplazamiento definido por el espacio de estado y las traducciones de la red de celdas.

Enlaces externos

1. Toffoli, T. and Margolus, N. (1987). Cellular automata machines. Cambridge, Massachusetts: MIT.
2. Toffoli, Tommaso (1977), "Computation and construction universality of reversible cellular automata", Journal of Computer and System Sciences, 15 (2): 213–231.
3. Morita, Kenichi (1995), "Simulación reversible de autómatas celulares irreversibles unidimensionales", Teoría de la computación , 148 (1): 157-163.
4. Patt, YN (1971), Inyecciones de tamaño de vecindario tres y cuatro en el conjunto de configuraciones de los infinitos autómatas de teselación unidimensionales de celdas de dos estados , Informe técnico ECON-N1-P-1, Ft. Monmouth, NJ 07703
5. http://delta.cs.cinvestav.mx/~mcintosh/comun/tesismaestria/seck/node22.html
6. http://www.jgiesen.de/rule30/index.html

• Datos: Q7318293