$Gliders$ en la $regla$ $110$

Cook muestra ocho tipos de gliders y un glider gun, estos resultados fueron descritos en [14] pero dado algunos problemas legales, no sean reportado con detalle como se obtuvieron estos resultados. La característica importante en esta regla de evolución es que puede llegar hacer computación, Cook ha analizado a fondo esta regla y menciona que dicha regla puede realizar computación universal.

La finalidad de estudiar esta regla de evolución no es determinar si la regla 110 puede o no puede hacer computación universal, mas bien establecer sus relaciones con Life aunque se sabe que Life puede realizar computación como se demostro en [10].

El uso de los diagramas de de Bruijn extendidos no han sido reportados para la reproducción de gliders o cualquier otras estructuras que existan en el espacio de evoluciones de la regla 110, Cook presentó varias configuraciones para que fueran analizadas por otros investigadores en el grupo de discución LifeCA, la condición inicial: 00010011011111$\{$15922-14$\}$110$\{$396-402$\}$1$\{$342-346$\}\{$653-1108$\}\{$343-996$\}$^5.1 establecida por Cook es difícil de analizar. Por ejemplo la parte $110\{396-402\}$ indica que la cadena 110 debe asignarse a la configuración despues se asignarán 396 células, a las que se le asignarán las últimas 402 células de la configuración inicial.

Se puede apreciar que es un trabajo muy laborioso y que requiere una buena cantidad de tiempo para su estudio. Empleando los diagramas de de Brujin se reproducen algunos de los gliders mostrados y clasificados por Cook en [14], los diagramas de de Bruijn extendidos que se muestran a continuación omitien todos los detalles mostrados en la Sección 4.2.

Glider A

En la Figura 5.5 se puede ver que una estructura de este tipo puede ser calculada con el diagrama de de Bruijn en 3 generaciones y con un desplazamiento de 4 células a la izquierda, tomando la secuencia de uno de los ciclos sabemos que el glider A puede ser reproducido por la secuencia de estados 000111, si se toma el ciclo definido por las vecindades parciales $28 \rightarrow 56 \rightarrow 113 \rightarrow 227 \rightarrow 199 \rightarrow 142 \rightarrow 28$, las células de evolución que representarán sus vecindades definen la secuencia 000111.

Nótese que cada uno de estos ciclos de longitud seis definen un glider A, aunque las secuencias sean diferentes, por ejemplo tenemos que las secuencias de estados 111110 y 001101 también definen la construcción de gliders A en el espacio de evoluciones.

Figura 5.5: Glider A

Es importante resaltar el hecho que la construcción de un glider sigue una permutación de estados con respecto a una secuencia dada, aquí se puede ver un problema menor muy interesante en los diagramas de de Bruijn extendidos.

Tratar de establecer una clasificación de acuerdo al tipo de secuencias que pueden generar un glider en particular, dado que existen varias combinaciones de estados que pueden producir una estructura en particular y sabiendo que hay varias configuraciones que producen una estructura dada, ver cual sería la diferencia entre utilizar una u otra configuración para obtener un resultado en el espacio de evoluciones con otras estructuras.

Glider B

El glider B de la Figura 5.6 se desplaza de manera inversa al glider A y se pueden reproducir varios de ellos con el diagrama de de Bruijn en 5 generaciones con un desplazamiento de 10 células a la derecha.

Figura 5.6: Diagrama de de Bruijn para obtener gliders B

El ciclo que se genera en este diagrama de de Bruijn es extenso, lo que implica un proceso mas grande que realizar para obtener dicho diagrama, tal ciclo se ilustra con la etiqueta de ``gliders B'' en la Figura 5.6. La Figura 5.7 ilustra varios gliders B.

Figura 5.7: Gliders B

En la Figura 5.8 se ilustran algunos gliders dados a conocer por Cook en [14].

Figura 5.8: Algunos gliders de la regla 110

Los gliders de la Figura 5.8 tienen un tamaño fijo y un periódo de desplazamiento a través del tiempo, por eso son estructuras periódicas con desplazamientos. Nótese que las estructuras son de diferentes tamaños, algunas son grandes como el glider gun que está constituido de 20 células con un desplazamiento en 77 generaciones, ésto implicaría que el diagrama de de Bruijn asociado al glider gun debe ser enorme.

Otra característica muy importate son los choques que se pueden producir con estos gliders y originar comportamientos complejos, este hecho provocó que se llegara a la conjetura de que la regla 110 puede realizar computación universal siguiendo la lógica que se empleó con la regla de Life, analizando sus choques entre gliders como lo demostró Conway en [10] donde Life puede hacer computación universal con estos choques. Life y la regla 110 tienen la característica de que si se quiere llegar a reproducir por ejemplo un contador binario a través del espacio de evoluciones, no es común obtenerlo con configuraciones aleatorias, es decir, hay que construirlo con cuidado en la configuración inicial para contruir dicho contador binario. En [34] se muestra la construcción de un contador binario con la regla 110 emplando tres gliders, el glider $E_{n}$ se incrementará en uno $E_{n+1}$ si choca con un glider B y se decrementará en uno $E_{n-1}$ si choca con un glider A.

Algunos gliders mas grandes son difíciles de obtener con los diagramas de de Bruijn, los diagramas aunque pueden ser calculados implican una labor de ordenamiento con paciencia, como se muestra en la Figura 5.9.

Figura 5.9: Diagrama de de Bruijn extendido en 10 generaciones

En la Figura 5.9 se muestra el diagrama de de Bruijn en 10 generaciones con un desplazamiento de 10 células a la izquierda, se selecciono el nodo 211150 del diagrama de de Bruijn y se puede ver que en el espacio de evoluciones se generan varios gliders con el ether. Aunque también puede llenarse el fondo con un solo glider y meter una línea de puro ether, es decir, el ether sería como un glider y el glider como el ether.