Modelo original The Game of Life

El autómata celular The Game of Life propuesto por Conway, es llamado así por su relación con la modelación de sistemas biológicos, tal como ecosistemas, incendios forestales, reacciones químicas, comportamientos colectivos de seres vivos, entre otros.

Este modelo evoluciona en dos dimensiones con la vecindad de Moore, la regla de evolución es semitotalística y es representada como $R(2,3,3,3)$, recordemos que cuando una célula está viva se representa con el estado 1, si está muerta se representa con el estado 0. Las variables de la Ecuación 1 toman los valores de $S_{min}=2$, $S_{max}=3$, $N_{min}=3$ y $N_{max}=3$.

Conway hace un amplio análisis para poder determinar una regla de evolución que tuviera dos características fundamentales:

1. Una configuración $c_{i}$ no debe desaparacer rápidamente.

2. Una configuración $c_{i}$ debe crecer ilimitadamente.

además se deben de definir tres condiciones, cuándo una célula debe de nacer, sobrevivir o morir. Estas condiciones son muy importantes para obtener las características mencionadas.

Por lo tanto la Equación 1 para la regla $R(2,3,3,3)$ en particular queda como:

$$\varphi({\mathbf{x}_{0}},{\mathbf{x}_{1}},\ldots,{\mathbf{x}_{8}}... ...}} \leq 3 \end{array} \right. \\ \\ 0 & \mbox{en otro caso} \end{array} \right.$$ (6)

tenemos que $3 \leq \sum_{i=1}^{8} \mathbf{x}_{i} \leq 3$ es el intervalo de células vivas que originan un nacimiento de una célula que se encuentra muerta y $2 \leq \sum_{i=1}^{8} \mathbf{x}_{i} \leq 3$ es el intervalo de células vivas que determinan la sobrevivencia de una célula que está viva. Las transformaciones para cada una de las células se efectúan de manera simultánea en el espacio de evoluciones.

El interés que se originó en Life se debe principalmente a los comportamientos complejos que la regla de evolución puede producir, llegando a resultados muy importantes como fue el hecho de demostrar que Life puede realizar computación universal [BCG82].

En el espacio de evoluciones existen cuatro tipos de comportamientos característicos que se pueden obtener desde cualquier configuración aleatoria:

1. Configuraciones que desaparecen.

2. Configuraciones estáticas.

3. Configuraciones periódicas.

4. Configuraciones periódicas con desplazamientos.

Las estructuras periódicas con desplazamientos conocidas como gliders son muy interesantes e importantes en Life. Muchos de los descubrimientos más relevantes están relacionados con este tipo de estructuras, determinando las trayectorias que pueden tener a través del espacio de evoluciones y que comportamientos o estructuras tan complejas se pueden llegar a producir cuando estos gliders colisionan entre sí o con otras estructuras.

El glider más relevante en la literatura de Life es el glider de cinco células ilustrado en la Figura 3, su periódo de desplazamiento es de dos células en cuatro generaciones.

Figura 3: Configuración periódica con desplazamiento llamada glider

El glider de la Figura 3 tiene una población total de cinco células y esta población se conserva en cada generación. Existen otros tipos de gliders que varían de forma, tamaño, periodo y dirección en el espacio de evoluciones, por lo tanto comportamientos de este tipo fueron los que originaron un interés más a fondo para poder explicar el origen y las construcciones de estas estructuras.

Figura 4: Glider gun

El glider gun ilustrado en la Figura 4 es una estructura que produce gliders como el de la Figura 3, de manera contínua cada treinta generaciones. Un descubrimiento muy importante y verdaderamente sorprendente realizado por Gosper, es que treinta gliders como el de la Figura 3 pueden construir su propio glider gun [BCG82], con este resultado se demostro que Life puede crecer ilimitadamente y puede reproducirse a sí mismo.

A continuación construimos el polinomio de la teoría del campo promedio paso a paso para ver con claridad la relación que existe entre las Ecuaciones 3 y 4. El número de combinaciones que se pueden generar en la vecindad de Moore cuando $S_{min}=2$ es igual a 28.

Figura 5: Vecindades que determinan la sobrevivencia cuando $S_{min}=2$

La Figura 5 ilustra las 28 combinaciones que se pueden generar en 8 células cuando $S_{min}=2$, es decir, el número de vecindades cuando la célula central está viva y sus vecinos suman dos células vivas, para que en la siguiente generación la célula central permanezca viva.

Tenemos que $v=3$ y $n-v=9-3=6$ cuando $S_{min}=2$, notemos que las combinaciones se realizan sobre los vecinos $\mathcal V$, donde la célula central $\mathbf{x}_{0}$ es ocupada por el estado 1. En realidad al momento de calcular las combinaciones no importa si $\mathbf{x}_{0}$ es ocupada por el estado 1 o el estado 0, sin embargo $\mathbf{x}_{0}$ es importante al momento de definir los exponentes del polinomio.

Ahora se realiza el cálculo cuando $S_{max}=3$.

Figura 6: Vecindades que determinan la sobrevivencia cuando $S_{max}=3$

En la Figura 6 se ilustran las 56 vecindades que se transforman al estado 1 en la siguiente generación cuando $S_{max}=3$. De esta manera se calcula el número de combinaciones empleando el coeficiente binomial:

$$\left (\begin{array}{c} n-1 \\ v \end{array} \right ) = \frac{(n-1)!}{v!((n-1)-v)!}$$ (7)

donde $n=\mathcal V+1$ y $v=\{0,1,\ldots,n-1\}$. Por ejemplo para el caso de la Figura 5 se tiene que $v=2$ y $n=9$ entonces:

$$\left (\begin{array}{c} 9-1 \\ 2 \end{array} \right ) = \frac{(9-1)!}{2!((9-1)-2)!} = 28$$

este número representa las combinaciones sin repetición que se generan cuando $S_{min}=2$. En el caso de la Figura 6 cuando $S_{max}=3$ tenemos que:

$$\left (\begin{array}{c} 9-1 \\ 3 \end{array} \right ) = \frac{(9-1)!}{3!((9-1)-3)!} = 56.$$

En el caso cuando $N_{min}=3$ y $N_{max}=3$ se tienen 56 combinaciones igual que cuando $S_{max}=3$ y esto se debe porque las combinaciones se realizan en los vecinos $\mathcal V$, es decir, las células de la vecindad sin tomar en cuenta la célula central $\mathbf{x}_{0}$. Por lo tanto las combinaciones de $S_{max}=3$ son iguales a las combinaciones de $N_{min}=3$ y $N_{max}=3$.

El grado del polinomio se determina por el número de células vivas $v$ y por el número de células muertas $n-v$, que existen en los vecinos $\mathcal V$. En el caso cuando $S_{min}=2$ el exponente $v=3$ y $n-v=6$, cuando $S_{max}=3$ el exponente $v=4$ y $n-v=5$, cuando $N_{min}=3$ el exponente $v=3$ y $n-v=6$ y cuando $N_{max}=3$ el exponente $v=4$ y $n-v=5$.

Finalmente el polinomio para la regla de evolución Life queda como:

$$p_{t+1}=28p_{t}^{3}q_{t}^{6}+56p_{t}^{4}q_{t}^{5}+56p_{t}^{3}q_{t}^{6}$$ (8)

simplificando:

$$p_{t+1}=84p_{t}^{3}q_{t}^{6}+56p_{t}^{4}q_{t}^{5}$$ (9)

la probabilidad que genera cuando $S_{max}=3$ es la misma probabilidad cuando $N_{min}=3$, porque el número de 1's en la vecindad es igual en ambos casos, por esa razón se tienen tres términos en el polinomio de la Ecuación 8 en lugar de cuatro como pudiera pensarse.

La curva de probabilidad se obtiene poniendo el polinomio de la Ecuación 9 en términos de $p$:

$$p_{t+1}=84p_{t}^{3}(1-p_{t})^{6}+56p_{t}^{4}(1-p_{t})^{5}$$ (10)

donde $p$ toma valores de 0 a 1. La curva de probabilidad del campo promedio muestra como se comporta la densidad de los estados en el espacio de evoluciones. La densidad es interpretada a través de la existencia de los puntos fijos en la curva de probabilidad que calcula el polinomio.

Figura 7: Curva de probabilidad de la regla de evolución Life

La gráfica de la Figura 7 muestra la curva de probabilidad que calcula el polinomio de la regla de evolución Life, el eje horizontal $x$ indica el valor al que será evaluado el polinomio, el eje vertical $f(x)$ indica el valor calculado, la función $f(x)$ representa a $p$, es decir, la probabilidad de obtener el estado 1 y es evaluado en el intervalo cerrado $[0,1]$. La diagonal muestra los punto fijos al momento de intersectar algún punto de la curva con la diagonal, eso significa que $f(x)=x$ en ese punto.

El punto fijo estable que se encuentra en el origen de la gráfica indica que la probabilidad de tener 1's en la siguiente generación es cero, porque las vecindades a calcular tienen muy pocas células vivas. Además en el otro extremo del eje $q$ si el espacio de evoluciones tiene muchas células vivas, la probabilidad de tener 1's en la siguiente generación también es cero porque hay sobrepoblación.

Existen dos puntos fijos más, un punto fijo inestable aproximadamente en 0.2 que indica la existencia de comportamientos impredecibles en el espacio de evoluciones, es decir, la densidad que existe en ese momento puede mantenerse igual, crecer o desaparecer por completo en pocas generaciones. El otro punto fijo es un punto crítico y se encuentra aproximadamente en 0.37 que indica la densidad promedio de células vivas que se mantienen vivas en el espacio de evoluciones a través del tiempo.

El análisis consiste en iterar el polinomio del campo promedio para ver como se comporta la curva de probabilidad en cada generación y de esta manera identificar el comportamiento de los estados a través del tiempo. Para obtener el comportamiento en la siguiente generación se sustituye el polinomio $p_{t}$ de la Ecuación 10, en él mismo para obtener la curva de probabilidad en $p_{t+2}$ de la siguente manera:

$$\begin{array}{lll} p_{t+2}&=&84(84p_{t+1}^{3}(1-p_{t+1})^{6}... ...)^{6} \\ & & +56p_{t+1}^{4}(1-p_{t+1})^{5}))^{5} \end{array}$$

este polinomio calculara el comportamiento de la curva en la siguiente generación. Un problema es cuando se desean calcular más generaciones con los polinomios porque crecen exponencialmente, los polinomios para la tercera y cuarta generación ocuparían tres páginas completas.

En la Figura 8 se grafican las curvas de probabilidad para la segunda, tercera, cuarta y quinta generación de la regla de evolución Life. El comportamiento de las células en cada generación limita cada vez más su densidad en el espacio de evoluciones sobre el eje $q$, en general éste es el comportamiento que debe seguir cualquier configuración inicial aleatoria en un largo tiempo.

En la Figura 8 el intervalo de la curva sobre el eje $q$ se hace cada vez más estrecho, esto indica que la población de células vivas es cada vez menor y en efecto a sí ocurre en Life. La densidad promedio de 0.37 calculada para la regla de evolución Life, coincide con otros resultados obtenidos en [SS78] y [GV87]. Los demás casos de estudio analizados en este artículo se estudian de la misma manera, para posteriormente establecer una caracterización a través de sus curvas de probabilidad.

Figura 8: Curvas de probabilidad para la 2a, 3a, 4a y 5a generación