Propiedades de los Autómatas Celulares Lineales Reversibles

El problema de reversibilidad en autómatas celulares se puede plantear como un análisis del mapeo que existe del conjunto de configuraciones globales del autómata a si mismo. Si dicho mapeo es biyectivo entonces la evolución del autómata es reversible.

Figura 3.2: El mapeo biyectivo entre configuraciones globales define un autómata celular reversible

Hay que hacer notar que desde el punto de vista de comportamiento local no se puede hablar de autómatas reversibles, ya que la regla de evolución mapea un conjunto de vecindades a un conjunto de estados, esto es $\phi: {K}^{2r+1} \rightarrow K$ el cual es evidente que no es un mapeo biyectivo para $r>0$; sin embargo, el interés y por qué no decirlo, la belleza de este tipo de sistemas es que la dinámica de los mismos dependiente de reglas de comportamiento local no reversibles inducen un comportamiento global que si es reversible. La cuestión a investigar es de que forma el funcionamiento del autómata es capaz de conservar la información del sistema para que en un momento dado podamos hacer uso de esta misma y poder reconstruir las configuraciones globales anteriores; con esta idea se pueden establecer dos propiedades importantes que deben tener estos sistemas:

• En un autómata celular reversible no existe Jardín del Edén.
• Cada configuración global tiene una única configuración de la cual precede.