En 1970, el matemático John Conway creó un juego sin jugadores que evoluciona completamente desde su estado inicial. El juego se desarrolla en una especie de universo computacional llamado autómata celular. Este universo consta de una cuadrícula infinita de cuadrados que pueden estar vivos o muertos y que, en cada paso de tiempo, pueden pasar de un estado a otro según los estados de los cuadrados que lo rodean.
Desde entonces, este autómata celular se conoce como el Juego de la Vida de Conway y es famoso por la extraordinaria complejidad que emerge en su interior. Este universo computacional alberga balizas que destellan, púlsares que ganan al tiempo y “planeadores” y “naves espaciales” que vuelan a través del cielo computacional. Los científicos informáticos han demostrado que este mundo puede albergar computadoras en forma de máquinas de Turing universales y replicadores que pueden producir copias exactas de sí mismas.
Cambio de paso
De hecho, nadie está muy seguro de dónde están los límites del Juego de la Vida y los científicos informáticos todavía están luchando con numerosos problemas sin resolver. Uno de ellos se relaciona con la periodicidad de los patrones en este universo. Desde hace tiempo está claro que algunos patrones no cambian con el tiempo; en otras palabras, tienen una periodicidad de un paso de tiempo. Otros repiten cada dos pasos o tres o cuatro o cinco pasos.
Luego, en la década de 1990, quedó claro que era posible producir patrones con cualquier periodicidad mayor o igual a 43 pasos de tiempo. Los matemáticos lo demostraron enviando señales modeladas a lo largo de pistas que forman bucles. El bucle más pequeño posible se puede recorrer en 43 pasos. Al aumentar su tamaño, los matemáticos pueden hacer que los patrones se repitan en cualquier cantidad de pasos de tiempo.
Ésto plantea una pregunta interesante. ¿Es posible hacer patrones que se repitan en todos los períodos posibles? En otras palabras, ¿el Juego de la Vida es omniperiódico?
Dada la prueba anterior, esto se reduce al problema de encontrar patrones oscilantes que se repitan para cada período del 1 al 42. Los primeros fueron relativamente fáciles de encontrar. “Los períodos en el “medio faltante”, 15 < p < 43, particularmente aquellos que son primos, resultaron más difíciles de encontrar", dicen Mitchell Riley, de la Universidad de Nueva York en Aby Dhabi y sus colegas.
Pero a medida que avanzaba el trabajo, los investigadores empezaron a llenar los vacíos. “En el cambio de milenio, sólo quedaban por encontrar doce períodos: 19, 23, 27, 31, 34, 37, 38, 39, 41, 43, 51 y 53”, dicen.
En este siglo, los informáticos encontraron todos estos osciladores, excepto dos: 19 y 41.
La última pieza del rompecabezas omniperiódico de la vida (fuente: arxiv.org/abs/2312.02799)
Ahora Mitchell y sus compañeros anuncian que el trabajo está terminado. “La búsqueda finalmente terminó con el descubrimiento de osciladores que tienen los dos últimos períodos”, afirman. Esto demuestra de una vez por todas que el Juego de la Vida es realmente omniperiódico.
El artículo de Mitchell y sus colegas describe los 43 osciladores junto con las técnicas que los informáticos y matemáticos han desarrollado para encontrarlos y construir osciladores cada vez más capaces.
Señalan que el problema de la omniperiodicidad ha sido un punto central de la investigación sobre el Juego de la Vida. Este trabajo ha dado lugar a una gran cantidad de técnicas, herramientas y enfoques para explorar y caracterizar este universo computacional.
Pero ahora que el problema está resuelto, ¿qué sigue? Mitchell y sus compañeros señalan numerosos problemas sin resolver que podrían proporcionar un punto focal similar para los investigadores. Dicen que el problema de la velocidad de la nave espacial es quizás el más importante.
Velocidades de la nave espacial
Una nave espacial es un patrón que se repite en otro lugar desde su posición original. En otras palabras, se traduce a través del cielo computacional. (Los osciladores ordinarios pueden considerarse como naves espaciales estacionarias).
Teniendo en cuenta que nada puede viajar a través de la red más rápido que una unidad de celda por unidad de tiempo, los autores dicen que hay buenas razones para pensar que todas las velocidades de una nave espacial suficientemente lentas deberían ser posibles.
Sin embargo, eso deja abierta la cuestión de “cuál de las velocidades teóricamente posibles de la nave espacial se puede alcanzar”, dicen.
Luego está el problema de encontrar los osciladores más pequeños de un período determinado. Muchos de los primeros descubiertos en cada época ya no son los más pequeños, afirman. El desafío de encontrar otros más pequeños persiste durante muchos períodos.
Hay muchos otros problemas abiertos. Como finalmente concluyen Mitchell y compañía: “¡El trabajo de la vida nunca termina!”
Ref: El juego de la vida de Conway es omniperiódico: arxiv.org/abs/2312.02799