Next: Algoritmo Up: Aut�matas celulares con Previous: Aut�mata (4h) regla
Next: Algoritmo Up: Aut�matas celulares con Previous: Aut�mata (4h) regla
El aut�mata celular 
regla 016ED4BB presenta grados de reversibilidad para configuraciones que no sean
m�ltiplos de tres. En primer instancia obtengamos los productos matriciales por estado
para determinar si alguno de los cuatro estados determina la reversibilidad para este
aut�mata.
Primeramente construyamos sus matrices de conectividad.
Todas las matrices cumplen con la condici�n de que su traza es igual a uno, lo que significa que las configuraciones de tama�o uno tienen un �nico ancestro. Ahora analizaremos cada uno de los estados y sus respectivas potencias.
Las matriz 
elevada a
una n-�sima potencia es idempotente para toda 
, por lo que para toda cadena formada por el
estado 00*, esta cadena va a tener un �nico ancestro.
La matriz de conectividad 
alcanza la idempotencia cuando 
, y conserva la 
para cualquer potencia de 
.
Para el estado 2 su matriz de conectividad alcanza r�pidamente la idempotencia cuando n=2. Mostrando un �nico ancestro para configuraciones 22*.
La matriz 
alcanza la
idempotencia cuando 
igual
que el estado 1 y la 
lo
que confirma un �nico ancestro para toda configuraci�n formada por la cadena 33*.
Todo parece indicar que el aut�mata celular es reversible para todas las configuraciones de tama�o par e impar. Sin embargo si an�lizamos su diagrama de parejas veremos que no es reversible.
Figura 4.10: Diagrama de parejas de la regla 016ED4BB.
La Figura 4.10 ilustra la existencia de ciclos fuera de la diagonal, lo que implica que
este aut�mata celular no es reversible. La explicaci�n de este f�nomeno es que los
ciclos se forman por cadenas que estan formadas por combinaciones de los mismos estados.
Si efectuamos todas las combinaciones posibles cuando l=2, entonces tenemos
dieciseis casos posibles donde la 
.
Figura 4.11: �rboles topol�gicos con l=2.
La Figura 4.11 ilustra todas las configuraciones 
donde el mapeo global es biyectivo y l�gicamente
t�mbien es reversible para este valor. Por que s�lo existe una configuraci�n que
construye a otra configuraci�n para todos los estados globales que podemos formar con l=2.
Los ciclos 5 y 10 son de longitud uno, esto quiere decir que la evoluci�n para este caso
va a ser siempre 5 � 10 en todo el diagrama de evoluciones.
Ahora analizemos la secuencia formada por los estados 123 donde sus productos matriciales los representamos de la siguiente manera:
podemos ver que la 
lo
que implica que la configuraci�n tiene dos ciclos que a su vez indican dos ancestros para
dicha cadena. Estas cadenas estan formadas por los bloques de evoluci�n 1221 y 3013, sus
ancestros de la cadena 123 son los estados 221 y 013 respectivamente.
Figura 4.12: Diagrama de transiciones con l=3.
La Figura 4.12 ilustra uno de los �rboles topol�gicos cuando l=3 y podemos verificar que la cadena 123 representada por el estado global 27 tiene dos ancestros, los estados globales 41 y 7 representadas por las cadenas 221 y 013 respectivamente.
Por lo que deducimos que para determinar los grados de reversibilidad de un ancho
espec�fico tenemos que efectuar todas las combinaciones posibles determinadas por k.
Y el orden de n determinar� el tama�o de l para toda configuraci�n 
.
Comprobando los grados de reversibilidad para este aut�mata revisemos la secuencia 102303 que debe de tener m�s de un ancestro, ya que l es un m�ltiplo de tres en este caso.
La matriz de conectividad para la cadena representada por los estados 102303 presenta
una 
lo que implica que
dicha configuraci�n posee dos ancestros y no es reversible cuando l=6.
Next: Algoritmo Up: Aut�matas celulares con Previous: Aut�mata (4h) regla