El mítico ‘juego de la vida’ del matemático John Conway sigue siendo uno de los problemas clásicos de programación 50 años después
Divulgadores del Misterio
Publicado el 13/04/2020
De John Horton Conway (Liverpool, 1937) se han dicho muchas cosas, pero hay una especial que Donald Knuth, leyenda de la programación, mencionó en un relato corto: «le dijo a los números, «creced y multiplicaos», y así lo hicieron, porque entre otras muchas cosas este prolífico matemático inglés se inventó un nuevo sistema numérico, el de los números surreales, infinitamente grandes e infinitesimalmente pequeños.
Para los programadores, no obstante, Conway es célebre sobre todo por su trabajo en teoría de juegos y, en concreto, por la creación del «juego de la vida» en 1970, un autómata celular que mantiene una fuerta analogía con la máquina de Turing: todo lo que se puede computar algorítmicamente se puede computar en el juego de la vida. El juego de la vida ha tenido una relevancia espectacular entre los desarrolladores, y para algunos se convirtió en una obsesión durante los 70 y parte de los 80.
Conway, ¿víctima del COVID-19?
Varios han sido los mensajes en Twitter que apuntaban al fallecimiento el pasado 11 de abril de Conway debido al COVID-19. La noticia no ha sido confirmada oficialmente, pero tanto su biógrafa, Siobhan Roberts, como uno de sus colegas matemáticos, Colm Mulcahy, apuntaban al triste suceso.
Eso ha hecho que rápidamente se recuerde la figura del que fue uno de los matemáticos más importantes de las últimas décadas. Su trabajo en teoría de grupos finitos, de nudos, de números y sobre todo de juegos es extraordinari, y se une por supuesto a la citada creación del sistema de números surreales y a la notación para números extremadamente largos, la llamada notación de flecha encadenada de Conway.
Muchos de esos logros pueden ser desconocidos para nuestros lectores, pero puede que uno de sus trabajos sí os suene: se trata del «juego de la vida», una creación que derivó en uno de los problemas matemáticos más interesantes a la hora de ser reproducido en un ordenador mediante todo tipo de algoritmos y lenguajes de programación.
El infinito juego de la vida
Entre las muchas curiosidades del juego de la vida está el hecho de que en realidad no puedes «jugar» como tal a él. Es un juego de cero jugadores, lo que significa que una vez indicas el estado inicial, te olvidas de participar más y te conviertes en un mero espectador.
Este autómata celular va mostrando su estado a través de una malla plana infinita formada por cuadrados denominados células. Cada célula tiene 8 células vecinas, y cada una de las células tiene dos estados, «viva» («encendida») o muertas («apagada»). A partir de ahí el estado evoluciona en una especie de turnos de acuerdo a dos reglas:
- Una célula muerta con exactamente 3 células vecinas vivas «nace» (es decir, al turno siguiente estará viva)
- Una célula viva con 2 o 3 células vecinas vivas sigue viva, pero en otro caso muere (por «soledad» o «superpoblación»)
Hay numerosos patrones de células que se pueden dar en el juego de la vida. Los osciladores, por ejemplo, acaban volviendo a su estado inicial tras un número finito de generaciones o turnos (su «período»), mientras que las vidas estáticas son patrones que no cambian nunca, o en otras palabras: son osciladores de período 1. Hay «naves espaciales» que cambian de posición tras cada generación, «matusalenes» que tardan muchísimos turnos en estabilizarse y multitud de variantes de todos ellos.
Tras 1.018 generaciones, en esto se había convertido ese estado inicial que creamos con la palabra «Xataka».
Con el juego de la vida se puede construir una estructura que actúe como una máquina de estados finitos, y que tendría el mismo comportamiento y potencia que una máquina de Turing.
La variedad y complejidad (o simplicidad, según se mire) del juego se puede disfrutar fácilmente en implementaciones online como esta en la que podremos elegir distintos patrones para ver cómo evolucionan. Podemos avanzar manual o automáticamente a menor o mayor velocidad, y podemos extender la malla hasta tener una de gran tamaño.
En esa malla podemos incluso dibujar cualquier patrón para ver cómo evoluciona (opción «Clear», tras lo cual podemos marcar y desmarcar células una a una), lo que permitirá experimentar con una creación singular que ha sido objeto de estudio de programadores durante décadas. 50 años después de su creación; de hecho, sigue siendo uno de los problemas de programación clásicos.
Lo demuestra el hecho de que ese código, relativamente sencillo, cuenta con soluciones en decenas de lenguajes de programación, desde JavaScript a Python pasando, por supuesto, por el BASIC del ZX Spectrum.
Una curiosidad: hasta Steve Jobs y Steve Wozniak mostraron aquel código funcionando en el Apple II durante su presentación original ante una junta de inversores de la empresa de Regis McKenna. Casi nadie debió entender qué era aquello, pero los creadores de Apple estaban absolutamente entusiasmados.
Maravilloso.
FUENTE
