Game of Life o
el Juego de la Vida es un autómata celular creado por John Conway en 1970. El juego no involucra otros jugadores aparte de una malla teóricamente infinita de
celdas/células denominada
universo en la que se manifiesta un proceso evolutivo determinado por el
estado inicial y un conjunto de reglas. Se dice que una célula está
muerta cuando su celda correspondiente está vacía o inactiva, mientras que una célula
viva es cualquiera que se encuentre activa.
Las reglas del juego describen la forma como la malla evolucionara en el siguiente instante de tiempo:
- Nacimiento: Una célula muerta en un tiempo t estará viva en el tiempo t+1 si exactamente 3 de sus 8 vecinos están vivos en el tiempo t.
- Muerte: Una célula puede morir por:
- Sobrepoblación: Si una célula está viva en el instante t y 4 o más de sus vecinos también están vivos en el tiempo t, la célula morirá en t+1.
- Exposición: Si en el tiempo t una célula viva tiene sólo uno o ningún vecino vivo, morirá en el tiempo t+1.
- Sobrevivencia: Una célula sobrevive del tiempo t al tiempo t+1 si y sólo si 2 o 3 de sus vecinos están vivos en el instante t.
Las reglas son aplicadas en la sucesión de instantes representados por un tiempo inicial
t y los sucesivos
t+1,
t+2,
..., lo que provoca a la configuración inicial del universo
evolucionar, o lo que es equivalente, que el juego
se juegue a sí mismo; lo que podría parecer una situación aburrida de no ser porque existen algunas situaciones interesantes, como las
formas de vida que pueden surgir del juego, el hecho de que ciertos juegos que pueden durar
indefinidamente y que un juego puede ser usado para encontrar una solución a
cualquier problema que se pueda resolver computacionalmente.
Las
formas de vida son resultados de la aplicación de las reglas del juego que pueden surgir ya sea espontáneamente, como parte de un juego, o ser creados intencionalmente usando ciertos estados iniciales. Algunas formas de vida populares son:
- Naturaleza Muerta: Patrones estables, finitos y no vacíos: Block, Beehive, Boat, Ship, Loaf.
- Formas de vida periódica / Osciladores: Oscilan periódicamente: Blinker [2], Toad [2], Glider [4], Spaceships [2], Guns (periódicamente disparan patrones móviles), Garden of Eden (sólo como estado inicial) Penadecatlon [15].
- Formas de vida no periódicas: Siguen su proceso evolutivo hasta desvanecerse o reducirse a osciladores o naturaleza muerta. Ejemplos de ello son el patrón Pi y R-pentomino,
No es fácil anticipar cómo evolucionará un juego a partir de un patrón inicial, por ejemplo, en la evolución de un patrón lineal de
n células, como configuración inicial, se puede observar:
- n = 1,2: Se desvanece de inmediato
- n = 3: Blinker
- n = 4: Se convierte en Beehive en t+2
- n = 5: Traffic Lights en t+6
- n = 6: Se desvanece en t+12
- n = 7: Simetric Screen y Honey Farm
- n = 8: Produce 4 Blocks y 4 Beehives
- n = 9: 2 conjuntos de Traffic Lights
- n = 10: Se vuelve un Pentadecathlon con periodo 15
- n = 11: Se vuelve en 2 Blinkers
- n = 12: Produce 2 Beehives
- n = 13: Cambia a dos Blinkers
- n = 14,15: Se desvanece por completo
- n = 16,17: Se vuelven 4 Blocks
- n = 18,19: Se desvanece
- n = 20: Forma 2 Blocks
Tampoco resulta obvio cuándo un patrón inicial crecerá de forma
indefinida, de hecho, hasta 1970 no se sabía si alguno podía hacerlo por lo que John Conway ofreció un premio (se dice que de $50) a quien proporcionara una respuesta a este misterio. El grupo del MIT encabezado por R.W. Gosper ganó el premio al descubrir que el
Glider Gun -que emite un nuevo
Glider cada 30 generaciones de forma indefinida- crece permanentemente, lo que demuestra la existencia de formas de vida siempre en crecimiento.
En el
Juego de la Vida es posible definir un parámetro denominado
velocidad de la luz (
c, como en física), como la máxima velocidad de cualquier objeto móvil, la tasa de propagación de un paso (horizontal, vertical o diagonal) por generación. Este parámetro representa dos cotas: la
velocidad máxima a la que la
información puede viajar y el
límite de la velocidad de cualquier patrón. A un
Glider le toma 4 generaciones moverse una celda en diagonal, de modo que tiene una velocidad de c/4. Un
Light Weight Spaceship se mueve ortogonalmente una celda en cada nueva generación, de modo que tiene una velocidad de
c/2. Aunque la velocidad de la luz es definida como una celda por generación, se ha mostrado que la máxima velocidad alcanzable por cualquier objeto móvil es
c/4 para movimientos diagonales y
c/2 para ortogonales.
Es posible representar la operación de compuertas lógicas mediante arreglos de patrones en un
Juego de la Vida usando
flujos de
Gliders para representar una señal o flujo de
bits y empleando las propiedades de las
colisiones entre patrones, por ejemplo, es posible invertir un flujo de
Gliders mediante el uso de una
Glider Gun controlando el choque de dos
Gliders en el ángulo adecuado, interpretando el resultado de la reacción como el resultado de la operación lógica
NOT.
Una
Glider Gun arroja patrones al flujo de entrada, de modo que cuando hay un patrón de entrada (1 lógico) ambos se eliminan resultado en un
espacio de salida (0 lógico) mientras que si el patrón de entrada es un
espacio (0), el
Glider de la
Glider Gun se llega a la salida, lo que se interpreta como un 1.
Dos
Gliders en colisión también pueden formar un
Eater que al chocar con otro
Glider le devora. Manipulando las direcciones y ángulos del flujo de
Gliders y aprovechando las diferentes reacciones que producen al chocar es posible construir representaciones que emulan la operación de las compuestas
OR y
AND.
Usando estas compuertas es posible construir una lenta y primitiva
computadora funcional a partir del
Juego de la Vida. A la propiedad de poder calcular mediante computo todo lo que es computable se llama
universalidad. Una forma equivalente para decir que el
Juego de la Vida es universal y que se puede construir una
Máquina de Turing a partir de ello. Las
Máquinas de Turing tienen las siguientes características:
- Un conjunto finito de estados.
- Reglas para las transiciones entre estados.
- En ellas se especifica el estado actual.
- El símbolo leído de la celda en turno.
- El estado al que se moverá.
- El símbolo que ha de escribirse en la celda actual.
- La dirección en la que se moverá la máquina por la cinta.
- Una secuencia de celdas infinita conocida como cinta.
- Un conjunto de símbolos que describen los posibles contenidos de cada celda en la cinta.
- La habilidad de leer y escribir el símbolo en una celda.
- La habilidad de moverse a través de la cinta para acceder a diferentes celdas.
- En cada paso, la Máquina de Turing lee la celda actual en la cinta, encuentra la regla de transición apropiada que coincide con el estado actual y símbolo leído y cambia al nuevo estado que se ha especificado, escribe el símbolo especificado y mueve la máquina en la dirección específicada.
La famosa tesis de
Church-Turing establece que todo lo que es computable puede ser computado por una
Máquina de Turing. Esta declaración no ha sido probada pero es casi universalmente aceptada. Si es verdadera, entonces el poder de una
Máquina de Turing es mayor que el de las computadoras modernas. Se dice que algo es
Turing-completo si contiene una
secuencia de procedimientos con el mismo poder computacional que una
Máquina de Turing. Si se demuestra que el Juego es Turing-completo, se puede decir que Life es tan poderoso como cualquier computadora y que podemos computar cualquier problema que pueda solucionarse mediante computación usando el
Juego de la Vida.
Referencias:
