Un jeu d'enfant qui tourne mal
Imaginez une règle simple : prenez 1, multipliez par 2, ajoutez 1, multipliez par 2, ajoutez 1… Recommencez. Au bout de dix étapes, vous obtenez un nombre raisonnable. Au bout de cent, votre calculatrice affiche une erreur. Au bout de mille, aucun ordinateur sur Terre ne peut stocker le résultat. Pourtant, la règle est d'une banalité désarmante. Que se passe-t-il vraiment ?
Ce genre de vertige arithmétique n'est pas qu'une curiosité de récréation mathématique. Il touche à quelque chose de profond : les limites de ce que les mathématiques peuvent connaître d'elles-mêmes. Et au cœur de cette histoire se trouve un objet aussi fascinant qu'inquiétant — la fonction Busy Beaver.
Quand la tortue dépasse la fusée
Pour comprendre pourquoi certains nombres sont « trop grands » pour les mathématiques, il faut d'abord saisir ce que signifie calculable. Une fonction est dite calculable si une machine — un ordinateur, en théorie infini en mémoire et en temps — peut produire son résultat en un nombre fini d'étapes. L'addition est calculable. La multiplication aussi. Même des fonctions qui croissent à une vitesse prodigieuse, comme la fonction d'Ackermann — qui empile des exponentielles sur des exponentielles — restent calculables : lentes à obtenir, certes, mais accessibles en principe.
La fonction Busy Beaver, elle, joue dans une autre catégorie. Introduite par le mathématicien Tibor Radó en 1962, elle pose une question apparemment innocente : parmi toutes les machines à calculer (appelées machines de Turing) ayant exactement n états internes, quelle est celle qui s'arrête en ayant écrit le plus grand nombre de symboles sur son ruban avant de s'arrêter ? Ce maximum, noté BB(n), c'est la valeur de la fonction Busy Beaver pour n.
Une machine de Turing, pour les non-initiés, est un modèle théorique d'ordinateur : elle lit et écrit des symboles sur un ruban infini, en suivant des règles précises selon son état interne. C'est le modèle abstrait sur lequel repose toute l'informatique moderne. Plus une machine a d'états, plus elle peut faire de choses complexes.
Résultat : BB(1) = 1. BB(2) = 6. BB(3) = 21. BB(4) = 107. Et BB(5) ? On ne le connaît pas encore avec certitude — les estimations actuelles le placent autour de 47 millions. BB(6) dépasse 10 puissance 18 267 — soit un 1 suivi de plus de dix-huit mille zéros. Et BB(7) ? Personne ne le sait. Personne ne peut le savoir.
La vitesse limite de l'arithmétique
Ce n'est pas une question de puissance de calcul insuffisante. C'est une limite fondamentale, de la même nature que la vitesse de la lumière en physique. La fonction Busy Beaver croît plus vite que toute fonction calculable. Quel que soit l'algorithme que vous inventez, aussi tordu soit-il, BB(n) le dépasse à partir d'un certain rang. C'est mathématiquement démontré.
Et la conséquence est stupéfiante : calculer BB(n) pour des valeurs même modestes de n est impossible en principe. Pas « difficile ». Pas « long ». Impossible. Aucune machine, aucun algorithme, aucune méthode systématique ne peut produire ces valeurs. La fonction Busy Beaver est ce qu'on appelle non-calculable — elle existe mathématiquement, mais elle échappe à tout procédé mécanique.
« La fonction Busy Beaver est comme un horizon : vous savez qu'il existe, mais vous ne pouvez jamais l'atteindre. »
—
Gödel avait prévenu
Pour comprendre pourquoi cette limite est si profonde, il faut remonter aux années 1930 et aux travaux de Kurt Gödel. En 1931, ce logicien autrichien a démontré deux théorèmes qui ont ébranlé les fondements des mathématiques. Le premier dit, en simplifiant : tout système logique suffisamment puissant contient des énoncés vrais qu'il ne peut pas prouver. Le second : un tel système ne peut pas prouver sa propre cohérence.
Ces théorèmes d'incomplétude signifient qu'il existe une frontière entre ce qui est vrai et ce qui est démontrable. Et la fonction Busy Beaver se trouve précisément sur cette frontière — ou plutôt, de l'autre côté. Déterminer la valeur de BB(n) pour des n suffisamment grands revient à résoudre des problèmes que les mathématiques standard — celles qu'on utilise tous les jours, fondées sur les axiomes de Zermelo-Fraenkel — ne peuvent tout simplement pas trancher.
Des chercheurs ont récemment montré que certaines valeurs de BB sont liées à des questions indécidables dans des systèmes logiques précis. Par exemple, BB(748) — un nombre à l'ampleur inconcevable — est directement connecté à la cohérence de l'arithmétique de Peano, le système formel qui décrit les nombres entiers. Autrement dit : pour connaître BB(748), il faudrait un système logique plus puissant que l'arithmétique elle-même.
Des niveaux de logique empilés comme des poupées russes
Face à ces limites, les mathématiciens ne restent pas les bras croisés. Ils inventent de nouveaux cadres logiques — des systèmes d'axiomes plus forts, capables de prouver davantage. Mais chaque nouveau système rencontre ses propres limites de Gödel. Il faut alors en inventer un autre, encore plus puissant. Et ainsi de suite, à l'infini.
C'est une image vertigineuse : les mathématiques ne sont pas un édifice fini, mais une tour dont on ne peut jamais voir le sommet. Chaque étage permet de voir plus loin — et de réaliser qu'il reste encore plus à construire.
Ce que la fonction Busy Beaver révèle, c'est que cette hiérarchie n'est pas abstraite. Elle est encodée dans des nombres concrets, issus de règles arithmétiques enfantines. Des additions, des multiplications, des machines à états. Et pourtant, ces nombres portent en eux toute la complexité des fondements des mathématiques.
Concepts à emporter
Pour les matheux
La fonction Busy Beaver BB(n) est définie comme le nombre maximal de « 1 » écrits sur le ruban d'une machine de Turing à n états qui s'arrête, en partant d'un ruban vide. Une machine de Turing à n états est un automate fini avec un alphabet binaire {0, 1}, un ruban infini, et une table de transition : à chaque paire (état, symbole lu), elle associe un symbole à écrire, une direction de déplacement (gauche ou droite), et un nouvel état (ou l'arrêt).
La non-calculabilité de BB se démontre par réduction au problème de l'arrêt : si BB était calculable, on pourrait décider si une machine de Turing quelconque s'arrête — il suffirait de simuler toutes les machines à n états jusqu'au seuil BB(n). Or le problème de l'arrêt est indécidable (Turing, 1936), donc BB ne l'est pas non plus.
Plus précisément, BB croît plus vite que toute fonction récursive totale : pour toute fonction calculable f : ℕ → ℕ, il existe un rang n₀ tel que pour tout n ≥ n₀, BB(n) > f(n). Cette propriété place BB strictement au-delà de toute hiérarchie de croissance constructive (hiérarchie de Grzegorczyk, fonction d'Ackermann, etc.).
Le lien avec l'incomplétude de Gödel est formel : pour un système axiomatique récursivement énumérable T suffisamment expressif, il existe un entier n_T tel que T ne peut pas prouver la valeur exacte de BB(n) pour n ≥ n_T. Des travaux récents ont précisé ces seuils pour des systèmes comme l'arithmétique de Peano (PA) ou ZFC.
