Juego de la vida

Animación del juego de la vida de Conway

El juego de la vida es un autómata celular diseñado por el matemático británico John Horton Conway en 1970.

Hizo su primera aparición pública en el número de octubre de 1970 de la revista Scientific American, en la columna de juegos matemáticos de Martin Gardner. Desde un punto de vista teórico, es interesante porque es equivalente a una máquina universal de Turing, es decir, todo lo que se puede computar algorítmicamente se puede computar en el juego de la vida.

Desde su publicación, ha atraído mucho interés debido a la gran variabilidad de la evolución de los patrones. Se considera que la vida es un buen ejemplo de emergencia y autoorganización. Es interesante para los científicos, matemáticos, economistas y otros observar cómo patrones complejos pueden provenir de la implementación de reglas muy sencillas.

La vida tiene una variedad de patrones reconocidos que provienen de determinadas posiciones iniciales. Poco después de la publicación, se descubrieron el pentaminó R, el planeador o caminador (en inglés glider, conjunto de células que se desplazan) y el explosionador (células que parecen formar la onda expansiva de una explosión), lo que atrajo un mayor interés hacia el juego. Contribuyó a su popularidad el hecho de que se publicó justo cuando se estaba lanzando al mercado una nueva generación de miniordenadores baratos, lo que significaba que se podía jugar durante horas en máquinas que, por otro lado, no se utilizarían por la noche.

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. Desarrolló un seguimiento casi fanático a lo largo de los años 1970 hasta mediados de los 80.

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, incluidas 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:

  • Una célula muerta con exactamente 3 células vecinas vivas "nace" (al turno siguiente estará viva).
  • Una célula viva con 2 ó 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por "soledad" o "superpoblación").

Ejemplos de patrones

Existen numerosos tipos de patrones que pueden tener lugar en el juego de la vida.

Osciladores

El blinker es el oscilador más pequeño y frecuente.

Los osciladores son patrones que son predecesores de si mismos. En otras palabras, son patrones que tras un número finito de generaciones vuelven a su estado inicial. El número de generaciones determina el período del oscilador. Se han descubierto osciladores de todos los períodos, pues hay reglas para generar osciladores de cualquier período deseado.

Los osciladores tienen un rotor y un estátor. El rotor son las células que cambian de estado en algún momento de la evolución del oscilador. El estátor son las células que permanecen vivas durante todas las fases de la evolución del oscilador. Así por ejemplo, en el caso del blinker, el más simple y frecuente de todos los osciladores, el estátor es la célula central, y el rotor son las células izquierda, derecha, arriba y abajo de la célula central.

Vidas estáticas

Las vidas estáticas son patrones que no cambian de una generación a la siguiente. Las vidas estáticas se puede considerar como osciladores de período 1. En general se asume que las vidas estáticas son finitas y no vacías. Se las puede dividir en vidas estáticas estrictas y pseudo vidas estáticas. Las vidas estáticas estrictas son aquellas cuyas partes no son estáticas por si mismas.

Naves espaciales

El planeador (glider) es la nave espacial más pequeña y frecuente.

Las naves espaciales son patrones que reaparecen en otra posición tras completar su período. Esto es, son patrones que tras un número finito de generaciones vuelven a su estado original pero en una ubicación diferente. La velocidad de una nave es el número de celdas que se desplaza dividido por la longitud de su período. El máximo posible es una celda por generación, velocidad que se conoce como c (metafóricamente, la velocidad de la luz)

Matusalenes

Los matusalenes son patrones que pueden evolucionar a lo largo de muchos turnos, o generaciones, antes de estabilizarse. El patrón Diehard desaparece después de 130 turnos, mientras que Acorn tarda 5206 turnos en estabilizarse en forma de muchos osciladores, y en ese tiempo genera 13 planeadores.

  Game of life diehard.png    Game of life methuselah.png 
Diehard Acorn

En la aparición original del juego en la revista, Conway ofreció un premio de 50 dólares por el descubrimiento de patrones que crecieran indefinidamente. El primero fue descubierto por Bill Gosper en noviembre de 1970. Entre los patrones que crecen indefinidamente se encuentran las " pistolas" ( guns), que son estructuras fijas en el espacio que generan planeadores u otras naves espaciales; " locomotoras" ( puffers), que se mueven y dejan un rastro de basura y " rastrillos" ( rakes), que se mueven y emiten naves espaciales. Gosper descubrió posteriormente un patrón que crece cuadráticamente llamado " criadero" ( breeder), que deja atrás un rastro de pistolas. Desde entonces se han creado construcciones más complicadas, como puertas lógicas de planeadores, un sumador, un generador de números primos y una célula unidad que emula el juego de la vida a una escala mucho mayor y una velocidad menor.

La primera pistola de planeadores que se ha descubierto sigue siendo la más pequeña que se conoce:

Game of life glider gun.png
Pistola de Gosper
Pistola de planeadores de Gosper (Gosper Glider Gun)

Se han hallado posteriormente patrones más simples que también crecen indefinidamente. Los tres patrones siguientes crecen indefinidamente. Los dos primeros generan un motor interruptor que deja bloques, mientras que el tercero genera dos. El primero tiene una población mínima de 10 células vivas, el segundo cabe en un cuadrado 5 × 5 y el tercero sólo tiene un cuadrado de altura:

Game of life infinite1.png      Game of life infinite2.png

Game of life infinite3.png

Es posible que los planeadores interactúen con otros objetos de forma interesante. Por ejemplo, si se disparan dos planeadores hacia un bloque contra el que chocan de la forma correcta, el bloque se acercará al origen de los planeadores, pero si se disparan tres planeadores de forma correcta el bloque se alejará. Esta "memoria del bloque deslizante" se puede emplear para simular un contador. Es posible construir puertas lógicas AND (y, conjunción), OR (o, disyunción) y NOT (no, negación) mediante el uso de planeadores.

También se puede construir una estructura que actúe como una máquina de estados finitos conectada a dos contadores. Esto tiene la misma potencia computacional que una máquina universal de Turing, así que el juego de la vida es tan potente como un ordenador con memoria ilimitada: por ello es Turing-completo.

Además, una estructura puede contener un conjunto de pistolas que se combinen para construir nuevos objetos, incluso copias de la estructura original. Se puede construir un "constructor universal" que contenga un ordenador Turing-completo y que pueda generar muchos tipos de objetos complejos, incluso nuevas copias de sí mismo. (Vienen descripciones de estas construcciones en Winning Ways for your Mathematical Plays de Conway, Elwyn Berlekamp y Richard Guy)

Other Languages