BusyBeaver(6) est vraiment énorme

• La 6e valeur du Busy Beaver (BB(6)) a récemment vu sa borne inférieure fortement augmenter grâce à de nouvelles recherches
• On connaissait auparavant BB(6) > 10↑36,534, puis cette borne a été relevée en 2022 à BB(6) > 10↑1510
• Plus récemment, dans le cadre de BBchallenge, BB(6) > 10↑10,000,00010 a de nouveau été établi, puis encore mis à jour jusqu’à 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
• La taille de BB(6) dépasse l’imagination, à un point tel que ce nombre pourrait remplir l’univers entier d’innombrables fois
• Ces avancées amènent à reconnaître sous un nouveau jour les limites et le potentiel de la logique mathématique et de la théorie de la calculabilité

---

Aperçu des récents résultats de recherche sur BB(6)

• Ces dernières années, le monde et l’environnement de recherche ont souvent semblé éprouvants
• Pourtant, les progrès récents de la recherche sur Busy Beaver ont ravivé une passion pure pour la recherche
• En 2022, Pavel Kropitz a démontré que BB(6) > 10↑1510
  • BB(6) désigne le nombre maximal d’étapes qu’une machine de Turing à 6 états peut exécuter sur un ruban entièrement nul avant de s’arrêter
  • Ici, ^1510 désigne la tétration de 10 à lui-même répétée 15 fois
• Des recherches antérieures avaient établi que BB(5) vaut 47,176,870 (équipe BBchallenge), ce qui marque le point où ces valeurs augmentent brutalement au-delà du domaine de la réalité observable

Processus récent de mise à jour de la borne inférieure

• « mxdys » de BBchallenge a démontré que BB(6) > 10↑10,000,00010
  • Cette preuve repose sur une preuve formelle écrite dans le langage Coq
• Par la suite, la borne inférieure a encore été mise à jour en BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
  • ↑↑ désigne la tétration (répétition de l’exponentiation) ; il s’agit ici de tétrer 2 par 2, puis de réappliquer cette opération au résultat, en répétant le processus 9 fois
  • On entre alors dans un domaine qui dépasse toute compréhension intuitive antérieure
• À titre de repère, la pentation désigne la répétition de la tétration ; c’est une opération qui va au-delà de la multiplication, de l’exponentiation et de la tétration

Comprendre l’échelle de ces grands nombres

• À la demande d’un journaliste, il a fallu expliquer l’ampleur du nombre 10↑10,000,00010
• Ce nombre de grains de sable suffirait à remplir de sable 10↑10,000,00010 univers
• Cela montre à quel point la valeur de BB(6) dépasse de très loin le monde réellement observable

Réflexion sur les limites fondamentales de l’algorithme BB

• L’énormité de la valeur de BB(6) montre le véritable potentiel de la fonction Busy Beaver
• On estimait que le point où les valeurs de BB(n) deviennent indépendantes du système axiomatique de la théorie des ensembles (ZFC) se situait autour de n=20~30, mais cela conduit désormais à penser qu’une telle indépendance pourrait déjà apparaître dès n=7~9
  • À l’heure actuelle, on sait officiellement que cette indépendance est établie pour n=643

Annexe : nouvelles récentes sur événements et conférences

• L’auteur a récemment assisté à STOC'2025 à Prague, où il a échangé avec divers chercheurs et obtenu de nouvelles informations
• Il a également partagé les diapositives de sa conférence plénière sur l’état actuel de l’accélération quantique
• Un compte rendu plus détaillé sur ce sujet sera partagé ultérieurement

[GN⁺]

Commentaires sur Hacker News

• Sur le serveur Discord de bbchallenge, quelqu’un a partagé des spéculations sur le nombre d’états de machine de Turing nécessaires pour dépasser le nombre de Graham. Le récent champion BB(6), avec son 2^^2^^2^^9, est déjà un nombre gigantesque, mais il est surprenant de voir à quel point une croissance de type Graham pourrait apparaître plus tôt qu’on ne l’imaginait. Il est mentionné qu’une ressource sur le functional busy beaver [1] suggère qu’un terme lambda de 49 bits suffit, qu’il n’existe que 77519927606 termes lambda clos de cette taille [2], alors qu’il existe pas moins de 399910780272640 machines de Turing à 6 états [3]. Depuis que la pentation a été implémentée avec seulement 6 états, beaucoup semblent désormais penser qu’avec 7 états, on pourrait aussi dépasser le nombre de Graham. L’auteur dit malgré tout trouver cela encore contre-intuitif. Il explique avoir récemment pris un pari important sur l’apparition, dans les dix prochaines années, d’une preuve que BB(7) dépasse le nombre de Graham, et demande l’avis des autres. (1, 2, 3)
  • Sans prétendre être expert, quelqu’un prédit que BB(7) sera plus grand que le nombre de Graham. BB doit croître plus vite que toute suite calculable arbitraire, donc même si l’on ne peut qu’esquisser à la main la taille réelle de BB(7), la direction générale est qu’il doit finir par dépasser toute famille d’opérateurs calculables, comme up-arrow^n. L’intuition est que le saut de 47176870 à 2^^2^^2^^9 est, en intensité d’opérateur, bien plus spectaculaire que celui de 2^^2^^2^^9 au nombre de Graham. Comme le nombre de Graham est g_64, ce qui peut aussi se comprendre comme un concept un niveau au-dessus de up-arrow^n, la personne partage son intuition que BB(7) le dépassera.
• Quelqu’un dit trouver fascinant que des nombres non calculables comme BB(748) puissent être indépendants de ZFC (le système d’axiomes de la théorie des ensembles). Cela lui donne honnêtement l’impression d’une erreur de catégorie.
  • La raison pour laquelle BB(748) est indépendant de ZFC ne vient pas de sa valeur elle-même, mais du fait qu’une des 748 machines, TM_ZFC_INC, ne s’arrête que si elle découvre une contradiction dans ZFC (une preuve du faux). Prouver que BB(748)=N revient à montrer que TM_ZFC_INC s’arrête en N étapes ou tourne indéfiniment, ce qui, d’après le théorème d’incomplétude de Gödel, est impossible à prouver si ZFC est cohérent.
  • Quelqu’un trouve encore plus étonnant d’avoir pensé qu’un petit nombre de lignes de texte — c’est-à-dire les axiomes de ZFC eux-mêmes — suffiraient à exprimer des vérités arithmétiques importantes pour les humains. Le fait qu’on ne puisse même pas prédire simplement le comportement d’une machine de Turing à 6 états lui paraît donc naturel. Il regrette qu’après l’annonce du théorème d’incomplétude de Gödel, les mathématiques n’aient pas cherché plus activement de nouveaux axiomes, en dehors de certains domaines de recherche fondamentale.
  • L’indépendance de l’hypothèse du continu vis-à-vis de ZFC en est un bon exemple : sa valeur de vérité (dans une perspective platonicienne, 1 ou 0) ne peut pas être établie dans ZFC. Même un seul bit n’y est donc pas garanti, sans parler de grands nombres.
  • Il est précisé qu’il faut bien distinguer le fait que BB(n) est non calculable, et le fait que BB(748), qui est par définition le nombre de 1 écrits par une machine de Turing à 748 états, est un nombre calculable. Le qualificatif « indépendant » signifie ici qu’il faut une théorie plus puissante que ZFC pour prouver que cette valeur est bien celle que l’on cherche.
  • Il est souligné que ce n’est pas le nombre lui-même qui est indépendant de ZFC, mais le processus de calcul de BB(748). (Tous les entiers peuvent être exprimés dans ZFC.)
• Le fait que BB(14) soit plus grand que le nombre de Graham est bien connu, et cette recherche donne à quelqu’un l’intuition que BB(7) sera lui aussi au moins aussi grand que le nombre de Graham. Intuitivement, l’idée permettant de passer de la pentation au nombre de Graham semble même plus simple que celle permettant d’aller de 47,176,870 à 2 <pentate> 5.
  • Réponse disant que c’est une bonne information et que cela pourrait constituer une excellente réponse à la publication d’origine.
• Partage d’un lien vers la conférence YouTube de Scott Aaronson, “How Much Math Is Knowable?” [Harward CMSA] https://www.youtube.com/watch?v=VplMHWSZf5c, ainsi que vers une discussion HN récente https://news.ycombinator.com/item?id=43776477
• Quelqu’un explique que les « exposants en haut à gauche » correspondent à la tétration, c’est-à-dire à une exponentiation répétée. Ainsi, ¹⁵10 signifie 10 à la puissance 10 à la puissance… répétée 15 fois. La personne dit avoir cru au départ à une faute de frappe, n’ayant jamais vu cette notation.
  • Dans la continuité des opérations itérées, quelqu’un répond que c’est cette fois la « pentation » qu’il découvre.
  • Une autre personne dit avoir déjà vu la tétration, mais préférer la notation up-arrow de Knuth [1], plus répandue et plus pratique pour les généralisations (1)
• L’explication selon laquelle BB(6) est le nombre maximal d’étapes avant arrêt d’une machine de Turing à 6 états et 2 symboles ({0,1}) démarrant sur un ruban initialement rempli de 0 a été très utile à un non-spécialiste. Il dit avoir senti que ce domaine est rempli d’une densité technique et d’une terminologie spécialisée propre à des chercheurs qui y travaillent depuis des décennies, mais avoir trouvé fascinant de tomber par hasard sur un texte aussi profond.
  • Quelqu’un ajoute que pour un étudiant de premier cycle en informatique théorique, le problème du busy beaver reste compréhensible même à la première lecture. Il y a certes beaucoup de vocabulaire spécialisé, mais il ne faut pas penser que c’est réservé à des gens ayant des décennies d’expérience.
  • Il est précisé que cette définition est standard en théorie de l’informatique plutôt qu’en software engineering.
• Quelqu’un se dit dérouté par l’explication selon laquelle avec « 10,000,000 sub10 » grains de sable, on pourrait remplir l’univers observable 10,000,000 sub10 fois. Il fait remarquer qu’on compare d’ordinaire ce genre de chose à la masse de l’univers observable, et qu’avec cette méthode on dépasse déjà de très loin la quantité réelle de matière.
  • Réponse : oui, c’est exact. Même en divisant par le nombre de grains de sable par univers, on reste à une échelle presque comparable, et dans cette notation les nombres voisins diffèrent déjà de façon astronomique. Ainsi, 10↑↑10,000,000 / (grains de sable par univers) reste bien plus grand que 10↑↑9,999,999. Dans notre système, on peut voir cela comme le fait qu’un (très grand) / (cosmiquement grand) reste simplement (très grand).
  • Quelqu’un ajoute qu’avec la tétration, on ne compare plus simplement des nombres de chiffres, mais des « nombres de nombres de chiffres ».
  • Il est réaffirmé que même en divisant ce nombre par environ 10^100000 grains de sable, cela ne le réduirait en rien de manière substantielle.
  • En guise d’exemple, il est rappelé que 10,000,000^10,000,000 est déjà une taille absurde, donc ajouter encore un étage exponentiel rend la comparaison elle-même dénuée de sens.
  • Un autre exemple plus familier est donné : en termes de chiffres significatifs, dire que 1 milliard - 1 million = 1 milliard n’est pas vraiment abusif.
• Quelqu’un se demande quel est le système logique le plus « riche » dont l’énumération des preuves peut être réalisée par une machine de Turing à 5 états.
  • La réponse dépend de ce qu’on entend exactement par « énumération ». Une question apparentée serait : quel est le système logique le plus puissant qui ne permet toujours pas de prouver la réponse pour toutes les machines de Turing à 5 états ? Une personne partage l’opinion que démontrer mathématiquement que Skelet #17 [0] ne s’arrête pas est tellement difficile que toute théorie capable de le prouver permettrait probablement aussi de décider tous les autres cas à 5 états. (0, 1)
  • Il faut d’abord préciser sous quelle interprétation des chaînes binaires finies on les considère comme une énumération de preuves logiques avant de discuter l’hypothèse.
• Quelqu’un demande si l’univers observable serait assez grand pour écrire la valeur exacte de BB(6).
  • En considérant l’univers observable comme un système fermé et en appliquant la borne de Bekenstein, on obtient une capacité maximale d’environ 10^120 bits. L’estimation actuelle de la masse-énergie totale est d’environ 10^53 kg, et en l’injectant dans la formule on reste autour de 10^120 bits. C’est donc impossible, chiffres à l’appui.
  • Il est souligné que la quantité d’information stockable dans l’univers est d’environ 10^120 bits et que, même en se trompant de plusieurs ordres de grandeur, cela ne changerait rien : on est de toute façon très loin du compte.
  • La question semble supposer que toute la valeur doit être stockée simultanément. Sans cette contrainte de simultanéité, il serait peut-être théoriquement possible de l’écrire au fil d’un temps infini, mais il faudrait alors tenir compte de limites réalistes comme la mort thermique de l’univers. C’est impossible dans le référentiel du CMB, mais on se demande s’il n’existerait pas d’autres façons de découper l’espace-temps.
  • Dès le premier nombre de l’article, on est déjà à ¹⁵10, c’est-à-dire quelque chose comme 10^(¹⁴10), donc le simple nombre de chiffres est déjà de l’ordre de ¹⁴10 ; c’est absolument impossible.
  • Quelqu’un reconfirme brièvement que non, c’est impossible.
• Chaque fois que quelqu’un voit ce type de résultat en théorie de la complexité, il se dit que les discours à la mode du type « la superintelligence est un dieu » sont complètement sans fondement. Même si on transformait tous les atomes de l’univers en superordinateur et qu’on exploitait jusqu’à l’énergie des trous noirs, calculer l’état d’arrêt de BB(6) resterait à jamais impossible.
  • Réponse brève : ce genre d’homme de paille n’a jamais été convaincant de toute façon.