Teoria de Autómatas y Computación: Juego de la vida y la Regla 100

Juego de la vida

¿En qué consiste?

El juego de la vida es un autómata celular diseñado por el matemático británico John Horton Conway en 1970, vio la luz en octubre de ese mismo año en la revista Scientific American. El interés de este autómata celular reside en su equivalencia con una máquina de Turing, es decir, todo lo que se puede computar algorítmicamente se puede computar en el juego de la vida.

Pero, ¿qué es un autómata celular?

Un autómata celular es una cuádrupla formada por 4 elementos y que evoluciona en pasos discretos.los elementos que forman la tupla son los que siguen:

Una rejilla de enteros de extensión infinita y dimensión $d \in \mathbb{Z}^+$ en la que a cada celda se la conoce con el nombre de célula.
Un conjunto finito de estados que puede tomar cada célula.
Una definición de vecindario de la célula que estará formado por células próximas a la misma.
Una función de transición f que dependiendo del estado de la célula y del estado de su vecindario determinará el nuevo estado de cada una de las células para la próxima interacción.

La vida se considera un buen ejemplo de emergencia y autoorganización. En este interesante autómata se puede observar como patrones complejos pueden provenir de la implementación de reglas muy sencillas. La vida tiene una variedad de patrones reconocidos que provienen de posiciones iniciales.

Para muchos aficionados, el juego de la vida sólo era un desafío de programación y una manera divertida de usar ciclos de la CPU. Para otros, sin embargo, el juego adquirió más connotaciones filosóficas.

El juego de la vida es en realidad un juego de cero jugadores, lo que quiere decir que su evolución está determinada por el estado inicial y no necesita ninguna entrada de datos posterior. El "tablero de juego" es una malla formada por cuadrados ("células") que se extiende por el infinito en todas las direcciones. Cada célula tiene 8 células vecinas, que son las que están próximas a ella, incluso en las diagonales. Las células tienen dos estados: están "vivas" o "muertas" (o "encendidas" y "apagadas").

El estado de la malla evoluciona a lo largo de unidades de tiempo discretas (se podría decir que por turnos). El estado de todas las células se tiene en cuenta para calcular el estado de las mismas al turno siguiente. Todas las células se actualizan simultáneamente.

Las transiciones dependen del número de células vecinas vivas:

Nacimiento: se reemplaza una célula muerta por una viva si dicha célula tiene exactamente 3 vecinos vivos.
Muerte: se reemplaza una célula viva por una muerta si dicha célula no tiene más de 1 vecino vivo (muerte por aislamiento) o si tiene más de 3 vecinos vivos (muerte por sobrepoblación).
Supervivencia: una célula viva permanecerá en ese estado si tiene 2 o 3 vecinos vivos.

Ejemplos de patrones

En el juego de la vida podemos encontrarnos una gran cantidad de tipos de patrones, pero podemos hacer una primera distinción como la de a continuación:

patrones estáticos ("vidas estáticas"):

Como podemos observar, permanecerán las celdas constantes, siempre vivas, porque se cumplen unas a otras.

patrones recurrentes ("osciladores", un conjunto de vidas estáticas):

patrones que se trasladan por el tablero ("naves espaciales", spaceships):

patrones que crecen indefinidamente (pistolas, locomotoras, criaderos…)

Pistola de planeadores de Gosper

Regla 110

¿Qué es la regla 110?

Otro conocido autómata celular es el conocido como “la regla 110“. Al igual que el juego de la vida se trata de un autómata Turing-Completo (demostrado por Stephen Wolfram quien estudió y dio una clasificación para los autómatas celulares), es decir cualquier algoritmo es computable con la regla 110.

¿Cómo funciona?

Este autómata es uno de los más sencillos pues consta de una rejilla unidimensional, es decir una tira de células. Además el vecindario de cada una está formado por las dos adyacentes y solo consta de dos estados posibles. Su evolución a lo largo de los ciclos de ejecución viene dada por la siguiente regla:

Este conjunto de reglas se puede representar gráficamente sobre la rejillas del autómata de la siguiente manera:

Si observamos los nuevos estados posibles podemos advertir la secuencia binaria “01101110” que corresponde con el número decimal 110, de ahí el nombre del autómata.

En una ejecución de la regla 110, se comienza con una tira de unos y ceros los cuales se van transformando a lo largo del tiempo (filas inferiores en la rejilla) formando secuencias totalmente impredecibles, como se puede observar en la imagen a continuación.

Tras sus numerosas investigaciones sobre autómatas celulares Stephen Wolfram, concluyó su trabajo proponiendo una clasificación de los autómatas celulares en 4 tipos o clases, que son los que siguen:

Clase I. La evolución lleva a una configuración estable y homogénea, es decir, todas las células terminan por llegar al mismo valor.
Clase II. La evolución lleva a un conjunto de estructuras simples que son estables o periódicas.
Clase III. La evolución lleva a un patrón caótico.
Clase IV. La evolución lleva a estructuras aisladas que muestran un comportamiento complejo (es decir, ni completamente caótico, ni completamente ordenado, sino en la línea entre uno y otro, este suele ser el tipo de comportamiento más interesante que un sistema dinámico puede presentar).