BusyBeaver(6) es realmente enorme

 (scottaaronson.blog)
2 puntos por GN⁺ 2025-06-29 | 1 comentarios | Compartir por WhatsApp
  • El límite inferior conocido de BB(6) volvió a subir de forma drástica, confirmando que el tiempo máximo de detención de una máquina de Turing de 6 estados es un número que supera por mucho la escala de la realidad observable
  • BB(6) se refiere al número máximo de pasos que una máquina de Turing de 6 estados y 2 símbolos, iniciada con una cinta llena de 0, puede ejecutar antes de detenerse
  • Tras la mejora de Pavel Kropitz en 2022, mxdys volvió a elevar el límite inferior a un nivel mayor que 10 tetrado 10 millones de veces
  • El resultado más reciente muestra que BB(6) es al menos 2 pentado a 5, introduciendo una operación un nivel por encima de la potenciación iterada
  • BB(5) fue determinado como 47,176,870, pero BB(6) crece de manera abrumadora, lo que lleva a conjeturar que el punto donde BB(n) se vuelve independiente de los axiomas ZFC podría estar en n=7, 8 o 9

El límite inferior de BB(6) vuelve a crecer

  • Antes de 2022, sobre BB(6) solo se sabía aproximadamente que BB(6) > 10^36,534, y Pavel Kropitz lo mejoró a un nivel mayor que 10 tetrado 15 veces
  • La tetración (tetration) significa potenciación iterada
    • Por ejemplo, apilar 10 quince veces da un número de la forma 10 elevado a 10 elevado a 10 elevado a …, continuado 15 veces
  • Tristan Sterin, organizador de BBchallenge, informó que el miembro del equipo mxdys volvió a elevar el límite inferior de BB(6)
  • Una mejora posterior de mxdys muestra que BB(6) es al menos 2 tetrado a 2 tetrado a 2 tetrado a 9
    • En particular, BB(6) es al menos 2 pentado a 5
    • La pentación (pentation) es tetración iterada, una operación un nivel por encima de la tetración, que a su vez itera la potenciación

La diferencia extrema entre BB(5) y BB(6)

  • BB(6) es el sexto número Busy Beaver
    • Se aplica a máquinas de Turing de 6 estados
    • El alfabeto es {0,1}
    • La cinta de entrada empieza completamente en 0
    • Significa el número máximo de pasos de ejecución posibles antes de detenerse
  • El equipo internacional BBchallenge determinó el año pasado que BB(5) es 47,176,870
  • Al pasar de BB(5) a BB(6), la función Busy Beaver salta desde la escala de decenas de millones hasta un tamaño que supera el rango de la realidad observable

Un número para el que casi no sirve la intuición de escala

  • Incluso cuando se sabía que BB(6) > 10 tetrado 10 millones de veces, era casi imposible explicarlo de forma intuitiva
  • Por ejemplo, se lo comparó diciendo que, si hubiera esa cantidad de granos de arena, podrían llenarse aproximadamente esa misma cantidad de copias del universo observable
  • La comparación muestra que, como ese número es abrumadoramente mayor incluso que cifras de escala cósmica como 10^100, al dividirlo sigue quedando una cantidad de prácticamente la misma escala que el número original

Posibilidad de que baje la estimación sobre la independencia de ZFC

  • Que BB(6) haya crecido tanto no significa que haya cambiado todo lo que se piensa sobre la función Busy Beaver
  • Ya estaba abierta la posibilidad de que BB(6) no estuviera en un nivel relativamente pequeño como 10^36,534, sino en el ámbito de las operaciones iteradas
  • Al confirmarse que el límite inferior real está en esa escala, podría bajar la estimación sobre el punto en que el valor de BB(n) se vuelve independiente de los axiomas de la teoría de conjuntos ZFC
    • Antes podía pensarse en algo cerca de n=20 o 30
    • Ahora se considera que podría ser n=7, 8 o 9
  • El resultado de independencia de ZFC conocido actualmente está en el nivel de que BB(n) se vuelve independiente de ZFC para n=643

Actualización aparte: STOC 2025

  • En Prague, donde se celebró STOC 2025, se reunió con varios investigadores y conoció nuevos contenidos
  • El título de la plenary lecture de STOC fue The Status of Quantum Speedups
  • Los lectores interesados pueden consultar las diapositivas de PowerPoint de esa charla

Lecturas relacionadas

1 comentarios

 
GN⁺ 2025-06-29
Opiniones de Hacker News

  • En el servidor de Discord de bbchallenge están especulando activamente cuántos estados de una máquina de Turing harían falta para superar el Número de Graham, que es muchísimo más grande que 2^^2^^2^^9, alcanzado por el campeón más reciente de BB(6).
    Si se mira el functional busy beaver https://oeis.org/A333479, un comportamiento del nivel de Graham podría aparecer sorprendentemente rápido. Bastaría con un término lambda de 49 bits.
    Por debajo de ese tamaño solo hay 77,519,927,606 términos lambda cerrados https://oeis.org/A114852, mientras que hay 4^12*23836540=399910780272640 máquinas de Turing únicas de 6 estados https://oeis.org/A107668.
    Como con solo 6 estados ya se logró pentación, ahora varias personas creen que con 7 estados se podría superar el Número de Graham. Aun así, a mí me sigue pareciendo bastante sorprendente. Hace unos días hice una apuesta grande con una de esas personas sobre si en los próximos 10 años aparecerá una demostración de BB(7)>Graham's, y tengo curiosidad por saber qué opinan los demás.

    • No puedo fingir ser experto, pero BB(7) probablemente sea mayor que el Número de Graham.
      BB tiene que crecer más rápido que cualquier sucesión computable. Lo que eso significa concretamente para BB(7) termina siendo más bien una explicación a grandes rasgos, pero da la sensación de que tiene que subir muy rápido por la escalera de la potencia de los operadores. En última instancia, debe crecer más rápido que cualquier operador computable que definamos, incluidos, por ejemplo, up-arrow^n o up-arrow^f(n) para una función computable f.
      Intuitivamente, el crecimiento de 47 million a 2^^2^^2^^9 parece cualitativamente mayor, en términos de la potencia de operadores necesaria, que el crecimiento de 2^^2^^2^^9 al Número de Graham. El Número de Graham es g_64, donde g está aproximadamente un nivel por encima de up_arrow^n, así que probablemente BB(7)>Graham's Number.

  • Me marea pensar que un número como BB(748), y encima uno no computable, pueda ser “independiente de ZFC”. Se siente como una especie de error de categoría.

    • Lo que hace que BB(748) sea independiente de ZFC no es el valor en sí, sino que una de las máquinas de 748 estados, TM_ZFC_INC, está diseñada para buscar una contradicción dentro de ZFC, es decir, una prueba de FALSE, y detenerse solo si la encuentra.
      Por lo tanto, una demostración de BB(748)=N tendría que mostrar que TM_ZF_INC se detiene en N pasos, o que nunca se detiene. Suponiendo que ZFC es consistente, por el famoso resultado de Gödel ambas cosas son imposibles.
    • Lo no computable es BB(n). Es decir, no existe un algoritmo que, para un n arbitrario, produzca el valor de BB(n).
      BB(748) sí es computable. Por definición, es la cantidad de unos que escribe alguna máquina de Turing con 748 estados, y esa máquina calcula BB(748).
      El número en sí es simplemente un entero literalmente inimaginablemente grande. La independencia de ZFC entra cuando intentamos demostrar que ese número es el que buscamos. Para eso hace falta una teoría más fuerte que ZFC, capaz de capturar las propiedades de una máquina de Turing de 748 estados.
    • Más bien, lo más sorprendente es haber pensado que un texto tan corto como los axiomas de ZFC, que caben holgadamente en una servilleta, sería “suficiente” para capturar la verdad aritmética o los aspectos de la realidad física más relacionados con la actividad humana.
      No sorprende en absoluto que el comportamiento de una máquina de Turing de 6 estados pueda ser impredecible a partir de unas pocas líneas de texto.
      Habría pensado que, apenas Gödel publicó el primer teorema de incompletitud, toda la comunidad matemática habría corrido a toda velocidad a buscar más axiomas. Pero durante casi un siglo, el trabajo de Gödel se ha tratado más como un hecho curioso en un rincón estrecho de los fundamentos que como un programa central. Conozco a Feferman, Friedman y otros, pero la investigación en esta área es mucho menor que en la mayoría de los demás temas de las matemáticas.
    • El número en sí no es independiente de ZFC. Todos los enteros son representables en ZFC. Lo que es independiente de ZFC es el proceso de calcular BB(748).
    • Los números individuales en sí no son no computables. No existe ningún par formado por algún número y una demostración en ZFC que pruebe que ese número es el valor de BB(748).
      Por lo tanto, tampoco existe un programa que ZFC pueda demostrar que produce el valor de BB(748). Pero, como con cualquier otro número, sí existe un programa que produce BB(748).

  • Se sabe que BB(14) es mayor que el Número de Graham, pero viendo este resultado, parece probable que BB(7) también sea mayor que el Número de Graham.
    Intuitivamente, la técnica necesaria para pasar de la pentación al Número de Graham se siente más simple que la necesaria para pasar de 47,176,870 a 2 5.

  • Al ver la explicación de que superíndice izquierdo significa tetración, es decir, exponenciación repetida, al principio pensé que era un error tipográfico. Es la primera vez que me topo con la tetración.

    • Ya la había visto antes, pero en ese momento usaban la notación de flechas hacia arriba de Knuth, que me gusta porque se generaliza fácilmente https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation.
    • Siguiendo la idea de la repetición, esta vez es la primera vez que me topo con la pentación.

  • No entiendo la parte que dice: “Imagina que hay 10,000,000sub10 granos de arena. Entonces podrías llenar con esa arena alrededor de 10,000,000sub10 universos observables”
    ¿De verdad están redondeando hasta eliminar el valor de dividir el volumen del universo observable entre el volumen promedio de un grano de arena? Eso es una diferencia de muchísimos más dígitos que la masa total del universo, que suele usarse en comparaciones.

    • Sí. Dividir por esa proporción, en esta notación, prácticamente no tiene efecto, porque los números “adyacentes” producen cambios muchísimo mayores.
      10↑↑10,000,000 / (cantidad de granos de arena por universo) sigue siendo abrumadoramente mayor, por ejemplo, que 10↑↑9,999,999.
      En un sistema que usa números así, casi no hay una forma mejor de expresar (un número gigantesco)/(un número que apenas está a escala cósmica) que escribirlo exactamente así; en la notación del número gigantesco, al final se redondea casi a (un número gigantesco).
    • Con la tetración ya no estás tratando con órdenes de magnitud de dígitos, sino con órdenes de magnitud de órdenes de magnitud de dígitos.
    • Un ejemplo más común de este tipo de comparación: en cifras significativas, si a mil millones le restas un millón, sigue siendo mil millones.
    • Exacto. Este número es tan inmensamente mayor que cantidades como 10^100000 o cuántos granos de arena caben, que dividirlo por algo de ese tamaño prácticamente no lo cambia. Al menos no baja lo suficiente como para acercarse a 9,999,999sub10.
    • Sí. Eso es apenas una diferencia de dígitos equivalente a un número ordinario. Incluso 10,000,000^10,000,000 ya es tan grande que esa diferencia deja de importar; mucho más después de elevar el exponente mismo nueve veces más.

  • How Much Math Is Knowable? de Scott Aaronson [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
    También apareció en HN hace unos meses: https://news.ycombinator.com/item?id=43776477

  • ¿Cuál es la lógica más rica con la que se pueden enumerar demostraciones usando solo una máquina de Turing de 5 estados?

    • Esa pregunta depende de qué se considere enumeración, pero hay una pregunta relacionada: “¿Cuál es la lógica más rica que no puede demostrar si todas las máquinas de Turing de 5 estados se detienen?”. Es decir, pregunta cuál es la lógica más rica para la cual la detención de alguna máquina de Turing de 5 estados sea independiente.
      Pensé un poco en esta versión, pero no llegué muy lejos porque me falta experiencia en lógica de primer orden. Hasta donde sé, Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA es una de las máquinas cuya no detención es más difícil de demostrar matemáticamente https://arxiv.org/abs/2407.02426, así que si una teoría puede demostrar que Skelet #17 no se detiene, probablemente también pueda decidir el resto de las máquinas de 5 estados.
    • Depende por completo de cómo interpretes una cadena binaria finita como enumeración de demostraciones lógicas.

  • Al leer la explicación de que “BB(6) es el sexto número Busy Beaver, es decir, el máximo número de pasos que puede dar una máquina de Turing de 6 estados con alfabeto {0,1} antes de detenerse cuando se ejecuta sobre una cinta inicialmente llena de 0”, sentí que, para alguien no experto como yo, en realidad se entendía demasiado bien.
    Claramente este es un blog hardcore para gente que lleva décadas trabajando en este tema. Es bastante genial encontrarse por casualidad con un texto escrito sin pudor para un público específico, denso y lleno de terminología técnica.

    • Para alguien con formación universitaria en ciencias de la computación, la explicación alcanza para hacerse una idea general de lo que está pasando aunque sea la primera vez que se topa con el problema Busy Beaver.
      Es cierto que es terminología de nicho, pero pensar que solo es accesible para quienes le han dedicado décadas es subestimarse.
    • Esa definición es material estándar de grado en teoría de la computación. Eso sí, puede que no sea estándar en ingeniería de software.

  • Un número tan grande no se puede visualizar humanamente. Contar no es la única forma de representar números.
    Por ejemplo, se puede considerar que un solo grano de arena tiene infinitos estados posibles. Como hay infinitos números reales, también se podría decir que un solo grano de arena puede representar BB(6). Las combinaciones pueden crecer exponencialmente, así que quizá ese tipo de enfoque sea útil para la representación.

    • A partir de cierto punto, los números grandes dejan de ser una “gran cantidad” y se parecen mucho más a la fuerza de consistencia de un sistema formal.
      Es decir, se trata de cuánto tiempo puede un sistema fingir que no es contradictorio antes de ser descubierto. Un sistema contradictorio que finge consistencia mediante BB(3) queda “al descubierto” mucho antes que uno que finge consistencia mediante BB(6). Aquí, fingir consistencia significa afirmar que todo programa que se ejecute por más de BB(n) pasos, para algún n, no se detiene.
    • Si el universo se redondeara a la unidad de Planck más cercana, de pronto un grano de arena no tendría tantos estados posibles.
      Para mí, traer precisión infinita para que parezca manejable se parece más a un truco de manos. Para explicar escalas, es mejor usar enteros.
    • Este ejemplo confunde. Si la cantidad de granos de arena y la cantidad de universos observables son iguales, ¿no significa eso que hay un grano de arena por universo?

  • Me pregunto si el universo observable es lo suficientemente grande como para escribir el valor exacto de BB(6)

    • Si consideramos el universo observable como un sistema cerrado, se podría aplicar el límite de Bekenstein
      Se usa R ≈ 46.5 billion light-years, es decir, el radio del universo observable, y E ≈ el contenido total de masa-energía del universo observable
      La masa-energía incluye materia ordinaria, materia oscura y energía oscura. Según las estimaciones actuales, el universo observable tiene aproximadamente un equivalente de masa-energía de 10^53 kg
      Al poner esto en S ≤ 2πER/ℏc, la cantidad máxima de información resulta estar aproximadamente en el orden de 10^120 bits
      S ≤ 2πER/ℏc
      S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)
      S ≤ 2.654135e+124
      S ≤ 10^120
      Así que es imposible
    • Definitivamente no es suficiente. La cantidad de información que se puede almacenar en el universo es de aproximadamente 10^120 bits. Incluso si me equivocara por un billón de dígitos, el resultado no cambiaría
    • En el artículo, solo el número inicial ya es ¹⁵10. Eso significa 10^(¹⁴10), por lo tanto tiene ¹⁴10 dígitos. Así que no se puede escribir
    • Probablemente se refiere a que todas las partes de la expresión completa existan al mismo tiempo. Si no tienen que existir simultáneamente, quizá sea posible “escribirlo” si la duración del universo es infinita. No sé cómo influye aquí la muerte térmica, así que digo “quizá”
      Pero en el espacio-tiempo relativista, “simultáneamente” no está bien definido. Los comentarios hermanos tienen razón con seguridad en el marco de referencia que sugiere la radiación de fondo de microondas. Aun así, me pregunto si en algún marco de referencia podría haber una forma de cortar el espacio-tiempo que permita que la expresión exista “simultáneamente”