Genaro Juárez Martínez
e-mail: genaro@sparcomp.cs.cinvestav.mx
Escuela Nacional de Estudios Profesionales Acatlán
Universidad Nacional Autónoma de México
D. F., México
Marzo 30, 1998
Un autómata celular, es un sistema dinámico discreto que evoluciona
en iteraciones a través de una regla determinística, tal como un sistema
dinámico; las variables del sistema cambian como una función de sus valores
actuales. Pueden ser vistos como un proceso de cómputo en paralelo, donde
los datos son la configuración inicial. Otra aproximación es que un autómata
celular es un ``universo lógico... con su propia física local". Tal como un
universo de autómata celular; no obstante su construcción matemática,
son capaces de soportar comportamientos complejos [13].
El estudio de los Autómatas Celulares se remonta desde los años 50's, época de grandes aportaciones en materia de conjuntos, expresiones regulares, bases de datos, autómatas, neurones, cibernética, máquinas finitas, computación, entre otros. Los autómatas celulares también fueron canalizados en un principio bajo fines bélicos. Los autómatas celulares pueden ser representados en dos dimensiones y en una dimensión, a los autómatas celulares en dos dimensiones se le encontró un juego ecológico llamado Life que hizo muy popular esta teoría gracias a su presentación que resulto muy llamativa. La teoría de autómatas celulares como tal a tenido altibajos a través de la historia, sin embargo se puede decir que ha pasado por tres étapas de alto grado de estudio, la primera de ellas es la etapa de John von Neumann, la segunda es de John Horton Conway y la última es de Stephen Wolfram. Aunque se han dado importantes aportaciones en estos períodos de bajo interés que han contribuido de manera relevante al estudio de dicha teoría, aunque algunas veces de manera indirecta.
Se han encontrado algunas aplicaciones dentro del campo de la biología, la química, la física, las matemáticas, la cristalografía, la termodinámica y cierta relación con la teoría del caos, la teoría fractal, vida artificial, simulación de procesos y ciencias de la computación.
El estudio de los autómatas celulares dentro del campo de la computación es uno de los principales focos de interés para muchos investigadores. Desde los inicios de la teoría de autómata celular se pretendia realizar la construcción de una máquina capaz de soportar comportamientos complejos. Se han hecho estudios sobre si una máquina de Turing [22] puede contener un autómata celular o viceversa, si esto es cierto cuales son las limitaciones y los alcances de cada una de estas máquinas. Por otra parte la representación del cómputo en paralelo es ideal para su representación en autómatas celulares.
El tema de como se manifiesta la reversibilidad en los autómatas celulares en los últimos años a sido de notable interés. Ya que hay algunas personas que tratan de buscar aplicaciones bajo estas características, tal como encriptadores de datos, almacenamiento masivo de información, por mencionar algunos. Sin embargo la teoría como tal aún se encuentra en fase de formalización matemática para posteriormente obtener una explicación real y concisa de tales fenómenos.
El presente trabajo titulado `` Grados de Reversibilidad en Autómatas Celulares Lineales", se encuentra dividido en tres partes principales: la primera consiste en el fundamento de la teoría de autómata celular donde se desglosa un poco de historia y se explica como esta constituida la estructura de los autómatas celulares en una dimensión, la segunda parte lo constituye el problema de explicar como a través de las estructuras partículares se originan los comportamientos globales que a su vez determinan el comportamiento de los mismos autómatas, la tercera y última parte la constituyen los resultados obtenidos a través de sus propiedades globales para autómatas celulares no reversibles pero que contienen grados de reversibilidad para configuraciones de cierto tamaño.
A través de todo el escrito se hizo uso del software NXLCAU (Web site http://www.cs.cinvestav.mx/mcintosh/cellular.html), desarrollado por el Dr. Harold V. McIntosh del Instituto de Ciencias de la Universidad Autónoma de Puebla (Departamento de Aplicación de Microcomputadoras, 49 Poniente 1102, Puebla.). Estos programas fueron codificados en el lenguaje de programación orientado a objetos C-Object en el sistema operativo NeXTSTEP y son de dominio público. También existe una versión del software (LCAU) compatible para el sitema operativo Ms-DOS.
El escrito fue realizado en LaTeX un derivado del formato TeX sobre el sistema operativo NeXTSTEP v3.3 y compatible con la versión de OPENSTEP, en las instalaciones del CINVESTAV (Centro de Investigación y Estudios Avanzados del IPN. Departamento de Ingeniería Eléctrica, Sección de Computación.).
El trabajo fue realizado en común acuerdo de los dos departamentos sobre un proyecto de investigación sobre `` Autómatas Celulares Lineales Reversibles", donde se han dado resultados importantes y buenos avances.
Genaro Juárez Martínez
E-mail:genaro@sparcomp.cs.cinvestav.mx