BusyBeaver(6) est vraiment immense

 (scottaaronson.blog)
2 points par GN⁺ 2025-06-29 | 1 commentaires | Partager sur WhatsApp
  • La borne inférieure connue de BB(6) a de nouveau fortement augmenté, confirmant que le temps d’arrêt maximal d’une machine de Turing à 6 états dépasse de très loin toute échelle de la réalité observable
  • BB(6) désigne le nombre maximal d’étapes qu’une machine de Turing à 6 états et 2 symboles, démarrant sur un ruban rempli de 0, peut exécuter avant de s’arrêter
  • Après l’amélioration de Pavel Kropitz en 2022, mxdys a repoussé la borne inférieure à un niveau supérieur à 10 tétré à 10 millions
  • Le résultat le plus récent montre que BB(6) est au moins égal à 2 penté à 5, faisant intervenir une opération encore un cran au-dessus de la tétration
  • BB(5) a été déterminé à 47 176 870, mais BB(6) devient si gigantesque que cela alimente l’idée que le point où BB(n) devient indépendant des axiomes de ZFC pourrait se situer à n=7, 8 ou 9

La borne inférieure de BB(6) augmente encore

  • Avant 2022, on ne savait guère plus que BB(6) > 10^36,534, puis Pavel Kropitz a amélioré cela à un niveau supérieur à 10 tétré à 15
  • La tétration (tetration) désigne l’itération de l’exponentiation
    • Par exemple, empiler 10 quinze fois donne un nombre de la forme 10 puissance 10 puissance 10 puissance … sur 15 niveaux
  • Tristan Sterin, organisateur de BBchallenge, a annoncé que le membre de l’équipe mxdys avait de nouveau relevé la borne inférieure de BB(6)
  • Une amélioration ultérieure de mxdys montre que BB(6) est au moins égal à 2 tétré à 2 tétré à 2 tétré à 9
    • En particulier, BB(6) est au moins égal à 2 penté à 5
    • La pentation (pentation) est l’itération de la tétration, soit une opération d’un niveau supérieur à la tétration, elle-même itération de l’exponentiation

L’écart extrême entre BB(5) et BB(6)

  • BB(6) est le sixième nombre de Busy Beaver
    • Il concerne les machines de Turing à 6 états
    • L’alphabet est {0,1}
    • Le ruban d’entrée est initialement rempli de 0
    • Il s’agit du nombre maximal d’étapes d’exécution possibles avant l’arrêt
  • L’équipe internationale BBchallenge a déterminé l’an dernier que BB(5) vaut 47 176 870
  • Entre BB(5) et BB(6), la fonction Busy Beaver passe d’une échelle de quelques dizaines de millions à une taille qui dépasse le champ de la réalité observable

Des nombres pour lesquels l’intuition ne fonctionne presque plus

  • Même au moment où l’on savait seulement que BB(6) > 10 tétré à 10 millions, il était déjà presque impossible d’en donner une explication intuitive
  • Par exemple, on peut dire qu’avec autant de grains de sable, on pourrait remplir approximativement ce même nombre de copies de l’univers observable
  • Cette analogie montre que ce nombre est si immensément plus grand qu’une grandeur cosmique comme 10^100 que, même après division, il reste pratiquement du même ordre que le nombre d’origine

Vers une baisse de l’estimation du seuil d’indépendance vis-à-vis de ZFC

  • Le fait que BB(6) soit devenu aussi grand ne bouleverse pas toutes les idées sur la fonction Busy Beaver
  • Il était déjà possible que BB(6), au lieu d’être à un niveau relativement modeste comme 10^36,534, se situe dans le domaine des opérations itérées
  • Maintenant qu’une borne inférieure de cet ordre a été confirmée, l’estimation du point où la valeur de BB(n) devient indépendante du système axiomatique en théorie des ensembles ZFC pourrait être revue à la baisse
    • Auparavant, on pouvait imaginer n aux alentours de 20 ou 30
    • Désormais, cela pourrait être n=7, 8 ou 9
  • Le résultat d’indépendance vis-à-vis de ZFC actuellement connu situe ce phénomène à n=643 pour BB(n)

Mise à jour séparée : STOC 2025

  • À Prague, où se tenait STOC 2025, plusieurs chercheurs ont été rencontrés et de nouveaux éléments ont été découverts
  • Le titre de la conférence plénière de STOC était The Status of Quantum Speedups
  • Les lecteurs intéressés peuvent consulter les slides PowerPoint de cette présentation

À lire aussi

1 commentaires

 
GN⁺ 2025-06-29
Avis sur Hacker News

  • Sur le serveur Discord de bbchallenge, on spécule activement sur le nombre d’états de machine de Turing qu’il faudrait pour dépasser le nombre de Graham, bien plus grand que le 2^^2^^2^^9 atteint par le dernier champion BB(6).
    Si l’on regarde le functional busy beaver https://oeis.org/A333479, des comportements à l’échelle de Graham pourraient apparaître étonnamment tôt. Un terme lambda de 49 bits suffirait.
    Il n’existe que 77 519 927 606 termes lambda clos d’une taille inférieure ou égale à celle-ci https://oeis.org/A114852, alors qu’il y a 4^12*23836540=399910780272640 machines de Turing distinctes à 6 états https://oeis.org/A107668.
    Puisqu’on a atteint la pentation avec seulement 6 états, plusieurs personnes pensent désormais qu’avec 7 états on pourrait dépasser le nombre de Graham. Je trouve tout de même cela assez surprenant. Il y a quelques jours, j’ai fait un gros pari avec l’une d’elles sur la question de savoir si une preuve de BB(7)>Graham's apparaîtra dans les dix prochaines années, et je suis curieux de savoir ce qu’en pensent les autres.

    • Je ne peux pas prétendre être un expert, mais BB(7) est probablement plus grand que le nombre de Graham.
      BB doit croître plus vite que toute suite calculable. Ce que cela signifie concrètement pour BB(7) relève au final surtout de l’explication à grands gestes, mais j’ai l’impression qu’il doit gravir très vite l’échelle de la puissance des opérateurs. En fin de compte, il doit croître plus vite que n’importe quel opérateur calculable que nous définissons, y compris par exemple up-arrow^n ou up-arrow^f(n) pour une fonction calculable f.
      Intuitivement, la croissance de 47 million à 2^^2^^2^^9 me semble qualitativement plus importante, en termes de puissance d’opérateur nécessaire, que celle de 2^^2^^2^^9 au nombre de Graham. Le nombre de Graham est g_64, où g se situe grosso modo un cran au-dessus de up_arrow^n, donc il est probablement vrai que BB(7)>Graham's Number.

  • Le fait qu’un nombre comme BB(748), qui plus est non calculable, puisse être « indépendant de ZFC » me donne le vertige. On dirait une sorte d’erreur de catégorie.

    • Ce qui rend BB(748) indépendant de ZFC, ce n’est pas la valeur elle-même, mais le fait que l’une des machines à 748 états, TM_ZFC_INC, soit conçue pour chercher une contradiction dans ZFC, c’est-à-dire une preuve de FALSE, et ne s’arrêter que si elle la trouve.
      Par conséquent, une preuve de BB(748)=N devrait montrer soit que TM_ZF_INC s’arrête en au plus N étapes, soit qu’elle ne s’arrête jamais. En supposant ZFC cohérent, le célèbre résultat de Gödel rend les deux impossibles.
    • Ce qui est non calculable, c’est BB(n). Autrement dit, il n’existe pas d’algorithme qui donne la valeur de BB(n) pour un n arbitraire.
      BB(748), lui, est calculable. Par définition, c’est le nombre de 1 écrits par une certaine machine de Turing à 748 états, et cette machine calcule BB(748).
      Le nombre lui-même n’est littéralement qu’un entier inimaginablement grand. L’indépendance vis-à-vis de ZFC intervient quand on essaie de prouver que ce nombre est bien celui que l’on cherche. Pour cela, il faut une théorie plus forte que ZFC, capable de capturer les propriétés des machines de Turing à 748 états.
    • Ce qui est plutôt plus étonnant, c’est qu’on ait pensé qu’un texte aussi court que les axiomes de ZFC, tenant largement sur une serviette en papier, serait « suffisant » pour capturer la vérité arithmétique ou les aspects de la réalité physique principalement liés aux activités humaines.
      Le fait que le comportement d’une machine de Turing à 6 états puisse être imprévisible à partir de quelques lignes de texte n’a rien d’étonnant.
      J’aurais pensé que, dès que Gödel a publié son premier théorème d’incomplétude, toute la communauté mathématique se serait ruée à toute vitesse vers la recherche de nouveaux axiomes. Or, pendant près d’un siècle, le travail de Gödel a plutôt été traité comme un fait étrange cantonné à un domaine étroit des fondements, plutôt que comme un programme dominant. Je connais Feferman, Friedman, etc., mais la recherche dans ce domaine est bien moins abondante que dans la plupart des autres sujets des mathématiques.
    • Le nombre lui-même n’est pas indépendant de ZFC. Tous les entiers sont exprimables dans ZFC. Ce qui est indépendant de ZFC, c’est le processus de calcul de BB(748).
    • Un nombre individuel n’est pas non calculable en soi. Il n’existe aucune paire composée d’un nombre et d’une preuve dans ZFC établissant que ce nombre est la valeur de BB(748).
      Il n’existe donc pas non plus de programme dont ZFC puisse prouver qu’il affiche la valeur de BB(748). Mais, comme pour tout autre nombre, il existe bel et bien un programme qui affiche BB(748).

  • On sait que BB(14) est plus grand que le nombre de Graham, mais au vu de ce résultat, BB(7) est probablement lui aussi plus grand que le nombre de Graham.
    Intuitivement, la technique nécessaire pour passer de la pentation au nombre de Graham me paraît plus simple que celle nécessaire pour passer de 47,176,870 à 2 5.

  • Quand j’ai lu l’explication selon laquelle l’exposant à gauche désigne la tétration, c’est-à-dire l’exponentiation itérée, j’ai d’abord cru à une faute de frappe. C’est la première fois que je rencontre la tétration.

    • J’en avais déjà vu auparavant, mais à l’époque on utilisait la notation des flèches de Knuth, que j’aimais bien parce qu’elle se généralise facilement https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation
    • En poursuivant cette logique d’itération, c’est la première fois que je rencontre la pentation.

  • Je ne comprends pas le passage qui dit : « Imaginez qu’il y ait 10,000,000sub10 grains de sable. On pourrait alors remplir environ 10,000,000sub10 univers observables avec ce sable »
    Est-ce qu’on arrondit vraiment jusqu’à faire disparaître le volume de l’univers observable divisé par le volume moyen d’un grain de sable ? Cela représente un écart de bien plus de chiffres que la masse totale de l’univers qu’on utilise d’habitude dans ce genre de comparaison

    • Oui. Diviser par ce rapport n’a en pratique presque aucun effet, parce que, dans cette notation, des nombres « adjacents » produisent des changements bien plus grands
      10↑↑10,000,000 / (nombre de grains de sable par univers) reste par exemple immensément plus grand que 10↑↑9,999,999
      Dans un système qui manipule des nombres comme ceux-là, il n’y a guère de meilleure façon d’écrire (un nombre extrêmement grand)/(un nombre seulement à l’échelle cosmique) qu’en l’écrivant exactement ainsi, et dans la notation du très grand nombre, cela finit presque par s’arrondir à (un nombre extrêmement grand)
    • Avec la tétration, on ne manipule plus l’ordre de grandeur du nombre de chiffres, mais l’ordre de grandeur de l’ordre de grandeur du nombre de chiffres
    • Un exemple plus courant de ce type de comparaison : en chiffres significatifs, un milliard moins un million, cela reste un milliard
    • Exact. Ce nombre est tellement plus grand que des quantités comme 10^100000 ou le nombre de grains de sable que l’on peut y mettre que le diviser par cette quantité ne le change pratiquement pas. En tout cas pas au point de le faire descendre près de 9,999,999sub10
    • Oui. Cela ne représente qu’un écart d’un nombre ordinaire de chiffres. Rien que 10,000,000^10,000,000 est déjà assez grand pour que ce genre d’écart ne compte plus vraiment ; alors a fortiori après avoir élevé l’exposant lui-même à une puissance neuf fois de plus

  • How Much Math Is Knowable? de Scott Aaronson [Harward CMSA] : https://www.youtube.com/watch?v=VplMHWSZf5c
    C’était aussi passé sur HN il y a quelques mois : https://news.ycombinator.com/item?id=43776477

  • Quelle est la logique la plus riche dont on puisse énumérer les preuves avec seulement une machine de Turing à 5 états ?

    • Cela dépend de ce qu’on considère comme une énumération, mais une question liée est : « quelle est la logique la plus riche qui ne puisse pas prouver l’arrêt ou le non-arrêt de toutes les machines de Turing à 5 états ? » Autrement dit, quelle est la logique la plus riche pour laquelle l’arrêt d’une certaine machine de Turing à 5 états est indépendant
      J’ai un peu réfléchi à cette version, mais je ne suis pas allé très loin faute d’expertise en logique du premier ordre. À ma connaissance, Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA est l’une des machines dont il est mathématiquement le plus difficile de prouver le non-arrêt https://arxiv.org/abs/2407.02426 ; donc si une théorie peut prouver que Skelet #17 ne s’arrête pas, elle a de bonnes chances de trancher aussi les autres machines à 5 états
    • Tout dépend entièrement de la manière dont on interprète une chaîne binaire finie comme une énumération de preuves logiques

  • En lisant l’explication selon laquelle « BB(6) est le sixième nombre de Busy Beaver, c’est-à-dire le nombre maximal d’étapes qu’une machine de Turing à 6 états sur l’alphabet {0,1} peut effectuer avant de s’arrêter lorsqu’elle est lancée sur un ruban initialement entièrement rempli de 0 », en tant que non-spécialiste, j’ai plutôt eu l’impression que c’était presque trop clair
    C’est manifestement un blog hardcore destiné à des gens qui font ce genre de recherche depuis des décennies. C’est assez fascinant de tomber par hasard sur un texte écrit sans compromis pour un public précis, très dense et rempli de jargon

    • Pour quelqu’un qui a une formation de licence en informatique, même s’il découvre le problème du Busy Beaver, l’explication suffit à peu près pour comprendre de quoi il s’agit
      C’est bien du jargon de niche, mais penser que seuls des gens qui y ont consacré des décennies peuvent y accéder, c’est se sous-estimer
    • Cette définition fait partie du contenu standard de théorie de l’informatique en licence. En revanche, ce n’est pas forcément standard en ingénierie logicielle

  • Un nombre aussi grand ne peut pas être visualisé par un humain. Compter n’est pas la seule façon de représenter un nombre
    Par exemple, on peut considérer qu’un seul grain de sable a une infinité d’états possibles. Comme il existe une infinité de nombres réels, on pourrait dire qu’un seul grain de sable peut représenter BB(6). Les combinaisons peuvent croître exponentiellement, donc ce genre de méthode pourrait être utile pour la représentation

    • À partir d’un certain point, les grands nombres ressemblent beaucoup moins à de « grandes quantités » qu’à la force de cohérence d’un système formel
      Autrement dit, il s’agit de savoir combien de temps un système peut réussir à faire semblant de ne pas être contradictoire avant d’être démasqué. Un système contradictoire qui simule la cohérence via BB(3) sera « démasqué » bien plus vite qu’un système qui la simule via BB(6). Ici, faire semblant d’être cohérent signifie affirmer que tous les programmes qui s’exécutent pendant plus de BB(n) étapes, pour un certain n, ne s’arrêtent pas
    • Si l’univers est arrondi à l’unité de Planck la plus proche, le nombre d’états possibles d’un grain de sable cesse soudain d’être si grand
      Faire appel à une précision infinie pour rendre le problème apparemment plus maniable relève pour moi du tour de passe-passe. Pour expliquer une échelle, mieux vaut utiliser des entiers
    • Cet exemple est déroutant. Si le nombre de grains de sable et le nombre d’univers observables sont égaux, cela ne signifie-t-il pas qu’il y a un grain de sable par univers ?

  • Je me demande si l’Univers observable est assez grand pour écrire la valeur exacte de BB(6)

    • Si l’on considère l’Univers observable comme un système fermé, on peut essayer d’appliquer la limite de Bekenstein
      R ≈ 46.5 billion light-years, c’est-à-dire le rayon de l’Univers observable, et E ≈ le contenu total en masse-énergie de l’Univers observable
      La masse-énergie inclut la matière ordinaire, la matière noire et l’énergie noire. Selon les estimations actuelles, l’Univers observable a un équivalent masse-énergie d’environ 10^53 kg
      En injectant cela dans S ≤ 2πER/ℏc, on obtient une quantité maximale d’information de l’ordre 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
      Donc c’est impossible
    • Clairement, ce n’est pas suffisant. La quantité d’information stockable dans l’Univers est d’environ 10^120 bits. Même si je me trompais de mille milliards de chiffres, le résultat ne changerait pas
    • Rien que le nombre de départ dans l’article est ¹⁵10. Cela signifie 10^(¹⁴10), et donc qu’il comporte ¹⁴10 chiffres. On ne peut donc pas l’écrire
    • Je pense qu’il s’agit sans doute du fait que toutes les parties de l’expression complète existent simultanément. Si elles n’ont pas besoin d’exister simultanément, il serait peut-être possible de « l’écrire » si la durée de vie de l’Univers est infinie. Je ne sais pas comment la mort thermique intervient là-dedans, donc je dis bien « peut-être »
      Mais dans l’espace-temps relativiste, le terme « simultanément » n’est pas bien défini. Les commentaires frères ont certainement raison dans le référentiel suggéré par le fond diffus cosmologique. Cela dit, je me demande s’il n’existerait pas un référentiel dans lequel on pourrait découper l’espace-temps de façon à rendre possible une expression « simultanée »