Ancestro y Jardín del Edén

Dos importantes conceptos que se tienen dentro de la teoría de autómatas celulares son los de ancestro y jardín del edén, los cuales nos servirán para analizar las características y limitaciones de la evolución de un autómata celular.

Tomemos a $K^*$ como el conjunto de todas las secuencias de cualquier longitud, desde longitud $0$ en adelante; a la secuencia de longitud $0$ o cadena vacía se denominará como $\lambda$.

Para $(i,j) \in \mathbb{Z}^+$, una secuencia de estados $s_i \in K^*$ se dice que es ancestro de otra secuencia $s_j \in K^*$ si al aplicar la regla de evolución $\phi$ a cada uno de sus elementos de $s_i$, la nueva cadena resultante es igual a $s_j$. Este concepto se puede aplicar para cualquier secuencia de estados, abarcando desde vecindades hasta la configuración completa; de este modo la configuración $C_i$ es ancestro de la configuración $C_j$ si $C_i$ evoluciona a $C_j$ bajo la aplicación de la regla de evolución $\phi$.

Por supuesto, con esta misma idea podemos tener distintos casos, pueden existir una secuencia de estados $s_i \in K^*$ que carezca de ancestros, que tenga un único ancestro o que tenga más de un posible ancestro. A las secuencias que caigan en el primer caso se les denomina como pertenecientes al jardín del edén de dicho autómata, esta forma tan particular de describir este caso se debe a que dichas secuencias solo pueden aparecer en la configuración inicial y no pueden presentarse como producto de la evolución del autómata, sino solamente al inicio de dicho proceso.