next up previous 
Next: Árboles Topológicos (4h) Up: Grados de Reversibilidad en Previous: Algoritmo


Conclusiones

Los autómatas celulares que presentan grados de reversibilidad para ciertas configuraciones , deden tener algunas de las siguientes características:

El estudio que se llevó a cabo se enfoco para el caso , sin embargo para el caso (2,1) tenemos que la regla 45 muestra grados de reversibilidad para configuraciones de tamaño impar, mientras que la regla 105 muestra grados de reversibilidad para configuraciones que no sean múltiplos de tres.

Para el caso la única regla que presenta grados de reversibilidad es la regla 1313, para configuraciones de tamaño impar. Como habíamos señalado en la Sección 4.3.3 el cálculo se va complicando conforme k, r y l, se van incrementando.

Finalmente presentamos una lista de reglas para el caso que muestran grados de reversibilidad para ciertos valores de l. Esta lista fue revisada manualmente y ordenada de acuerdo a su cluster mínimo correspondiente por cada una de las reglas. Para comprobar esta lista se anexó un apéndice que ilustra todos los árboles topológicos que muestran sus respectivos grados de reversibilidad para todas las reglas que cumplen con estas condiciones.

 
Tabla 5.1: Reglas con grados de reversibilidad.

En total existen 685 reglas suryectivas de las cuales 22 reglas tienen grados de reversibilidad para valores de l igual a dos, tres, cuatro y cinco. El cálculo se efectuó hasta un valor de l=6 por eso el valor de l no va más alla de cinco.

Evidentemente estos cálculos sugieren un método computacional para todos los demás casos , , , , , , , , , , , , , , , , , , , , , , y .

El estudio sobre los autómatas celulares lineales reversibles ha sido muy importante en los últimos tiempos dado por las contribuciones de Hillman, Nasu, Moore, Hedlund, Tommaso Toffoli, Norman Margolus, McIntosh, Fredkin, Jarkko Kari, S. Amoroso, Y. N. Patt, Erica Jen, por mencionar algunos. Todos estos estudios han ido formando una mejor idea para explicar el surgimiento y comportamiento de tal fenómeno. Buscando una formalización matemática por demás general, aunque esta todavía esta por verse.

Los grados de reversibilidad son un derivado de los autómatas celulares reversibles, su estudio es importante por el hecho de que podemos clasificar un autómata reversible aunque este no lo sea. Es importante determiniar con detalle estas relaciones y determinar con claridad sus respectivas características.

A los autómatas celulares reversibles se les han encontrado aplicaciones tales como la simulación de reacciones químicas, procesos biológicos, simulación de epidemias, simulación de incendios forestales, simulación de procesos matemáticos, simulación de cómputo en paralelo, simulación del control de tráfico y encriptación de datos.

Siendo un poco aventurado la aplicación de encriptación de datos puede ser enfocada a los autómatas que presentan grados de reversibilidad, dificultando aún más la descriptación de tal información ya que ahora intervendría un factor más y este factor es l. Esto significa que podriamos trabajar con varias configuraciones de varias l's dificultando el proceso para descifrar tal configuración inicial.

No cabe duda que la teoría de autómata celular aún tiene varios problemas por resolver, sin embargo es una teoría que se presta al uso de otras herramietas tales como la estadística, la probabilidad, el cáculo diferencial e integral, ecuaciones diferenciales, teoría de gráficas, metodos númericos, estructuras algebraicas, geometría proyectiva, algebra booleana, algebra lineal, teoría de conjuntos, expresiones regulares, procesos estocásticos, simulación y ciencias de la computación. Como habíamos señalado desde la Capítulo 1 es una teoría múltidiciplinaria.

Finalmente señalamos que la teoría de autómata celular tiene un amplio campo de estudio y consecuentemente un amplio campo de futuras aplicaciones. Por lo que se siguen obteniendo nuevos e importantes avances así como nuevas aplicaciones.

 


next up previous 
Next: Árboles Topológicos (4h) Up: Grados de Reversibilidad en Previous: Algoritmo


Genaro Juárez Martínez
E-mail:genaro@sparcomp.cs.cinvestav.mx