La plupart des gens ne pensent probablement pas aux mathématiques en entendant parler des « castors occupés ». Pourtant, ces petits animaux symbolisent un concept fascinant dans le domaine complexe des mathématiques : il existe des choses qui ne peuvent pas être calculées, peu importe l’effort fourni (ou à quel point vous êtes un castor occupé). La fonction des castors occupés est le premier exemple d’une expression mathématique non calculable. Cette fonction est simple à expliquer : elle fait référence au plus grand nombre d’étapes qu’un programme informatique peut effectuer avant de s’arrêter, si le programme a n états, où les états représentent la complexité du problème. Cependant, ses valeurs, notées BB(n), ne seront jamais connues pour toutes les quantités de n. Les mathématiciens et les informaticiens théoriciens se sont longtemps interrogés sur la valeur de n à partir de laquelle les outils mathématiques échouent : où se situe exactement la limite de ce qui peut être calculé ?
Pendant plus de 40 ans, de nombreux experts ont supposé que BB(5) pourrait dépasser cette limite de calculabilité et serait donc inaccessibile. Cependant, un projet collaboratif international, le Busy Beaver Challenge, a réussi à déterminer la valeur de BB(5), et son calcul a été formellement vérifié par un assistant de preuve assisté par ordinateur. Selon cette nouvelle recherche, le nombre magique pour BB(5) est 47 176 870, ce qui signifie qu’un programme avec cinq états peut effectuer un maximum de 47 176 870 étapes avant de s’arrêter — ou ne s’arrêtera jamais. La dernière grande réalisation des « castors occupés » a eu lieu en 1983, lorsque le regretté informaticien Allen Brady a prouvé que BB(4) équivaut à 107.
Les castors occupés sont profondément ancrés dans les fondements des mathématiques. Au XXe siècle, de nombreux experts rêvaient de trouver une base sur laquelle toutes les vérités mathématiques pourraient être prouvées. Mais en 1931, le logicien Kurt Gödel, alors âgé de seulement 25 ans, a brisé leurs espoirs. Il a prouvé qu’il existe inévitablement des énoncés indémontrables en mathématiques — des énoncés qui ne peuvent être ni prouvés ni réfutés. Au départ, les experts espéraient que cela soit un résultat abstrait sans applications significatives. Mais ils avaient tort.
Les mathématiciens connaissent désormais de nombreux problèmes indémontrables. L’un des premiers exemples est le problème de l’arrêt, qui concerne l’exécution des algorithmes. Dans les années 1930, Alan Turing a découvert qu’il n’existe aucun algorithme capable de prédire si un programme informatique avec certaines entrées s’exécutera indéfiniment ou s’arrêtera à un moment donné. À l’époque, Turing travaillait sur le modèle théorique d’un tel ordinateur, désormais appelé machine de Turing. Cette machine théorique se compose d’une bande infinie étiquetée avec des 1 et des 0, et d’une tête qui lit la bande, la décrit et la déplace à droite ou à gauche. Une telle machine peut théoriquement effectuer n’importe quel type de calcul — tout comme un ordinateur.
Imaginons que vous souhaitiez programmer une machine de Turing pour multiplier deux nombres. Les 1 et les 0 sur la bande correspondent alors aux deux nombres. Avant le calcul, vous définissez un certain nombre d’états, ou règles, pour la machine, tels que A, B, C et D, ainsi que HALT. Ces états déterminent comment la machine de Turing agit avec chaque entrée. Par exemple : si la machine à cinq états lit un 1 sur la bande dans l’état A, elle le remplace par un 0, déplace la bande vers la gauche et passe à l’état C. Deux instructions sont donc nécessaires pour chacun des états A à D, selon que la machine trouve un 1 ou un 0 sur la bande. Dans certaines circonstances (par exemple, l’état B en lisant un 1), la machine peut passer à l’état HALT. Dans ce cas, la machine de Turing s’arrête, et le calcul est terminé. Le résultat serait alors les nombres sur la bande à ce moment-là.
Comme Turing l’a prouvé, il n’existe pas de machine de Turing capable de déterminer, pour toutes les configurations possibles de machines de Turing, c’est-à-dire tous les algorithmes, si elles s’arrêteront à un moment donné. Et c’est là que les castors occupés entrent en jeu.
Dans le « jeu des castors occupés », développé en 1962, le mathématicien hongrois Tibor Radó a cherché à identifier la machine de Turing la plus assidue d’une certaine taille : quel est le nombre maximum d’étapes de calcul qu’une machine de Turing avec n états, qui s’arrête à un moment donné, peut effectuer ?
Pour répondre à cette question de manière générale, il faudrait résoudre le problème de l’arrêt. Pour trouver le castor occupé le plus actif, il est nécessaire de savoir quelles machines de Turing s’arrêtent (et donc cessent de fonctionner à un certain moment) et lesquelles ne le font pas. Mais Turing a montré qu’il est impossible de le savoir, ce qui signifie que la fonction des castors occupés BB(n) ne peut pas être calculée pour tous les nombres d’états possibles.
Néanmoins, Radó a déterminé les trois premières valeurs de la fonction BB, bien que cela ait nécessité de grands efforts dans certains cas. La difficulté provient en partie du fait que le nombre de machines de Turing possibles (algorithmes informatiques) augmente rapidement à mesure que le nombre d’états (n) augmente. Pour chacune des deux valeurs d’entrée, 0 ou 1, la machine de Turing effectue trois étapes différentes dans un état particulier :
- Elle remplace l’entrée par une sortie (0 ou 1). Cette étape a deux opérations possibles.
- Elle déplace la bande vers la droite ou vers la gauche. Cela implique également deux opérations possibles.
- Elle change vers l’un des n états ou vers l’état d’arrêt. Cette étape nécessite n + 1 opérations possibles.
Ainsi, il y a 2 x 2 x (n + 1) opérations possibles pour chaque valeur d’entrée et chacun des n états. En combinant les deux entrées, on obtient un total de (4n + 4)²n ensembles possibles d’étapes particulières, où chaque ensemble représente un algorithme différent, ou une machine de Turing différente. Si un seul état est autorisé, il y a déjà 64 machines de Turing différentes. Parmi celles-ci, seules celles qui passent à l’état HALT après la première étape de calcul s’arrêteront. Comme il n’y a qu’une seule autre règle en plus de HALT, si la machine ne s’arrête pas, elle continuera à exécuter cette règle indéfiniment. Par conséquent, aucune des machines de Turing qui s’arrêtent ne dépassera une étape de calcul, ce qui explique pourquoi BB(1)=1.
Les choses deviennent un peu plus compliquées si l’on autorise deux états. Dans ce cas, il y a déjà (4 x 2 + 4) à la puissance quatre, soit 20 736 machines de Turing à examiner. Il n’existe pas de méthode généralement valide pour déterminer quelles machines de Turing s’arrêtent. Comme Radó l’a découvert, le programme le plus long avec deux états — le castor occupé le plus actif — peut effectuer six étapes arithmétiques, donc BB(2)=6.
Radó et son étudiant en doctorat Shen Lin ont également pu clarifier le cas de trois états en 1965 : parmi les 16 777 216 machines de Turing, celles qui s’arrêtent à un moment donné peuvent effectuer au maximum BB(3)=21 étapes de calcul. En 1963, Radó a décrit la tentative de calcul de BB(4) comme désespérée. Mais 20 ans plus tard, Brady a réussi à déterminer BB(4) : le nombre maximum d’étapes de calcul pour une machine de Turing avec quatre états (ou quatre règles) est 107. Cela est resté la dernière valeur de la fonction des castors occupés qui a pu être déterminée exactement pendant quatre décennies.
Peu après la publication du résultat de Brady, la communauté mathématique s’est tournée vers le calcul exact de BB(5). Des experts ont organisé une compétition dans la ville allemande de Dortmund en 1984, où ils ont tenté de trouver la cinquième valeur de la fonction. Les participants cherchaient des machines de Turing à cinq états qui effectuaient le plus grand nombre d’étapes de calcul avant de s’arrêter. Le gagnant de la compétition était l’informaticien Uwe Schult, qui a trouvé un programme avec 134 467 étapes de calcul. Cinq ans plus tard, les informaticiens Heiner Marxen et Jürgen Buntrock ont découvert l’une des machines à cinq états qui ne s’est pas arrêtée avant d’atteindre 47 176 870 étapes, présentant ainsi une nouvelle valeur minimale pour BB(5). Cependant, il n’a pas été prouvé qu’un programme encore plus assidu ne se cachait pas parmi les machines de Turing à cinq états.
Les chasseurs de castors occupés devaient prouver que toutes les autres machines fonctionnaient indéfiniment ou s’arrêtaient plus tôt que la 47 176 870e étape. Et il y a un grand nombre de machines de Turing à cinq états. Pour déterminer BB(n), il faut clairement montrer que certaines des machines de Turing ne s’arrêtent jamais. Par exemple, il faut prouver qu’un programme se termine dans une boucle qui se répète indéfiniment. Il est encore plus difficile de prouver qu’une machine de Turing continue de fonctionner indéfiniment sans motif répétitif — comme les décimales d’un nombre irrationnel.
La recherche d’une machine de Turing à cinq états qui effectue plus de 47 176 870 étapes de calcul est restée infructueuse pendant plusieurs décennies. Par conséquent, de nombreux experts soupçonnaient que BB(5)=47 176 870. Mais sans preuve solide, cela restait hypothétique.
C’est pourquoi Tristan Stérin, alors doctorant en informatique, a lancé le Busy Beaver Challenge en 2022. L’objectif du projet était de rassembler et de vérifier tous les résultats relatifs aux castors occupés. Par exemple, si quelqu’un prouvait qu’un programme à cinq états pouvait fonctionner indéfiniment, il pouvait publier la preuve et la faire vérifier par un logiciel d’assistance à la preuve. Cela a permis à de nombreuses personnes intéressées de collaborer et de présenter des résultats valides. Le projet a été achevé ce mois-ci, avec la preuve finale que BB(5) est effectivement 47 176 870.
Étant donné que chacun des castors occupés correspond à un algorithme, on peut se demander ce que BB(5) calcule réellement. Le programme correspond à une fonction récursive similaire à celle de la conjecture de Collatz, l’un des plus grands problèmes non résolus en théorie des nombres. BB(5) calcule la valeur (5x + 18) / 3 pour une entrée x si x est divisible par 3 ; (5x + 22) / 3 si x divisé par 3 donne un reste de 1 ; et si x divisé par 3 a un reste de 2, le programme s’arrête.
Et la recherche de castors occupés se poursuit. Le détenteur du record pour les machines de Turing à six états effectue déjà tant d’étapes arithmétiques qu’il faut une nouvelle opération arithmétique pour enregistrer le nombre de manière compacte (10↑↑15, ou 10 à la puissance de 10 à la puissance de 10, 15 fois au total). De plus, il y a de plus en plus de preuves que BB(6) n’est probablement pas calculable. Plus significatif encore, en 2024, une machine de Turing à six états a été trouvée qui correspond presque au problème de Collatz. Ainsi, si l’on voulait montrer que cette machine s’arrête (ou continue de fonctionner indéfiniment), cela équivaudrait à résoudre le problème de Collatz. La conjecture de Collatz stipule que si vous commencez avec un entier positif et suivez deux règles spécifiques, vous finirez dans une boucle spécifique. Les mathématiciens tentent de résoudre ce problème depuis des décennies sans succès. Une crainte est donc que le problème de Collatz soit l’un des énoncés indémontrables des mathématiques.
Dans ce cas, les tentatives de calculer BB(6) seraient inévitablement vouées à l’échec. L’informaticien Scott Aaronson n’est pas non plus très optimiste, comme il l’a écrit dans un article de blog : « Si et quand des superintelligences artificielles prennent le contrôle du monde, elles pourront se soucier de la valeur de BB(6). Et ensuite, Dieu pourra se soucier de la valeur de BB(7). » Peut-être que les mathématiciens ont vraiment atteint la limite du calculable avec BB(5). Mais qui sait : peut-être que quelqu’un parviendra à surprendre à nouveau les experts.
