Existen actualmente dos campos de investigación para los autómatas, estos son debidos
a la dirección de la evolución del autómata, es decir, el problema de la evolución
hacia adelante y el problema de la Evolución Reversiva.
El problema hacia adelante, analiza características en la conducta de la evolución de
los autómatas como son ciclos, puntos fijos etc; con desarrollo de técnicas para el
análisis de los autómatas.
Por otro lado, el problema Reversivo, tiene gran importancia en la modelación
para simular características de sistemas vivos, (como Life). Se busca determinar
una reversibilidad en el tiempo, de tal forma que configuraciones pasadas puedan
ser recuperables desde cualquier otra configuración posterior a ellas, el sistema debe de
ser capaz de guardar la información [9]. Esto es,
determinar autómatas que satisfagan restricciones como generar configuraciones
inalcanzables, denominadas Jardín del Edén.
Un aspecto importante en este estudio es que los conceptos inherentes a la reversibilidad,
son muy sencillos y el nombre de cada uno de estos conceptos proporciona ideas intuitivas.
Sistema Invertible o Reversivo. Es un sistema determinístico, en ambas direcciones del tiempo, futuro y pasado.
Figure 12: Autómata (2,1) regla 15 la cual es reversible.
Regla Inversa.Regla que hace posible regresar en el tiempo.
Ancestro. Es una configuración, que por la aplicación de una regla de
evolución, ha generado una configuración siguiente.
Mapeo Local.Es el que asigna sucesores a las vecindades.
Mapeo Global. Es el que produce la sucesión de configuraciones de una
ge-neración a la siguiente.
El concepto de reversibilidad, no se aplica al mapeo local sino al mapeo global.
El estudio de los autómatas reversivos, tiene muchos problemas abiertos; no es
conocida actualmente una forma sistemática para determinar la existencia de la reversibilidad,
que se aplique a todos los autómatas, sin importar el número de estados o de vecinos.
Estas son las tres diferentes configuraciones que se pueden generar en los autómatas:
Existen conceptos fundamentales en el estudio de la reversibilidad, uno de ellos es el
concepto de la Multiplicidad Uniforme, que indica que cada cadena debe de tener tantas
formas de reproducirse como nodos en el Diagrama de de Bruijn haya. Otro concepto
muy importante es el de los Índices de Welsh, que dan una descripción de como se
comportan los ancestros.
Gustav A. Hedlund, en 1969 expuso su trabajo acerca de las propiedades de endomorfismos
y automorfismos de los sistemas dinámicos, en un lenguaje matemático muy abstracto con
muchas características topológicas. En 1978, Masakasu Nasu, des-cribió estos resultados
en una forma más amigable utilizando la Teoría de Gráficas, para incorporar unas
ideas a la Teoría de Autómatas.
Para facilitar el análisis de estas propiedades, la Teoría de Gráficas, puede
convertirse en una poderosa herramienta, ya que permite describir la evolución del
autómata en forma gráfica, mostrando también la transición de las propiedades locales
a las propiedades globales [5].
Las gráficas más importantes son:
Actualmente se estudian otro tipo de diagramas, llamados Diagramas de Welsh, los
cuales serán vistos con detalle más adelante.
Se presenta la siguiente cuestión filosófica, si la máquina constructora universal
de von Neumann hubiera sido posible, por ejemplo en un autómata que tuviera implementado
una máquina de Turing, llevaría implícitas las mismas limitaciones de la máquina de
Turing, entonces un autómata celular debe superara estas limitaciones. Si un autómata
celular puede ser modelado por una máquina de Turing, la unión de estos dos hará que
sus capacidades sean compatibles.
Lo inverosímil de esta afirmación (que pareciera verdad), surge cuando se encontró
que había autómatas que tenían configuraciones que no podían ser originadas por la
evolución. ( Jardín del Edén). La relación de estas configuraciones con el
constructor universal estaba en que, en la realización del constructor no se requería
llenar espacios con diseños arbitrarios, por el contrario creaba objetos específicos de
acuerdo a instrucciones que había recibido. La universalidad es referida a si
des-cripciones arbitrarias pueden ser seguidas y no si construcciones arbitrarias pueden
ser construidas.
Este análisis permite evaluar la conducta de los autómatas, ya que la reversibilidad
es una de las características universales de las leyes físicas y en los autómatas
celulares no se da automaticamente. Se cree que puede ser introducida pero el sistema
perderá otras propiedades importantes, para la modelación.