BusyBeaver(6) es realmente enorme

• El sexto número de Busy Beaver (BB(6)) aumentó recientemente de forma drástica su cota inferior gracias a nueva investigación
• Antes se conocía como BB(6) > 10↑36,534, pero en 2022 se actualizó a BB(6) > 10↑1510
• Más recientemente, en BBchallenge se volvió a elevar a BB(6) > 10↑10,000,00010, y luego se actualizó hasta 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
• El tamaño de BB(6) supera toda imaginación, hasta el punto de que este número bastaría para llenar incontables veces todo el universo
• Estos avances sirven para reconocer de nuevo los límites y el potencial de la lógica matemática y la teoría de la computación

---

Resumen de los resultados recientes de investigación sobre BB(6)

• En los últimos años, la situación del mundo y del entorno de investigación se ha sentido difícil de sobrellevar
• Sin embargo, este avance en la investigación de Busy Beaver sirvió para recordar nuevamente la pasión pura por la investigación
• En 2022, Pavel Kropitz demostró que BB(6) > 10↑1510
  • BB(6) se refiere a cuántos pasos máximos puede ejecutar una máquina de Turing con 6 estados sobre una cinta inicialmente toda en ceros antes de detenerse
  • Aquí, ^1510 es el valor de repetir la exponenciación de 10 sobre sí mismo 15 veces (tetración)
• En investigaciones anteriores se determinó que BB(5) es 47,176,870 (equipo de BBchallenge), y ese es el punto en el que esta cifra se dispara hacia una región que rebasa el rango de la realidad observable

Proceso reciente de actualización de la cota inferior

• "mxdys" de BBchallenge demostró que BB(6) > 10↑10,000,00010
  • Esta prueba se basa en una demostración formal escrita en el lenguaje Coq
• Después, la cota inferior volvió a actualizarse a BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
  • ↑↑ significa tetración (repetición de exponentes), es decir, una forma de tetrar 2 con 2 y luego repetir la tetración 9 veces con ese resultado
  • Un número de este nivel pertenece a una escala que supera cualquier comprensión intuitiva previa
• Como referencia, la pentación significa la repetición de la tetración, y este tipo de operación va más allá de la multiplicación, la potenciación y la tetración

Cómo entender la escala de números tan grandes

• A petición del reportero, fue necesario explicar la magnitud de un número como 10↑10,000,00010
• Esta cantidad bastaría para llenar de arena 10↑10,000,00010 universos
• Con ello se transmite que el valor de BB(6) está inmensamente más allá del mundo realmente observable

Reflexión sobre los límites esenciales del algoritmo BB

• La enorme magnitud de BB(6) muestra el verdadero potencial de la función Busy Beaver
• Se estimaba que el punto en que los valores de BB(n) se vuelven independientes del sistema axiomático de teoría de conjuntos (ZFC) estaría alrededor de n=20~30, pero ahora se puede prever que quizá ya sean independientes incluso para n=7~9
  • Actualmente se sabe oficialmente que es independiente en n=643

Apéndice: noticias recientes de eventos y charlas

• El autor asistió recientemente al evento STOC'2025 celebrado en Praga, donde intercambió ideas con varios investigadores y obtuvo nueva información
• También compartió las diapositivas de su conferencia magistral sobre el estado actual de la aceleración cuántica
• Se prevé compartir más adelante una reseña más detallada sobre este tema

[GN⁺]

Comentarios en Hacker News

• En el servidor de Discord de bbchallenge, alguien compartió a personas especulando cuántos estados de máquina de Turing harían falta para superar el número de Graham. Aunque el reciente ganador de BB(6), 2^^2^^2^^9, ya es un número enorme, les sorprendió que un crecimiento del tipo del de Graham pudiera aparecer antes de lo esperado. Mencionan material sobre el functional busy beaver [1], según el cual bastarían términos lambda de 49 bits, y que solo existen 77,519,927,606 términos lambda cerrados de ese tamaño[2], mientras que en cambio hay nada menos que 399,910,780,272,640 máquinas de Turing de 6 estados[3]. A partir de que la pentación se implementó con solo 6 estados, comentan que ahora bastante gente del área cree que con 7 estados ya podría superarse el número de Graham. Aun así, al autor le sigue pareciendo inesperado. Cuenta que hace unos días hizo una apuesta grande sobre si en los próximos 10 años aparecerá una prueba de que BB(7) supera el número de Graham, y pregunta qué opinan los demás. (con enlaces a 1, 2, 3)
  • No voy a fingir ser experto, pero predeciría que BB(7) será mayor que el número de Graham. BB tiene que crecer más rápido que cualquier sucesión computable arbitraria, así que aunque solo puedo tantear a mano qué tan grande sería realmente BB(7), al final debería crecer más rápido que cualquier operador computable (por ejemplo, up-arrow^n, etc.). Intuyo que el salto de 47,176,870 a 2^^2^^2^^9 es, en intensidad operativa, mucho más dramático que el salto de 2^^2^^2^^9 al número de Graham. El número de Graham es g_64, que también puede interpretarse como un concepto un nivel por encima de up-arrow^n, así que comparto la intuición de que BB(7) superará el número de Graham.
• Expresa que le parece fascinante que un número no computable como BB(748) sea independiente de ZFC (el sistema axiomático de teoría de conjuntos). Dice con honestidad que casi se siente como un error de categoría.
  • La razón por la que BB(748) es independiente de ZFC no es el valor en sí, sino que una de las 748 máquinas de estados, TM_ZFC_INC, se detiene solo si encuentra una contradicción (una prueba de falsedad) en ZFC. Probar que BB(748)=N significa mostrar que TM_ZFC_INC se detiene en N pasos o que corre infinitamente, pero por el teorema de incompletitud de Gödel, si ZFC es consistente entonces eso implica algo que no puede probarse.
  • Le parece aún más sorprendente haber pensado que unas pocas líneas de texto (es decir, los propios axiomas de ZFC) pudieran expresar suficientes verdades aritméticas importantes para los humanos. Que ni siquiera podamos predecir fácilmente el comportamiento de una máquina de Turing de 6 estados le parece lo natural. Lamenta que, tras la publicación del teorema de incompletitud de Gödel, la comunidad matemática no se haya movido mucho más activamente a buscar más axiomas, y que eso haya quedado en la práctica solo para algunas áreas de investigación fundamental.
  • Un buen ejemplo es que el valor de verdad de la hipótesis del continuo (si uno lo ve platónicamente como 1 o 0) está probado como independiente de ZFC. Ni siquiera un solo bit, no ya un número gigantesco, queda garantizado por ZFC.
  • Distingue claramente que BB(n) es no computable, mientras que BB(748), por definición, es la cantidad de unos escritos por una máquina de Turing de 748 estados, así que es un número computable. Explica que la etiqueta de “independiente” significa más bien que para demostrar en ZFC que ese número es realmente el valor que queremos, hace falta una teoría más fuerte.
  • Enfatiza que no es el número en sí lo que es independiente de ZFC, sino el proceso de calcular BB(748). (Todos los enteros pueden expresarse en ZFC).
• Es bien sabido que BB(14) es mayor que el número de Graham, y con esta investigación siente la intuición de que BB(7) también será al menos tan grande como el número de Graham. Intuitivamente, le parece que la idea necesaria para pasar de pentación al número de Graham es incluso más simple que la de pasar de 47,176,870 a 2 <pentate> 5.
  • Buena información; responde que podría ser una excelente respuesta a su publicación.
• Comparte el enlace a la charla de Scott Aaronson en YouTube “How Much Math Is Knowable?” [Harward CMSA] https://www.youtube.com/watch?v=VplMHWSZf5c y a una discusión reciente en HN https://news.ycombinator.com/item?id=43776477
• Señala que el “superíndice en la esquina superior izquierda” es tetración, es decir, exponenciación repetida. Explica que ¹⁵10 significa 10 elevado a 10 elevado a... repetido 15 veces. Comparte que, como nunca lo había visto antes, pensó que era un error tipográfico.
  • Siguiendo con el tema de operaciones repetidas, responde que esta vez conoció por primera vez la “pentación”.
  • Dice que ya había visto la tetración antes, pero que prefiere la notación de up-arrow de Knuth[1] porque es más común y mejor para generalizar (1)
• La explicación de que BB(6) es el número máximo de pasos antes de detenerse de una máquina de Turing de 6 estados y 2 símbolos ({0,1}) sobre una cinta inicial en 0 le resultó muy útil como no especialista. Sintió que este campo está compuesto por una densidad difícil y una terminología especializada para investigadores de décadas, pero le pareció genial haberse topado por casualidad con un texto así de profundo.
  • Piensa que para alguien con nivel de licenciatura en ciencias de la computación, incluso viendo por primera vez el problema del busy beaver, esto es contenido del que se puede captar la idea general. Claro, hay mucho término especializado, pero no hace falta sentir que es algo exclusivo para gente con décadas de experiencia.
  • Aclara que esa definición es estándar más en teoría de la computación que en ingeniería de software.
• Dice que le confundió la explicación de que con “10,000,000 sub10” granos de arena se podría llenar el universo observable 10,000,000 sub10 veces. Señala que lo normal es comparar con la masa del universo observable, y que con ese método ya se está muy por encima de la cantidad real de materia.
  • Le responden que sí. Incluso si se divide entre granos de arena por universo, eso sigue siendo prácticamente del mismo orden de magnitud gigantesco, y números adyacentes (en esta notación) difieren de forma descomunal. Explican que 10↑↑10,000,000 / (granos de arena/universo) sigue siendo muchísimo mayor que 10↑↑9,999,999. Lo comparan con que, en nuestro sistema, (muy grande) / (cósmicamente grande) sigue siendo simplemente (muy grande).
  • Añaden que con tetración ya no se trata de una simple comparación de cantidad de dígitos, sino de un crecimiento del orden de “los dígitos de los dígitos”.
  • Reafirman que este número no se reduce de manera apreciable ni siquiera con unos 10^100000 granos de arena, así que dividirlo no cambia esencialmente nada.
  • Ponen como ejemplo que 10,000,000^10,000,000 ya es absurdamente grande, así que si se añade una cola exponencial más, la comparación deja de tener sentido.
  • Como ejemplo más común, mencionan que en el concepto de cifras significativas no sería una exageración decir que 1,000,000,000 - 1,000,000 = 1,000,000,000.
• Expresa curiosidad por cuál sería el sistema lógico más “rico” cuyas pruebas pudieran enumerarse con una máquina de Turing de 5 estados.
  • La respuesta puede cambiar dependiendo de cómo se defina exactamente “enumerar”. También tiene sentido la pregunta relacionada: “¿Cuál es el sistema lógico más poderoso que no puede demostrar si todas las máquinas de Turing de 5 estados se detienen o no?”. Comparte la opinión personal de que demostrar matemáticamente que Skelet #17 [0] no se detiene es muy difícil, así que si existiera una teoría capaz de probar eso, probablemente también podría decidir el resto de las máquinas de Turing de 5 estados (0, 1)
  • Primero habría que dejar claro el supuesto de cómo interpretar cadenas binarias finitas como enumeraciones de pruebas lógicas para poder discutir la premisa.
• Alguien plantea si el universo observable sería lo bastante grande como para escribir el valor exacto de BB(6).
  • Si se toma el universo observable como un sistema cerrado, al aplicar el límite de Bekenstein la capacidad máxima de almacenamiento de información queda alrededor de 10^120 bits. La estimación actual de la masa-energía total es de aproximadamente 10^53kg, y aun sustituyéndola en la fórmula se obtiene del orden de 10^120 bits. Por lo tanto, no es posible, y lo explican con base numérica.
  • Enfatizan que la cantidad de información almacenable en el universo es de unos 10^120 bits y que, aunque uno se equivocara por muchos órdenes de magnitud, seguiría dando exactamente igual: “obviamente no alcanza”.
  • Suponen que la pregunta asume almacenar todo el valor al mismo tiempo. Si no existiera esa condición de simultaneidad, quizá en teoría podría registrarse a lo largo de un tiempo infinito, aunque habría que considerar límites físicos reales como la muerte térmica del universo. Dicen que en el marco de referencia del CMB no sería posible, pero se preguntan si quizá podría pensarse en otro tipo de corte del espaciotiempo.
  • Desde el primer número del artículo ya es imposible: ¹⁵10, es decir, algo de la forma 10^(¹⁴10), así que solo la cantidad de dígitos ya es ¹⁴10.
  • Reconfirman brevemente que no se puede.
• Cada vez que ve resultados así en teoría de la complejidad computacional, siente que el discurso popular del tipo “la superinteligencia artificial es dios” carece totalmente de fundamento. Aunque convirtiéramos todos los átomos del universo en una supercomputadora y usáramos incluso la energía de un agujero negro, seguiría siendo imposible para siempre calcular el estado de detención de BB(6).
  • Respuesta breve: ese tipo de argumento de hombre de paja ya nunca fue convincente.