Descubierto un glider de 1D en el Juego de la Vida de Conway de 3.7 mil millones de celdas

• En el foro de Conway’s Game of Life (Juego de la Vida de Conway) se completó un patrón de nave espacial 1D (1D spaceship) de aproximadamente 3.7 mil millones de celdas (3.7B).
• Este patrón se desplaza con una velocidad de 133,076,755,768 generaciones y su caja delimitadora inicial es de 3707300605×1 celdas.
• Los desarrolladores combinaron cuatro sistemas de construcción: ECCA1·ECCA2 compressed construction arm, binary arm, fuse arm, para implementar procesos de autorreplicación, limpieza y reinicio.
• La simulación se verificó en entornos Golly y lifelib, y apg (calcyman) agregó al repositorio el código de validación del ciclo completo.
• Este hallazgo se considera un ejemplo del avance de la técnica de slow salvo y de las herramientas de automatización para patrones gigantescos.

---

Informe de finalización de la nave espacial 1D

• Hippo.69 anunció que se había completado una nave espacial de velocidad “2c/133076755768”, lo que equivale a dos celdas de movimiento por ciclo.
  • El rango de la coordenada y es de aproximadamente ±5,537,521,000 y la coordenada x máxima es de aproximadamente 11,075,626,500.
• apg (calcyman) confirmó con simulación completa que el patrón funcionaba correctamente y corrigió un error de tipeo en el valor del período.
• El resultado final se compartió en varios archivos .mc (example.mc, example_42168M.mc, example_46000M.mc) para poder reproducirlo de forma incremental en Golly.

Simulación y depuración

• Durante la depuración inicial se detectó un problema en el que una Cordership generaba un glider inverso que causaba daño de SoD (Stop of Destruction).
• Se ajustó el “switch far seed” para tener en cuenta ese glider.
• La simulación avanzó rápidamente por bloques de decenas de millones de generaciones usando la optimización Hashlife de lifelib.
• Un script de Lua basado en BigNum automatizó saltos masivos de generaciones en Golly y guardó puntos de control en eventos clave (por ejemplo, inicio de ecca2, llegada de la cordership, etc.).

Estructura y principio de funcionamiento

• El sistema completo está compuesto por cuatro brazos de construcción.
  • Fuse arm: creación e inicialización de señales unidimensionales basadas en blinker.
  • Binary arm: interpreta señales binarias combinando dos gliders para construir estructuras.
  • ECCA1 / ECCA2: brazos de construcción ultradensos que interpretan instrucciones comprimidas para limpiar el patrón y preparar la siguiente generación.
• ECCA2 lanza una flota de cordership (corderfleet) en la etapa final para eliminar patrones residuales y, finalmente, regresar al estado unidimensional (y = 0).
• Todo el proceso fue diseñado con simetría total, con ambos lados funcionando de forma idéntica respecto al eje central (spine).

Desarrollo y colaboración

• El proyecto se completó con la colaboración de calcyman (apg) y Hippo.69.
  • calcyman diseñó la mitad inicial (estructura de brazos y base de código).
  • Hippo.69 realizó durante los años siguientes las tareas restantes de limpieza, sincronización y depuración.
• Usuarios del foro propusieron los nombres “Arrow 1” o “Unidimensional Spaceship 1”.
• Miembros de la comunidad como hth3 e I6_I6, entre otros, intentaron simular en Golly y dejaron mensajes de felicitación.

Relevancia técnica

• Esta nave espacial es el primer patrón auto-replicante de gran escala que se mueve unidimensionalmente, demostrando un nuevo nivel de complejidad computacional dentro del Juego de la Vida.
• Se emplearon tecnologías recientes como la automatización de slow salvo, el decodificador comprimido ECCA y el control de Cordership.
• Los investigadores tienen previsto realizar optimizaciones adicionales para reducir el tamaño y mejorar la velocidad en el futuro, y están evaluando una publicación relacionada.

[GN⁺]

Comentarios en Hacker News

• Al principio empecé a leer pensando “oh, qué interesante”, pero no imaginaba que hubiera tanta jerga especializada en la comunidad de Game of Life
  Empezaron a aparecer términos como ECCA1 y gpse90 por todos lados, y al final siento que tendría que leer el wiki durante horas

  • El libro gratuito Conway’s Game of Life: Mathematics and Construction es bueno para empezar
  • Entro a ese foro más o menos una vez al año, y siempre me sorprende cuánta gente le dedica una cantidad enorme de tiempo y cerebro
  • En realidad, esto no es tanto “jerga de Game of Life” como terminología matemática del campo de los cellular automata

• Sorprende que empiece como una línea simple, luego explote en una estructura compleja gigante en 2D y, después de muchísimas generaciones, vuelva a convertirse en una línea de 3.7B celdas de largo
  Ojalá alguien analizara las unidades de abstracción que hay dentro de esto

  • Según esta publicación del foro, en realidad es una estructura dispersa con menos de 1/100 de celdas vivas en comparación con la longitud de la línea (Unidimensional spaceship 1)
  • Gracias a la explicación ya lo entendí. Al principio pensé que era un glider de un autómata celular unidimensional

• Leer las explicaciones largas del foro de GoL se siente como experimentar lo que siente mi pareja cuando escucha mis reuniones de trabajo por Zoom. Esta lluvia de jerga especializada está buenísima

  • Me hizo pensar en este video
  • Me parece una comparación mucho más divertida de lo que indica el karma que recibió este comentario
  • La única diferencia es que, aunque yo no entienda nada, igual la estoy pasando bien. A mi pareja solo le importa mi estado de ánimo: “¿así que esa arquitectura RISC no cumple con ADA-1056? ¡Wow, qué increíble, amor!”

• “¡Dios mío, esto es un Quine!”
  Cuando una secuencia lineal de bits se interpreta como un tablero de Game of Life, resulta ser una estructura que se duplica a sí misma desplazada dos píxeles a la derecha
  Eso es más difícil que una simple replicación, pero es hermosa la interpretación de verlo como un autorreplicador tipo cinta que imprime su propio código dos píxeles más allá

  • En realidad, este tipo de estructura se llama “spaceship”. Es una de las 2 spaceship descubiertas ese mismo día. Pero esta es la primera 1D spaceship
  • De hecho, moverse es más fácil que autorreplicarse. Todavía no se ha descubierto un verdadero replicator, aunque sí hay millones de spaceship

• Había un comentario de “como el comienzo es lento, salta a la generación 42168M”, y eso me hizo imaginar a seres que juegan con el universo como si fuera un juguete diciendo “se pone interesante como por los 13.8B años”

  • Filosóficamente, la realidad también podría ser una simulación compleja de GoL. Si estuviéramos dentro de una simulación, me pregunto si podríamos reconocerlo

• Hay dos preguntas abiertas interesantes sobre Game of Life

  1. ¿Cuál es el comportamiento a partir de un estado inicial aleatorio? Como es Turing-complete, quizá incluso podrían surgir formas de vida inteligentes. ¿Dominaría el caos, o aparecería la inteligencia? (discusión relacionada)
  2. ¿Existe alguna estructura superestable (superstable) que se mantenga ante cualquier interferencia externa? (pregunta relacionada)
  • La primera pregunta se trata en The Recursive Universe (1984) de William Poundstone. Ese libro toma a las máquinas autorreplicantes como definición de vida, y más tarde Gemini, creado por Andrew J. Wade en 2010, fue el primer caso exitoso que cumplió con esa definición.
    La probabilidad de que surja vida a partir de un estado inicial aleatorio es casi cero, pero la vida sí tiene potencial evolutivo
  • Es Turing-complete, sí, pero el cálculo real es difícil, y los patrones tienden al caos o a la extinción. Para mover información se necesitan estructuras complejas como spaceship. En cambio, variantes como Lenia o Neural CA son más estables
  • Las configuraciones aleatorias están llenas de ruido homogéneo con densidad del 50%, así que rara vez generan estructuras interesantes. Hay que empezar con ruido libre de escala para que aparezca estructura global
  • Que sea Turing-complete no garantiza inteligencia, pero en un plano infinito eventualmente podría surgir una forma de vida inteligente y llenar todo. Aunque si aparecen varias, también podrían entrar en competencia de extinción entre sí
  • Si sigues agregando puntos al azar sobre un plano infinito, tarde o temprano aparecerá una forma de vida inteligente que convierta energía de baja entropía en alta entropía

• Hace tiempo hice un experimento de glider con movimiento continuo — glider.gif

  • Es realmente hermoso. Parece una obra de arte que representa visualmente las reglas básicas

• Me preguntaba si había una visualización del glider. Quería verlo usando el eje temporal como una dimensión

  • Según entiendo, esto solo empieza en 2D GoL como una línea de 1x3.7B celdas
  • Para ejecutarlo, el software Golly es lo mejor. Gracias al algoritmo HashLife, se puede simular rápido
  • Después del primer paso ya deja de ser 1D, así que esa visualización no sería posible

• Es una estructura que solo en cierta etapa cabe dentro de una caja de 1 celda de alto

  • No soy un GoLtician, pero bajo las reglas estándar parecería imposible algo así salvo que quede estático o se extinga.
    Aun así, de verdad impresiona la pasión y dedicación que hay en este hilo

• En 1995 una vez recibí un correo de alguien llamado John Conway. En ese momento fue solo por una publicación que hice en un grupo de noticias de matemáticas, y recién después me di cuenta de que era Conway
  Ahora, al ver este increíble mundo de GoL, me hace pensar en para qué debería usar la humanidad este tipo de potencial creativo