Next: Algunos algoritmos existentes Up: Grados de Reversibilidad Previous: Grados de Reversibilidad

Aut�matas celulares reversibles

El estudio sobre aut�matas celulares reversibles no ha sido resuelto en su totalidad hasta nuestros d�as para todos los casos posibles, sin embargo se han logrado avances muy importantes que nos han permitido comprender de una manera m�s clara la explicaci�n de este comportamiento. Mencionaremos de manera general las caracter�sticas m�s importantes para identificar aut�matas celulares reversibles.

Los aut�matas celulares reversibles se caracterizan por tener un mapeo inyectivo y a la vez suryectivo, es decir tienen un mapeo biyectivo, carecen de configuraciones pertenecientes al Jard�n del Ed�n y tampoco tienen m�ltiples ancestros. Esto significa que los �rboles topol�gicos estan constituidos s�lo de puras ra�ces c�clicas, no existen ramas ni hojas. Trabajaremos con un aut�mata para tener una idea m�s clara de estos conceptos.

El aut�mata celular de la Figura 4.1 ilustra algunas condiciones b�sicas para detectar si el aut�mata es reversible o no. Mencionaremos s�lo algunas pues este estudio se ha desarrollado detalladamente en [21].

Una primera condici�n es que los estados deben existir en igual n�mero en el diagrama de de Bruijn, esto es, debe de cumplir el teorema de M�ltiplicidad Uniforme [2] [16] [11] que nos dice; si tenemos un estado con un n�mero de ancestros igual al n�mero de nodos del diagrama de de Bruijn, entonces para toda concatenaci�n que realizemos por la izquierda o por la derecha el n�mero de ancestros debe ser el mismo.

 
Figura: Aut�mata reversible regla F5A0F5A0.

La segunda implica que en el diagrama de subconjuntos no deben existir cadenas que vayan del conjunto m�ximo al conjunto m�nimo y adem�s que no existan secuencias de estados que formen ciclos dentro de las mismas clases unitarias, ya que las secuencias deben estacionarse en una clase unitaria del diagrama sin pasar a otra clase unitaria, es decir, estacionarse en un s�lo nivel o en su defecto llegar de un s�lo paso al conjunto m�ximo o al conjunto m�nimo. Esta propiedad va asociada a la primera condici�n ya que si el aut�mata cumple con el teorema de m�ltiplicidad uniforme, tambi�n debe cumplir con el teorema de los �ndices de Welch [2] [16] [11] que nos dice; si todas las secuencias posibles que se encuentran dentro de las clases unitarias que describen los mismos �ndices de Welch ya sea por la izquierda o por la derecha, forman cadenas de longitud mayor igual que uno y menor igual al n�mero de nodos del diagrama de de Bruijn, esto nos indica que debe existir un �nico ancestro.

La tercera propiedad es analizar el diagrama de parejas que nos ayuda a verificar la nula existencia de ciclos fuera de la diagonal principal, es decir no existen m�ltiples ancestros. Los ciclos que existen dentro de la diagonal principal se debe por que los nodos de la diagonal principal no son m�s que los mismos nodos del diagrama de de Bruijn.

Regresando a la Figura 4.1 podemos identificar estas propiedades mencionadas en el p�rrafo anterior, las matrices de conectividad derivadas del diagrama de de Bruijn por estado, contienen el mismo n�mero de elementos por cada uno de los estados posibles, lo que implica que en el diagrama de de Bruijn deben existir igual n�mero de aristas por cada uno de los estados. El diagrama de subconjuntos muestra todas las posibles secuencias originadas desde cualquier nodo, es decir con sus cuatro clases unitarias construidas. Si seguimos cualquier secuencia podemos verificar como de la clase unitaria uno sube a la clase unitaria dos o baja al conjunto vacio, la clase unitaria tres s�lo baja a la clase unitaria dos, la clase unitaria cuatro baja a los nodos 12 y 3 de la clase unitaria dos, a estos nodos tambi�n se les conoce como nodos atractores. Por lo que deducimos que la clase unitaria nivel dos es la clase que contiene las propiedades de los �ndices de Welch y cumple con la propiedad de que toda secuencia que exista dentro de esta clase debe de ser mayor igual a uno y menor igual al n�mero de nodos del diagrama de de Bruijn. Finalmente podemos verificar que el aut�mata presenta un mapeo biyectivo y carece de m�ltiples ancestros ya que se a gr�ficado su respectivo diagrama de parejas con la opci�n s�lo ciclos y observamos que no existen ciclos fuera de la diagonal principal con lo que se determina que el aut�mata celular es reversible.

Existen a�n m�s sutilezas por analizar, pero este no es el fin de esta secci�n. Si se desea un mayor an�lisis de estas propiedades se puede consultar la siguiente bibliograf�a [2] [16] [20] [11] [10] [21], donde se desarrolla con gran profundidad y de manera formal la demostraci�n y representaci�n de tales teoremas.

Next: Algunos algoritmos existentes Up: Grados de Reversibilidad Previous: Grados de Reversibilidad