Con el quinto Busy Beaver, investigadores se acercan a los límites de la computación

• Introducción

  • Hace 40 años, científicos de la computación se reunieron en Dortmund, Alemania, para competir por encontrar el quinto Busy Beaver
  • Un Busy Beaver es un programa de computadora simple cuyo tiempo de ejecución se vuelve extremadamente largo
  • Estos programas están relacionados con famosos problemas matemáticos no resueltos y se originan en un viejo problema de la informática
  • Hace dos años, el estudiante de posgrado Tristan Stérin inició el Busy Beaver Challenge, y más de 20 colaboradores de todo el mundo han participado
  • Hoy, el equipo confirmó que el valor de BB(5) es 47,176,870

• Detenerse o no detenerse

  • Los programas Busy Beaver están escritos como instrucciones para una computadora teórica llamada máquina de Turing
  • Una máquina de Turing realiza cálculos leyendo y escribiendo 0 y 1 en una cinta infinita
  • El problema de predecir si una máquina de Turing se detendrá o seguirá ejecutándose para siempre se llama problema de la detención
  • El problema de la detención no tiene una solución general, lo que hace que la caza del Busy Beaver sea aún más atractiva

• La aparición del castor

  • El matemático Tibor Radó inventó el juego del Busy Beaver en 1962
  • A la máquina de Turing que corre durante más tiempo dentro de cada conjunto de reglas se le llama Busy Beaver
  • BB(n) representa la cantidad de pasos que toma una máquina Busy Beaver con n reglas antes de detenerse

• La manada de castores de Brady

  • Allen Brady desarrolló técnicas para cazar Busy Beavers en la década de 1960 y determinó el valor del cuarto Busy Beaver en 1974
  • Se confirmó que BB(4) es una máquina que se detiene después de 107 pasos

• El quinto castor

  • En la competencia de Dortmund de 1984 comenzó la primera gran cacería para encontrar el quinto Busy Beaver
  • En 1989, Heiner Marxen descubrió una máquina que se detiene después de 47,176,870 pasos
  • En 2003, Georgi Georgiev abandonó la búsqueda de BB(5) dejando 43 máquinas de Turing sin resolver

• Llamado a todos los cazadores

  • Tristan Stérin inició el Busy Beaver Challenge en 2022, con la participación de colaboradores de todo el mundo
  • Shawn Ligocki se unió al equipo en 2022 e hizo contribuciones importantes
  • Justin Blanchard desarrolló el método de lenguaje de cinta cerrada, una de las técnicas más potentes del equipo

• Acercándose al monstruo

  • Skelet #1 y #17 eran máquinas particularmente difíciles, y el equipo combinó varias ideas para resolverlas
  • En mayo de 2023, un colaborador anónimo llamado mxdys completó una demostración en Coq

• Donde deambulan los castores

  • El equipo está escribiendo un artículo académico formal, y algunos ya están intentando encontrar el siguiente castor
  • BB(6) parece difícil de resolver debido a un problema similar a la conjetura de Collatz

La opinión de GN⁺

• Este artículo ofrece un caso interesante para explorar los límites de la informática
• El Busy Beaver Challenge muestra la importancia de la investigación colaborativa
• La resolución de BB(5) tiene un gran significado para las comunidades de informática y matemáticas
• Un proyecto con características similares es la investigación sobre la conjetura de Collatz
• Al adoptar nuevas tecnologías u open source, la colaboración y la reproducibilidad son importantes

[GN⁺]

Comentarios en Hacker News

• Se compartieron comentarios sobre una publicación del blog de Scott Aaronson

  • Se proporciona un enlace a un hilo anterior relacionado

• Existen varias variantes del problema de Busy Beaver

  • Hay una variante que usa cálculo lambda
  • Hay una variante expresada mediante complejidad de Kolmogorov

• Se compartió la historia de un ingeniero que dejó su trabajo para estudiar el problema de Busy Beaver

  • Se preguntan si ese ingeniero es mxdys

• Hay una mención de una prueba en Coq

  • Se plantea la posibilidad de que no sea una prueba organizada desde el principio, sino la primera prueba organizada

• Hay una opinión de que el artículo original de Tibor Radó sobre Busy Beaver es fácil de leer y entretenido

  • Se proporciona un enlace a una versión moderna del artículo

• Se resolvió el problema de parada para programas de máquinas de Turing de 5 estados y 2 colores

  • Se plantea si podría aplicarse al caso de 2 estados y 4 colores

• Se menciona la idea equivocada de que los humanos pueden resolver intuitivamente el problema de parada

• Se compartió la experiencia de haber escrito un programa en un proyecto personal para resolver el problema de Cutting Stock

  • Usa un método de optimización similar al programa de Brady

• Hay una opinión de que fue cuestión de suerte haber podido demostrar si los programas de máquinas de Turing de 5 estados se detienen o no

• Según una publicación del blog de Scott Aaronson, existen 16,679,880,978,201 máquinas de Turing de 5 estados

  • Se preguntan qué porcentaje de ellas se detiene

• Se compartieron los valores de la función Busy Beaver

  • Se demostró que BB(5) es 47,176,870
  • BB(6) es al menos 10^10^...^10 (una torre exponencial de 15 niveles)