El juego de la vida

En 1948 von Neumann diseñó un constructor universal que viene a ser una máquina que, siguiendo unas instrucciones dadas, es capaz de montar otra máquina con un conjunto de piezas que se encuentran en su entorno, algo que en cierta forma podemos ver en cualquier fábrica moderna que esté robotizada. Pero von Neumann quería llegar un poco más allá y dotar a la máquina y a su entorno de las instrucciones y las piezas necesarias para construir una réplica exacta de sí misma, es decir, quería construir un replicador.

La naturaleza en la que vivimos abunda en replicadores, el ADN es uno de ellos. Curiosamente, von Neumann, una de las mentes teóricas más privilegiadas del siglo XX, pretendía traspasar el terreno teórico y construir de factum su máquina autoreplicante, a la que llamó Kinematon. Cuando estaba peleando con las insalvables dificultades técnicas que suponían la realización práctica del Kinematon, un matemático, Stanislaw Ulam (1909-1984), le dio un buen consejo: le sugirió que si lo que le interesaba era profundizar en las leyes que regían el proceso, dejara los trabajos manuales y se dedicara a establecer un modelo virtual. Stanislaw Ulam (1909-1984) y Konrad Zuse (1910-1995) habían desarrollado, a finales de los años 40, la teoría de lo que se conoce como Autómatas Celulares.

Autómatas celulares

Un autómata celular viene a ser la abstracción matemática de los procesos celulares que observamos en los seres vivos y se puede definir como un sistema dinámico que consta de dos elementos: un espacio celular y unas reglas de comportamiento.

Vamos a dar primero una definición rigurosa de lo que es el espacio celular: un espacio celular es un dominio n-dimensional cuyos elementos, a los que se denominan células, poseen un estado que viene determinado o bien por un número finito de valores {v1,…,vn} o bien por un valor continuo cualquiera. Damos esta definición, que a mucha gente le resultará un tanto críptica, sin ánimo de fastidiar, sino para dejar claro que, aunque esto acabará por desembocar en un juego, no está exento de todo el formalismo que la rigurosidad matemática exige. Pero para dejar las cosas más claras reduzcamos esta definición a su expresión más sencilla y que, además, es la que se utiliza en las exposiciones teóricas.

De entrada, el dominio n-dimensional va ser 2-dimensional, de manera que imagínate que delante tuyo tienes un papel cuadriculado y que cada una de las cuadrículas es una célula. De los dos conjuntos de valores vamos a rechazar, uno es el del conjunto continuo, ya que todo el proceso se va a llevar a cabo en las tripas de un ordenador y éstos se mueven siempre con valores discretos. En cuanto al conjunto {v1,…,vn} posible de dichos valores discretos, nos vamos a quedar sólo con dos {1, 0}. El primero va a significar que la célula esta viva y el segundo que está muerta. También podríamos haber elegido dos colores. En definitiva, tomamos el papel cuadriculado y delimitamos nuestra zona de trabajo, por ejemplo un cuadrado. Ahora cogemos un rotulador rojo y rellenamos unas cuantas casillas:

Ya tenemos nuestro espacio celular en el que hay unas cuantas células vivas, las casillas de color rojo, y unas cuantas células muertas, que son las casillas de color blanco.

Ahora sólo nos queda establecer las reglas de desarrollo, es decir, la descripción precisa de la manera en cómo estas células van a medrar en su entorno. Si la figura anterior la consideramos la etapa 1, debemos tener algún criterio para pasar a la etapa 2 y, evidentemente, debe ser el mismo criterio que nos sirva para pasar de la etapa 2.456 a la 2.457.

Expresado en términos matemáticos, necesitamos un algoritmo que, conociendo el estado de la etapa n, nos permita configurar el de la etapa n+1. Como en nuestra cuadrícula no aparecen, de momento, elementos extraños, como marcianitos comecocos o cosas parecidas, sobre cada una de nuestras células sólo pueden influir las otras células del entorno, lo que nos lleva a precisar el concepto de entorno.

Uno de los entornos más sencillos es el de las reglas Norte, Sur, Este, Oeste, que significa que sobre una célula solo pueden influir las células que estén encima, debajo o a alguno de los dos lados. Éste es el que se llama “entorno de von Neumann”. Si a éstas les añadimos también las celdas diagonales, tendremos lo que se llama un “entorno de Moore”. Se entiende que la posibilidad de definir entornos es casi ilimitada. Podríamos empezar por decir que sólo influyen las celdas que se encuentran a una distancia r determinada, por ejemplo. Hay entornos muy complejos que se definen mediante funciones matriciales, pero de los que no vamos a hablar aquí.

Un sencillo juego

Partamos del espacio celular anterior y definamos las siguientes reglas que van a actuar en un entorno de Moore:

1. Las células con número par de vecinas vivas mueren.

2. Las celdas con número impar de vecinas vivas generan una célula viva.

Sabemos que la influencia en una casilla viene dada por todas las casillas que la rodean. Lo mejor es coger una goma de borrar y empezar por eliminar las casillas rojas que están rodeadas por un número par de casillas rojas. Las que quedan son células vivas. Luego, señalamos las casillas blancas y miramos si tocan a un número impar de casillas rojas; si es así, hay que pintarlas de rojo. Tendremos las tres etapas siguientes:

Si quieres puedes empezar con menos casillas y definir tus propias reglas de juego. Es una actividad ciertamente relajante llevar adelante unas cuantas etapas y contemplar el resultado (existen sencillos programas de ordenador que le pueden plantar rápidamente en la etapa 1000). Nos podemos encontrar con figuras y situaciones sorprendentes. Se pueden crear configuraciones estables, especies en extinción, naturalezas muertas, depredadores, o estructuras que se van moviendo por la cuadrícula sin perder su forma. Éste es, en definitiva el Juego de la Vida. Pero esto, además de ser un juego divertido y tener importantes implicaciones Matemáticas, puede ser una herramienta valiosa para investigar y comprender algunos procesos complejos de la naturaleza, ya que en sí mismo es un potente modelo que se puede aplicar, por ejemplo, a estudiar la forma en cómo una marea negra puede afectar a la fauna marina.

El juego de Conway

La revista Scientific American (Investigación y Ciencia) incluía una sección fija titulada “Juegos matemáticos” en la que varios matemáticos, como M. Gardner, proponían juegos que tras su fachada lúdica solían encerrar conceptos matemáticos profundos. En el número de octubre de 1970 apareció un artículo escrito por el matemático John. H. Conway (Liverpool, 1937), una personalidad científica singular que ha repartido su tiempo por igual entre las áreas más complejas y abstractas de las Matemáticas y el terreno lúdico del juego. En dicho artículo se describía un sencillo juego de tres reglas que marcó un antes y un después en la historia de los autómatas celulares. En palabras del propio Gardner: El juego de Conway enseguida se hizo famoso, pero además abrió las puertas a todo un nuevo campo de investigación matemática, la teoría de los autómatas celulares.

El Juego de la Vida se desarrolla en un entorno de Moore, con un autómata celular binario, es decir, que las células sólo pueden tomar los valores 0 (muerta) o 1 (viva). Originalmente Conway estableció un algoritmo de tres pasos para determinar la configuración de las sucesivas etapas, pero como encerraba ciertas redundancias fueron modificadas posteriormente quedando de la siguiente forma:

1) Una célula muerta renace si tiene tres (ni más ni menos) vecinas vivas. En caso contrario se queda muerta.

2) Una célula viva muere si no hay un mínimo de dos y un máximo de tres células vivas en su entorno. En caso contrario se queda viva.

Por ejemplo, en este espacio celular:

la aplicación de estas reglas conduce a la extinción de nuestra colonia en tan sólo dos pasos.

Conway, cuando definió estas reglas, se había propuesto observar procesos como el nacimiento, la supervivencia y la muerte en colonias de autómatas celulares.

El Juego de la Vida

Las instrucciones que deben implementarse en un programa de ordenador para el Juego de la Vida son sencillas. El resultado puede visualizarse en una pantalla a base de cuadrículas como las que hemos estado usando hasta ahora. En general, la vida de estos autómatas celulares puede discurrir de tres formas diferentes.

Si estudiamos esta configuración

observaremos que no hay ninguna célula muerta que tenga tres vecinas vivas, por lo tanto se quedan todas muertas. Y, por otro lado, cada una de las células vivas tiene un máximo de tres vecinas vivas, por lo que permanecen vivas. De manera que en todas las etapas vamos a obtener el mismo esquema. Este es un tipo de vida a la que se le llama “naturaleza muerta”. La mayoría de las naturalezas muertas tiene nombre. La que acabamos de ver se llama bloque. Otras son el barco:

La serpiente

La charca

o la Tina

Otro tipo de configuración posible es la de “oscilador” o “flip-flops”, que son los osciladores estables de período dos, porque adoptan dos configuraciones que se van alternando. Es el caso de la siguiente que, en dos etapas, o períodos, como también se les llama, vuelven a la configuración original:

 

 

Los hay también de períodos tres, cuatro,…etc., según el número de configuraciones distintas que adoptan.

Por ejemplo, el Pentadeclatón es un oscilador de período 15.

Puede adoptar posiciones de depredador en las que devora deslizadores de 5 células. En cambio en otras posiciones puede convertir estos deslizadores en su simétrico. Todo un bicho.

Zoológico de autómatas

Existen autómatas celulares «famosos», como son

Mechas

Estructura largada que desaparece a velocidad constante. Hay varios tipos de mechas. La más simple es

Deslizadores

Son configuraciones que se van desplazando por la pantalla sin perder su forma. Un ejemplo sencillo de deslizador es

Cuando una configuración o una célula se mueve a un cuadro por pantalla se dice que se mueve a la “velocidad de la luz”. Al igual que sucede en la física del mundo real, en el Juego de la Vida no se puede alcanzar la velocidad de la luz. Conway demostró que en el sentido vertical o en el horizontal la velocidad máxima que se podía alcanzar por pantalla era de un medio de la velocidad de la luz, mientras que en sentido oblicuo es de un cuarto de la misma.

Matusalén

Recibe este nombre cualquier configuración que contenga un número de células vivas con menos de diez cuadros y con la propiedad de que no se estabiliza antes de que hayan pasado 50 etapas. El matusalén más viejo que se conoce recibe el nombre de “bellota” y no se estabiliza hasta las 5.206 etapas.

El autoreplicador Universal de von Neumann

Una máquina de von Neumann consiste en un módulo de fabricación que, si tiene las instrucciones precisas y un entorno de piezas adecuado, es capaz de construir lo que sea, y que además posee las instrucciones necesarias para construirse a sí misma.

Von Neumann se vio obligado a introducir una tercera condición para evitar lo que se llama una “regresión infinita”, que consiste en lo siguiente: en alguna parte de la máquina deben estar las instrucciones que describen la propia máquina en su totalidad. Por lo tanto, dentro de dichas instrucciones debe haber otras instrucciones que las describen, y así sucesivamente. Una máquina, sea como sea, no puede contener una regresión infinita como ésta.

Para solucionarlo añadió una tercera componente, que era un copiador de instrucciones, de forma que la máquina completa está formada por un constructor, la lista de instrucciones y un copiador. De esta manera, en la primera fase la lista de instrucciones es interpretada y en la segunda fase es simplemente copiada. Von Neumann estaba tratando de descubrir cuál era el secreto de la vida, por lo menos en su faceta reproductora. Quería demostrar que no obedecía a extrañas leyes ocultas, sino a reglas matemáticas, más o menos simples, aquéllas que conforman el verdadero lenguaje de la naturaleza. Crack y Watson desvelaron este secreto de la vida en el terreno de lo concreto. Al estudiar la manera en cómo funciona el ADN se vuelve a encontrar la estructura abstracta de la máquina autoreplicante: interpretación de instrucciones y copia exacta de las instrucciones.

Para construir una máquina autoreplicadora en un ordenador es necesario diseñar un autómata celular que emule a una máquina de Turing. Teóricamente es posible diseñar las puertas lógicas necesarias para ello: NOT-AND-OR. Se puede, por ejemplo, diseñar una puerta NOT con lo que se denomina un “cañón de autómatas deslizadores”, un esquema demasiado complejo para describirlo en este contexto. Von Neumann llegó a demostrar que, en un entorno Neumann, un autómata celular de 200.000 casillas sería capaz de autoreproducirse. Algo que, de momento, va más allá de nuestras posibilidades de computación.

Si algún día es posible la realización práctica de un autoreplicador de von Newmann, quiere decir que en alguna parte habrá un robot rodeado de piezas que se pondrá a trabajar, y al cabo de un tiempo aparecerá una réplica exacta del mismo. Entonces serán dos los que se pondrán a fabricar, y luego cuatro, y así en progresión geométrica. Lo que von Neumann no previó, ni nadie puede prever, es qué tal se llevarán estos robots con los humanos, ya que hay que tener en cuenta que en muy poco tiempo acabarían por representar una mayoría abrumadora e imparable.

Una conversación

Dos especialistas en autómatas celulares podrían mantener una conversación del tipo siguiente:
-Llevo varias semanas trabajando en Vida 4555
-Interesante. Yo me estoy dedicando a Vida 5766. Le estoy encontrando una aplicación práctica a la forma en cómo se propagan los incendios en los bosques.
Su intención no es que usted, que se está tomando un café en la mesa de al lado, no se entere de nada, sino que están hablando de tipos de vida muy concretos. Simplemente hay que conocer el significado de los cuatro dígitos. El primero de ellos hace referencia al número mínimo de células que han de rodear a una célula viva para que no se muera. El segundo es lo mismo, pero hace referencia al número máximo. El tercero es el número mínimo de células vivas que ha de haber para que exista la posibilidad de recobrar vida. Y el cuarto y último representa el número máximo de vecinas que se pueden tener para recobrar vida. EL juego de la vida de Conway es Vida 2333.

Fractales

Los autómatas celulares pueden ser utilizados para la obtención de fractales, o para ser exactos, para una buena aproximación de los mismos. Un curioso ejemplo es el siguiente: definimos las siguientes reglas en un entorno de Moore: 1) cualquier célula que se encuentre en el borde inferior del espacio celular no muere nunca; 2) una célula nace o permanece viva si exactamente una de las tres células de la fila inferior está viva. En cualquier otro caso, muere. La primera etapa empieza con una célula viva en el borde inferior. Las cuatro primeras etapas están representadas en el cuadro siguiente:

Realizando un buen número de etapas se llegaría a una figura como ésta:

que es un conocido fractal llamado el triángulo de Sierpinski.

Una de las cosas importantes que parece estar ausente en el Juego de la Vida es la energía necesaria para que la vida transcurra. En realidad esto no es así. Si instalas en tu ordenador un programa de autómatas celulares y llevas a cabo todos los pasos de su configuración, lo que habrá sucedido es que parte de la energía que proviene de la fuente de alimentación sirve para generar y alimentar a tus autómatas celulares y el resto desaparece como energía térmica.