El 'juego de la vida' de las matemáticas revela patrones repetitivos largamente buscados | Revista Quanta

En 1969, el matemático británico John Conway ideó un conjunto de reglas fascinantemente simples para crear comportamientos complejos. Su Juego de la Vida, a menudo denominado simplemente Vida, se desarrolla en una cuadrícula infinita de celdas. Cada célula puede estar "viva" o "muerta". La cuadrícula evoluciona a lo largo de una serie de turnos (o “generaciones”), y el destino de cada celda está determinado por las ocho celdas que la rodean. Las reglas son las siguientes:

1. Nacimiento: una célula muerta con exactamente tres vecinos vivos cobra vida.
2. Supervivencia: una célula viva con dos o tres vecinos vivos se mantiene viva.
3. Muerte: Muere una célula viva con menos de dos o más de tres vecinos vivos.

Estas reglas simples crean una variedad sorprendentemente diversa de patrones, o “formas de vida”, que evolucionan a partir de las diferentes configuraciones iniciales posibles de la red. Los amantes del juego han contabilizado y taxonomizado estos patrones en una metodología en constante expansión. catálogo en línea. Conway descubrió un patrón llamado intermitente, que oscila entre dos estados.

Al año siguiente, encontró un patrón mucho más complicado llamado púlsar, que oscila entre tres estados diferentes.

Poco después de que se descubrieran los osciladores, los primeros exploradores del juego se preguntaron si existían osciladores para cada período. “Al principio, sólo vimos los períodos 1, 2, 3, 4 y 15”, dijo el programador informático y matemático Bill Gosper, quien descubriría 17 nuevos osciladores diferentes durante las siguientes décadas. Los osciladores del período 15 (que se muestran a continuación) aparecieron sorprendentemente a menudo en búsquedas aleatorias.

Las sorpresas acechaban a quienes estuvieran dispuestos a encontrarlas. "Después de horas y días de visualización, el período 5 parecía imposible", dijo Gosper. Luego, en 1971, dos años después de que se inventara el juego, se encontró uno. La búsqueda de nuevos osciladores se convirtió en un foco importante del juego, una búsqueda reforzada por la llegada de la tecnología informática. Los relatos de búsquedas encubiertas realizadas en computadoras de oficina se han convertido en la piedra angular del folclore del juego. "La cantidad de tiempo de computadora robado a los mainframes corporativos y universitarios fue asombrosa", dijo Gosper.

A lo largo de la década de 1970, matemáticos y aficionados completaron los otros períodos cortos y encontraron algunos más largos. Finalmente, los matemáticos descubrieron una forma sistemática de construir osciladores de período largo. Pero resultó difícil encontrar osciladores con períodos entre 15 y 43. "La gente ha estado tratando de encontrar el punto medio durante años", dijo Maia Karpovich, estudiante de posgrado de la Universidad de Maryland. Llenar los vacíos obligó a los investigadores a idear una serie de nuevas técnicas que ampliaron los límites de lo que se creía posible con los autómatas celulares, como los matemáticos llaman redes en evolución como la Vida.

Ahora Karpovich y seis coautores han anunciado en un preimpresión de diciembre que han encontrado los dos últimos períodos faltantes: 19 y 41. Una vez llenados esos espacios, ahora se sabe que la vida es "omniperiódica": nombre un número entero positivo, y existe un patrón que se repite después de tantos pasos.

La floreciente comunidad dedicada al estudio de la vida, que incluye a muchos investigadores matemáticos pero también a muchos aficionados, ha encontrado no sólo osciladores sino todo tipo de patrones nuevos. Han encontrado patrones que viajan a través de la red, denominados naves espaciales, y patrones que construyen otros patrones: armas, constructores y criadores. Encontraron patrones que calculan números primos e incluso patrones que pueden ejecutar algoritmos arbitrariamente complicados.

Los osciladores con períodos inferiores a 15 se pueden encontrar manualmente o con algoritmos rudimentarios que buscan osciladores una celda a la vez. Pero a medida que el período se hace más grande, también lo hace la complejidad, lo que hace que las búsquedas por fuerza bruta sean mucho menos efectivas. “Para períodos pequeños, se puede buscar directamente”, dijo Matthias Merzenich, coautor del nuevo artículo que descubrió el primer oscilador de período 31 en 2010. “Pero realmente no se puede ir más allá de eso. No se puede simplemente elegir un período y buscarlo”. (Merzenich obtuvo su doctorado en matemáticas en la Universidad Estatal de Oregón en 2021, pero actualmente trabaja en una granja).

En 1996, David Buckingham, un consultor informático independiente canadiense y entusiasta de Life que había estado buscando patrones desde finales de los años 1970, demostró que era posible construir osciladores de período 61 y superiores enviando un patrón alrededor de una pista cerrada en un bucle sin fin. . Al controlar la longitud del bucle (y el tiempo que tardaba el patrón en completar un viaje de ida y vuelta), Buckingham descubrió que podía alargar el período tanto como quisiera. "Es química sin olores extraños ni cristales rotos", dijo. "Como construir compuestos y luego explorar las interacciones entre ellos". Esto significaba que, de un solo golpe, había ideado una forma de construir osciladores de períodos arbitrariamente largos, siempre que fueran superiores a 61.

Hubo una gran cantidad de resultados a mediados de la década de 1990, cuando muchos de los osciladores faltantes entre 15 y 61 fueron descubiertos mediante combinaciones creativas de osciladores conocidos, a los que se les había dado una serie de nombres coloridos. Los servicios de catering se combinaron con los semáforos, los volcanes escupieron chispas y los comensales comieron planeadores.

A principios del siglo XXI, sólo quedaban pendientes una docena de períodos. "Parecía muy posible resolver este problema", afirmó Merzenich. En 21, un nuevo descubrimiento llamado bucle de Snark mejoró la técnica de Buckingham de 2013 y redujo el límite por encima del cual era fácil construir osciladores de 1996 a 61. Esto dejó solo cinco períodos faltantes. Se descubrió uno más en 43 y dos más en 2019, dejando solo 2022 y 19, ambos primos. "Los números primos son más difíciles porque no se pueden utilizar osciladores de período pequeño para construirlos", dijo Merzenich.

Mitchell Riley, investigador postdoctoral de la Universidad de Nueva York en Abu Dhabi y otro coautor del nuevo artículo, lleva mucho tiempo intrigado por un tipo de oscilador llamado hassler. "La forma en que funcionan los molestos es que tienes un patrón activo en el medio y algo estable en el exterior que reacciona con él", explicó Riley. El material estable, llamado catalizador, está ahí para devolver el patrón activo a su estado original.

Diseñarlos es difícil. "Todos estos patrones son increíblemente frágiles", dijo Riley. "Si pones un solo punto fuera de lugar, normalmente simplemente explota".

Riley creó un programa llamado Barrister para buscar nuevos catalizadores. “Lo que buscamos son naturalezas muertas que sean robustas. El punto es que queremos que interactúen con lo que está sucediendo en el medio y luego se recuperen”, dijo Riley.

Riley introdujo los catalizadores que Barrister encontró en otro programa de búsqueda que los emparejó con patrones activos. Esto condujo principalmente a fracasos, afirmó. “Es bastante raro que uno de estos catalizadores sobreviva a la interacción. No hay garantía de éxito. Simplemente cruzas los dedos y esperas ganar el premio gordo. Se siente un poco como apostar”.

Al final, su apuesta dio sus frutos. Después de algunos casi accidentes (y una modificación del código que amplió la búsqueda para incluir patrones simétricos), encontró una interacción catalizadora que podría sostener un oscilador de período 19. "La gente había estado intentando todo tipo de búsquedas realmente complicadas con muchos catalizadores y muchas cosas activas raras en el medio, pero todo lo que era necesario era encontrar este nuevo catalizador grueso", dijo Riley.

El último período faltante, 41, fue encontrado por Nicolo Brown, otro coautor, que todavía estudia matemáticas en la Universidad de California, Santa Cruz. Brown utilizó planeadores como catalizadores, una idea propuesta por primera vez por Merzenich.

"Hemos descubierto muchos comportamientos profundos en los últimos 10 años", dijo Karpovich. “Todo el mundo celebra durante una semana y luego pasa a otras cosas. Hay muchos otros problemas que resolver”. ¿Se pueden hacer más pequeños los osciladores de un período determinado? ¿Se pueden encontrar osciladores en los que oscile cada celda? ¿Se pueden fabricar armas con períodos particulares? ¿Se puede hacer que las naves espaciales viajen a velocidades determinadas?

Como dijo Buckingham: "Es como ser un niño en una juguetería infinita".