Caso de Estudio: Autómata $(4,1/2)$

Para ver en la práctica los conceptos anteriores, tomemos como ejemplo un autómata $(4,1/2)$; es decir, de $4$ estados y un radio de vecindad de $1/2$, entonces tenemos las siguientes características:

Tabla 2.1: Características generales de un autómata $(4,1/2)$

Número de estados:	$k=4$
Radio de vecindad:	$r=1/2$
Tamaño de vecindad:	$2r+1=2$
Número de vecindades distintas:	$k^{2r+1}=16$
Número de reglas de evolución distintas:	$k^{k^{2r+1}}=4294967296$

Escojamos una de estas reglas:

Tabla 2.2: Autómata $(4,1/2)$ con regla de evolución $342917C6$

Vecindades	Evolución	Bloques de $2$ elementos	Valor
		en base $4$	hexadecimal
33	0	$4^1$	3
32	3	$4^0$
31	1	$4^1$	4
30	0	$4^0$
23	0	$4^1$	2
22	2	$4^0$
21	2	$4^1$	9
20	1	$4^0$
13	0	$4^1$	1
12	1	$4^0$
11	1	$4^1$	7
10	3	$4^0$
03	3	$4^1$	C
02	0	$4^0$
01	1	$4^1$	6
00	2	$4^0$

Usando esta agrupación en la regla de evolución, ésta se puede representar por el número hexadecimal $342917C6$; una evolución típica de este autómat es la siguiente:

Figura 2.1: Ejemplo de una evolución del autómata $(4,1/2)$ regla $342917C6$

Las características del diagrama de de Bruijn son las siguientes:

Tabla 2.3: Características del diagrama de de Bruijn en un autómata $(4,1/2)$

Número de nodos:	$k^{2r}=4$
Número de ligas:	$k^{2r+1}=16$

El diagrama de de Bruijn y su representación matricial son las siguientes:

Figura 2.2: Diagrama de de Bruijn y su representación matricial para la regla $342917C6$

Por medio del diagrama de de Bruijn podemos conocer los ancestros de una secuencia dada, por ejemplo, para la secuencia $20$ los ancestros son los siguientes:

Figura 2.3: Ancestros de la cadena $20$ en el diagrama de de Bruijn

El diagrama de parejas tiene $k^{4r}=16$ nodos posibles, la gráfica es la siguiente:

Figura 2.4: Diagrama de parejas del autómata $(4,1/2)$ regla $342917C6$

Podemos editar este diagrama de tal modo que observemos los ciclos que este contenga además del de su diagonal principal, que como se dijo anteriormente es el mismo diagrama de de Bruijn; para la cadena $30$ tenemos dos distintos ancestros, la secuencia $323$ y la secuencia $030$, dada la forma de estas secuencias, la cadena formada por la repetición indefinida de la secuencia $30$ tendrá siempre dos posibles ancestros, uno formado por la repetición indefinida de $323$ y otro con la misma forma usando la secuencia $030$.

Figura: Ancestros de la secuencia $03 \ldots 03$

El diagrama de subconjuntos tendrá tantos nodos como $2^{k^{2r}}=16$, que son todos los posibles subconjuntos que se pueden formar con los nodos del diagrama de de Bruijn, McIntosh [McIntosh 91a] codifica los distintos subconjuntos ordenando los nodos de de Bruijn, y formando un número binario colocando un uno si el nodo aparece en el subconjunto, de este modo cada subconjunto recibe un valor binario distinto, la clasificación de subconjuntos queda de la siguiente manera:

Tabla: Clasificación de los subconjuntos de nodos del diagrama de de Bruijn del autómata $(4,1/2)$

	Nodos de
Subconjunto	de Bruijn				Clasificación
	presentes				binario
	$0$	$1$	$2$	$3$
$\emptyset$	0	0	0	0	0
0	1	0	0	0	1
1	0	1	0	0	2
2	0	0	1	0	4
3	0	0	0	1	8
01	1	1	0	0	3
02	1	0	1	0	5
03	1	0	0	1	9
12	0	1	1	0	6
13	0	1	0	1	10
23	0	0	1	1	12
012	1	1	1	0	7
013	1	1	0	1	11
023	1	0	1	1	13
123	0	1	1	1	14
0123	1	1	1	1	15

El diagrama de subconjuntos asociado a este autómata es el siguiente:

Figura 2.6: Diagrama de subconjuntos del autómata $(4,1/2)$ regla $342917C6$

Si editamos este diagrama se puede observar que existe un camino formado por la secuencia $3333$ que va del conjunto total al conjunto vacío, por lo que esta secuencia pertenece al jardín del edén de dicho autómata, como podemos observar si editamos el diagrama de de Bruijn y solo dibujamos los ancestros del estado $3$.

Figura 2.7: Laconfiguración $3333$ pertenece al jardín del Edén

Se observa en la Figura 2.7 que la secuencia más larga que se puede formar utilizando unicamente al estado $3$ es de tamaño tres, por lo que tratar de generar un secuencia de tamaño mayor o igual a cuatro resulta imposible en la evolución como indica el diagrama de subconjuntos.