Detección de estructuras periódicas

El diagrama de de Bruijn básico define los ancestros de una secuencia para una generación, sin embargo, podemos extender este proceso para un número $t$ de generaciones, donde $t \in \mathbb{N}$. Para esto se tomará un mayor número de elementos para formar cada nodo del diagrama, en el caso $(2,1)$ en una generación cada vecindad consta de 3 elementos, para calcular la evolución en dos generaciones se tienen 5 elementos en cada vecindad, en general para cada generación serán necesarias vecindades de $(2rt+1)$ células.

Una forma de obtener estas estructuras periódicas a las que Cook denomina como gliders, es detectando los ciclos que existen en el diagrama de de Bruijn. La característica principal de estos gliders es que se desplazan en el espacio de evoluciones en un periódo dado, con dirección negativa (a la izquierda), positiva (a la derecha) o neutral.

Encontrar dichos gliders con el diagrama de de Bruijn consiste en analizar los ciclos que pueden formarse dentro del diagrama lo que indica la presencia de estructuras periódicas, si la secuencia que forman los nodos del ciclo se repite (no necesariamente en el mismo orden) después de $t$ generaciones, entonces podemos conocer tanto la periodicidad como el desplazamiento del glider. Este proceso aprovecha que el diagrama de de Bruijn contiene toda la información de la evolución del autómata.

Existen tres tipos de comportamientos asociado a estos ciclos:

I.

Ciclos aislados. Los ciclos aislados cubren todo el plano con un solo tipo de estructura, un ejemplo de este tipo lo podemos observar en la Figura 5, esta formación se denomina ether en fase alfa [Mc99].

Figura 5: Ciclo aislado

II.

Ciclos conectados en una dirección. El espacio de evoluciones es cubierto por estructuras donde cada una ocupa un espacio independiente de las otras, lo que en el juego de la vida se conoce como fusibles como se ilustra en la Figura 6.

Figura 6: Ciclo fusible

III.

Ciclos conectados en ambas direcciones. El espacio de evoluciones es cubierto por estructuras que se alternan, esta situación es la que se presenta en los gliders interactuando con el ether como se puede observar en la Figura 7.

Figura 7: Ciclo conectado en ambas direcciones

Al extender el diagrama de de Bruijn para determinar el desplazamiento de las células en más generaciones, produce diagramas más grandes y complicados de calcular, por ejemplo en la Tabla 1 se calculan las vecindades de tamaño cinco y su evolución en dos generaciones.

En la Tabla 1 las vecindades parciales bajo el traslape `$\diamond$' forman secuencias de tamaño impar; aplicando la regla 110 sin tomar en cuenta la propiedad a la frontera, se generan vecindades de tamaño $2r+1$. Se aplica nuevamente la regla en estas vecindades y se obtienen los estados en los cuales las vecindades de tamaño cinco evolucionan en dos pasos.

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 más 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.

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

Vecindades de tamaño cinco para la 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

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. Un mayor detalle de este tipo de estudio se puede ver en [Mc99] y [Jua00].

El interés sobre la regla 110 surge a partir de los estudios realizados por Cook, uno de estos temas es la realización de ciertas operaciones lógicas en el espacio de evoluciones a través de la interacción de las estructuras periódicas.