Diagramas de de Bruijn en la $regla$ $110$

Las características en las estructuras de Life son sencillas y muy complejas a la vez, éstas son alcanzadas desde casi cualquier configuración aleatoria. Ahora bien Life es una regla semitotalística y la regla 110 no es una regla totalística ni semitotalística, lo que implica que sus posibles proyecciones en autómatas celulares de dos y tres dimensiones tengan que realizarse definiendo cada una de las vecindades que se derivan con la vecindad de von Neumann y la vecindad de Moore. Cook presenta ocho tipos de gliders y un glider gun en [14], no describe sus métodos o las herramientas que emplea para construir dichos gliders, sin embargo logramos reproducir estos gliders empleando teoría de gráficas con los diagramas de de Bruijn [45], tal como lo describe McIntosh en [46].

Se emplean diagramas de de Bruijn [45] para determinar la tranformación local en cada una de las vecindades de la regla de evolución, McIntosh reporta estas relaciones en [46] describiendo la importancia de emplear estas herramientas que proporcionan la información rápidamente, estos diagramas se ajustan muy bien a las reglas de los autómatas celulares en una dimensión aunque originalmente fueron empleados para el estudio de la teoría de registro de corrimientos. La teoría de registro de corrimientos es una disciplina basada en el tratamiento de secuencias traslapando.

Figura 5.1: Evolución típica de la regla 110

En el espacio de evoluciones de la Figura 5.1 se puede ver la existencia de estructuras periódicas que se desplazan a través de un fondo periódico llamado ether Figura 5.4, donde estas estructuras periódicas son los gliders que se desplazan sin sufrir cambios en sus estructuras por el ether y a su vez el ether tampoco se destruye por los desplazamientos de los gliders. La complejidad de la regla 110 se produce cuando los gliders coalisionan entre ellos, originando otros gliders. Estas coalisiones son muy variadas pues la estructura que se genera depende de que gliders son los que coalisionan, que desplazamiento tienen los gliders, a que altura coalisionan, entre otras cosas.

Los vértices del diagrama de de Bruijn son secuencias de símbolos de algún alfabeto, estos símbolos pueden ser secuencias de vértices de una gráfica en específico. Las aristas del diagrama describen como tales secuencias pueden traslapar, por lo tanto diferentes grados de traslape producen diagramas diferentes, el traslape se produce entre un símbolo inicial, los símbolos que traslapan y un símbolo terminal.

Por ejemplo la secuencia binaria $0011$ traslapa con la secuencia $0110$ tomando el 0 de la primera secuencia como el símbolo inicial, 011 como los elementos que traslapan entre la primera y segunda secuencia, el útimo 0 de la segunda secuencia como el símbolo terminal, las aristas pueden ser etiquetadas de acuerdo a la nueva secuencia que se produce que es 00110 y producir una variedad de caminos.

Cuando los símbolos son enteros consecutivos pueden ser tratados como elementos de un anillo o quiza un campo finito.

La matriz de incidencia del diagrama de de Bruijn es:

$$M_{i,j} = \left\{\begin{array}{lllll} 1&si&j&=& \left\{\begin{arr... ...ki+k-1 \end{array} \right. \ \ 0& \mbox{en otro caso} \ \end{array} \right.$$ (5.2.1)

donde $k$ y $r$ deteminan el orden del autómata celular. Sea un autómata celular de orden $(k=2,r=1)$. La matriz de incidencia para el diagrama de de Bruijn de la Figura 5.2 queda como:

$$M_{i,j} = \left [\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{array} \right ].$$

Esta matriz se obtuvo empleando la Ecuación 5.2.1. Si $i=0$ entonces $j=ki=2*0=0$ y $j=(2*0)+1=1$ por lo tanto $M_{0,0}=1$ y $M_{0,1}=1$. Si $i=1$ entonces $j=ki=2*1=2$ y $j=(2*1)+1=3$ por lo tanto $M_{1,2}=1$ y $M_{1,3}=1$. Si $i=2$ entonces $j=ki=2*2=4$ y $j=(2*2)+1=5$, 4 módulo 4 es 0 y 5 en módulo 4 es 1, por lo tanto $M_{2,0}=1$ y $M_{2,1}=1$. Si $i=3$ entonces $j=ki=2*3=6$ y $j=(2*3)+1=7$, 6 módulo 4 es 2 y 7 en módulo 4 es 3, por lo tanto $M_{3,2}=1$ y $M_{3,3}=1$, en todos los demas casos $M_{i,j}=0$. Finalmente se ve que la Ecuación 5.2.1 representa una gráfica de de Bruijn para cualquier autómata celular de orden $(k,r)$.

En la Figura 5.2 se muestra el diagrama de de Bruijn genérico para los autómatas celulares de orden $(k=2,r=1)$.

Figura 5.2: Diagrama de de Bruijn genérico $(2,1)$

El modulo $k^{2r}=2^{2}=4$ es el número de vértices en el diagrama de de Bruijn, $j$ tomará valores de $k*i=2i$ hasta $(k*i)+k-1=(2*i)+2-1=2i-1$. Los vértices tienen fracciones de vecindad originada por las secuencias 00, 01, 10 y 11. El traslape define cada una de las aristas como:

Tabla 5.2: Traslapes en el diagrama de de Bruijn genérico (2,1)

Formando vecindades
(0,0) $\diamond$ (0,0)	000
(0,0) $\diamond$ (0,1)	001
(0,1) $\diamond$ (1,0)	010
(0,1) $\diamond$ (1,1)	011
(1,0) $\diamond$ (0,0)	100
(1,0) $\diamond$ (0,1)	101
(1,1) $\diamond$ (1,0)	110
(1,1) $\diamond$ (1,1)	111

En la Tabla 5.2 se muestran los traslapes que se derivan de los elementos de cada vértice, estos traslapes son las aristas del diagrama de de Bruijn genérico para los autómatas celulares de orden $(2,1)$ de la Figura 5.2.

El diagrama de de Bruijn genérico para un autómata $(2,1)$ tiene cuatro vértices $\{0,1,2,3\}$ que corresponden a cuatro vecindades parciales de dos células $\{00,01,10,11\}$, con ocho aristas representando sus vecindades de tamaño $2r+1$ Tabla 5.1, entonces el número de vértices en el diagrama de de Bruijn está determinado por $k^{2r}$ y el número de aristas es igual a $k^{2r+1}$.

El diagrama de de Bruijn para la regla 110 se deriva del diagrama de de Bruijn genérico de la Figura 5.2, el diagrama de de Bruijn genérico puede ser diferenciado con respecto a una regla de evolución en particular. En la Figura 5.3 se puede ver como cada arista representa el estado al que va a evolucionar la vecindad, el estado 1 está de color negro y el estado 0 está de color gris, éste es el diagrama de de Bruin para la regla 110.

Figura 5.3: Diagrama de de Bruijn para la regla 110

Los diagramas de de Bruijn se emplean para describir como se pueden reproducir de manera mas sencilla y práctica los resultados presentados por Cook en [14], cabe señalar que estas técnicas no han sido reportadas por otros autores, McIntosh describe su método en [46].

El diagrama de de Bruijn puede ser extendido para formar vecindades mas grandes y determinar el desplazamiento de las células en $t$ generaciones, ésto origina diagramas de de Bruijn mas grandes y complicados de calcular, por ejemplo calculemos las vecindades de tamaño cinco.

Tabla 5.3: Extensión de vecindades en el diagrama de de Bruijn con la regla 110

Vecindades de tamaño cinco aplicando regla 110
traslape	vecindad generación 0	generación 1	generación 2
$(0,0,0,0) \diamond (0,0,0,0)$	$00000$	$000$	0
$(0,0,0,0) \diamond (0,0,0,1)$	$00001$	$001$	$1$
$(0,0,0,1) \diamond (0,0,1,0)$	$00010$	$011$	$1$
$(0,0,0,1) \diamond (0,0,1,1)$	$00011$	$011$	$1$
$(0,0,1,0) \diamond (0,1,0,0)$	$00100$	$110$	$1$
$(0,0,1,0) \diamond (0,1,0,1)$	$00101$	$111$	0
$(0,0,1,1) \diamond (0,1,1,0)$	$00110$	$111$	0
$(0,0,1,1) \diamond (0,1,1,1)$	$00111$	$110$	$1$
$(0,1,0,0) \diamond (1,0,0,0)$	$01000$	$100$	0
$(0,1,0,0) \diamond (1,0,0,1)$	$01001$	$101$	$1$
$(0,1,0,1) \diamond (1,0,1,0)$	$01010$	$111$	0
$(0,1,0,1) \diamond (1,0,1,1)$	$01011$	$111$	0
$(0,1,1,0) \diamond (1,1,0,0)$	$01100$	$110$	$1$
$(0,1,1,0) \diamond (1,1,0,1)$	$01101$	$111$	0
$(0,1,1,1) \diamond (1,1,1,0)$	$01110$	$101$	$1$
$(0,1,1,1) \diamond (1,1,1,1)$	$01111$	$100$	0
$(1,0,0,0) \diamond (0,0,0,0)$	$10000$	$000$	0
$(1,0,0,0) \diamond (0,0,0,1)$	$10001$	$001$	$1$
$(1,0,0,1) \diamond (0,0,1,0)$	$10010$	$011$	$1$
$(1,0,0,1) \diamond (0,0,1,1)$	$10011$	$011$	$1$
$(1,0,1,0) \diamond (0,1,0,0)$	$10100$	$110$	$1$
$(1,0,1,0) \diamond (0,1,0,1)$	$10101$	$111$	0
$(1,0,1,1) \diamond (0,1,1,0)$	$10110$	$111$	0
$(1,0,1,1) \diamond (0,1,1,1)$	$10111$	$110$	$1$
$(1,1,0,0) \diamond (1,0,0,0)$	$11000$	$100$	0
$(1,1,0,0) \diamond (1,0,0,1)$	$11001$	$101$	$1$
$(1,1,0,1) \diamond (1,0,1,0)$	$11010$	$111$	0
$(1,1,0,1) \diamond (1,0,1,1)$	$11011$	$111$	0
$(1,1,1,0) \diamond (1,1,0,0)$	$11100$	$010$	$1$
$(1,1,1,0) \diamond (1,1,0,1)$	$11101$	$011$	$1$
$(1,1,1,1) \diamond (1,1,1,0)$	$11110$	$001$	$1$
$(1,1,1,1) \diamond (1,1,1,1)$	$11111$	$000$	0

En la Tabla 5.3 se necesita que las vecindades parciales bajo la operación traslape `$\diamond$' formen una vecindad de tamaño par, despues se aplica la regla 110 de la Tabla 5.1 sin tomar en cuenta la propiedad a la frontera, ésto produce una vecindad de tamaño $2r+1$ en la generación 1, se aplica nuevamente la regla de volución en esta vecindad y se obtiene el estado al que va a evolucionar la vecindad de tamaño cinco.

Por ejemplo la secuencia 0110 traslapa con la secuencia 1101 para formar la vecindad 01101, al aplicar la regla 110 se tiene que 01101 genera la secuencia 111 que es una vecindad mas pequeña, si se vuelve aplicar la regla de evolución a la secuencia 111 se tiene el estado 0, entonces la vecindad 01101 evoluciona a 0 en dos generaciones.

Las fracciones de vecindad compuestas por 4 células derivan 16 vértices para el diagrama de de Bruijn de este orden y 32 aristas que son las vecindades, despues se calcula la célula de evolución que le corresponde a cada vecindad de ese tamaño. Este método es el que se emplea para generar diagramas de de Bruijn extendidos, que van a determinar como se puede construir una estructura que la regla 110 produsca en particular.

McIntosh hace notar que el problema de la regla 110 es un problema de cubrir el espacio con triángulos, aunque Cook no aplica este enfoque ya que su análisis lo presenta con configuraciones muy grandes, con la unión de varias configuraciones $c_{i}$ de diferentes tamaños en diferentes ciclos de longitud variada; si uno desea hacer a mano tales procesos es una labor muy difícil de finalizar.

Figura 5.4: Ether en la regla 110

En la Figura 5.4 se determina el fondo no periódico con configuraciones de tamaño seis, por ejemplo el vértice 5 (000101) traslapa con el vértice 11 (001011) formando la vecindad 11 (0001011), que evoluciona al estado 1 aplicandole la regla 110 como se describe en la Tabla 5.3, nótese que hay $k^{2(3)+1}=128$ vecindades de tamaño seis. El corrimiento de los estados de estas estructuras es de un desplazamiento de dos células a la derecha en tres generaciones.

La manera en que se van a identificar las estructuras es siguiendo las secuencias de los estados que tienen las aristas, porque las aristas van a estar representadas por un color, este color es el estado al que evoluciona una vecindad dada, entonces se forma una secuencia de estados simplemente tomando el estado que tiene cada arista hasta cerrar un ciclo y ver que la secuencia resultante produce una estructura en particular.

En la Tabla 5.4 se toma la secuencia de estados 1000101 que produce el ciclo de la izquierda en la Figura 5.4, esta secuencia de estados debe producir el ether si se llena la configuración inicial con esta secuencia de estados, entonces en el espacio de evoluciones se tendrá puro ether. Por otra parte el diagrama de de Bruijn indica que esta secuencia o cualquier permutación de ella, debe desplazarse 3 células a la derecha en 2 generaciones.

Tabla 5.4: Secuencia $1000101$ que produce puro ether

Configuración ether
generación	binario
0	1000101 $\dagger$
1	1001111
2	1011000 $\dagger$
3	1111001
4	0001011 $\dagger$
5	0011111
6	0110001 $\dagger$
7	1110011
8	0010110 $\dagger$
9	0111110
10	1100010 $\dagger$
11	1100111
12	0101100 $\dagger$
13	1111100
14	1000101 $\dagger$
15	1001111

En la Tabla 5.4 la configuración 1000101 muestra como todas sus células se mueven al mismo tiempo tres posiciones a la derecha en dos generaciones marcadas con $\dagger$, la configuración 1001111 también sufre este cambio de desplazar todas sus células tres posiciones a la derecha en dos generaciones. Finalmente permutaciones de la cadena 1000101 puede reproducir la estructura ether.