Caracterización del Comportamiento de los Autómatas Celulares Lineales Reversibles

Juan Carlos Seck Tuoh Mora
Depto. de Ingeniería Eléctrica, Sección Computación
CINVESTAV-IPN, Apartado Postal 14-740 México D.F
email:seck@computacion.cs.cinvestav.mx

Asesores:
Dr. Harold V. McIntosh
Dr. Sergio V. Chapa Vergara

Agosto de 1999

Resumen:

En el siguiente trabajo se analizan las transformaciones locales que operan sobre un sistema el cual consiste en un espacio celular de una dimensión. En particular, se discuten aquellas transformaciones locales que generan un comportamiento global reversible, es decir, que conservan la información del sistema.

Damos una caracterización de este tipo de transformaciones locales utilizando el trabajo desa-rrollado por Hedlund en [Hedlund 69] basado en conceptos de dinámica simbólica, combinatoria y registro de corrimientos. Para hacer más entendible esta caracterización, los resultados de Hedlund son complementados con las herramientas gráficas elaboradas por McIntosh y Nasu en [McIntosh 91b] y [Nasu 78] respectivamente.

Conjuntando las ideas anteriores con el trabajo hecho por Kari en [Kari 96], explicamos el comportamiento global reversible por medio de permutaciones en bloque y corrimientos, haciendo esta idea extensiva para toda transformación local que genere este tipo de comportamiento global.

Por último, establecemos una cota máxima para el tamaño mínimo de la transformación inversa asociada a una transformación local que induzca un comportamiento global reversible.

(Nota:El resultado mostrado en el capítulo 6 es incorrecto y actualmente esta bajo revisión y mejora utilizando otras ideas distintas a las aquí presentadas; sin embargo, se ha respetado la presentación original del escrito como una muestra del planteamiento y la relevancia que el problema abordado en este capítulo tiene.)