Busy Beaver : l’enquête sur des nombres incalculables

Intervenant 10:00

Bonjour et bienvenue sur le podcast du magazine Tangente. Aujourd'hui, on a une analyse d'un article absolument fascinant au programme. Préparez-vous, parce qu'on va parler de nombres tellement immenses qu'ils brisent littéralement les mathématiques.

Intervenant 20:13

Ouais, bonjour. C'est clair que le sujet du jour donne le vertige et ça va très vite escalader, tu vas voir.

Intervenant 10:19

Carré vrant. Alors, pour commencer, on donne le ton avec un petit jeu. Genre, on prend une calculatrice, on multiplie un par deux, on ajoute un et on recommence en boucle. C'est un jeu d'enfant, non ?

Intervenant 20:29

Oui, c'est super basique. Sauf que si on pousse cette logique assez loin, on ne fait pas que planter la calculatrice, on crée une véritable faille dans la logique mathématique elle-même.

Intervenant 10:39

Une faille de dingue. Et pour comprendre comment un simple nombre peut briser les maths, il faut d'abord redéfinir un truc important, à savoir qu'est-ce qu'un résultat calculable en fait ?

Intervenant 20:49

Exactement. Parce que souvent, on a l'impression que face à un calcul très lourd, il suffit d'avoir un ordinateur avec une mémoire illimitée et de juste le laisser tourner.

Intervenant 10:58

Oui, on se dit que même avec des fonctions qui empilent des exponentielles de façon monstrueuse, ça finira bien par sortir un résultat.

Intervenant 21:05

Voilà. En théorie, ça reste calculable. Le processus sera infiniment long, certes, mais la machine finira par crasher sa réponse et s'arrêter. Sauf que l'article nous amène sur un tout autre terrain avec la fonction du Busy Beaver.

Intervenant 11:19

Ah, le fameux castor affairé. C'est basé sur la machine de Turing, c'est bien ça ?

Intervenant 21:23

C'est ça. Ce modèle théorique d'ordinateur qui lit et écrit des symboles sur un ruban infini, le tout en suivant un nombre hyper précis de règles qu'on appelle ses états.

Intervenant 11:32

Donc, la question centrale, c'est de se dire, parmi toutes les machines possibles ayant, disons, cinq états, quelle est celle qui va écrire le plus grand nombre de symboles avant de s'arrêter définitivement ? C'est un peu comme chercher l'employé de bureau le plus frénétique, quoi.

Intervenant 21:46

J'adore cette analogie. Imagine qu'on donne à cet employé un manuel d'instruction de seulement cinq pages.

Intervenant 11:52

Et le but, ce n'est pas de l'occuper dans le vide éternellement, mais qu'il abatte un maximum de travail, qu'il rédige le plus de rapports possible juste avant de démissionner pour toujours.

Intervenant 22:00

Parfaitement résumé. Et les valeurs que ça donne sont vertigineuses. Avec un manuel de quatre pages, donc quatre états, le maximum de symboles générés, c'est 107.

Intervenant 12:10

107, ça va. C'est super modeste.

Intervenant 22:13

Bah oui, mais avec 5 États, on frôle déjà les 47 millions. Et avec 6 États, tiens-toi bien, on obtient un suivi de plus de 18 000

Intervenant 12:22

zéros. Attends, 18 267 zéros, très exactement selon l'article. C'est astronomique. Mais le vrai choc, ça arrive avec le castor à 7 États, le bébé 7.

Intervenant 22:33

Ah ouais, parce que ce nombre-là, il est totalement et définitivement inconnu.

Intervenant 12:37

Mais pourquoi ? Je veux dire, on a des supers calculateurs aujourd'hui, on peut pas juste lancer toutes les combinaisons possibles de machines à cet état en même temps et juste attendre de voir celle qui s'arrête en dernier ?

Intervenant 22:46

Eh ben non, parce qu'on parle plus du tout ici d'un manque de puissance de calcul. La croissance de cette fonction Busy Beaver dépasse toute fonction calculable.

Intervenant 12:54

Elle va trop vite en gros.

Intervenant 22:55

C'est ça. Elle crève la vitesse limite de l'arithmétique. On bascule carrément dans le non calculable. Et la raison, c'est qu'on se heurte violemment au problème de l'arrêt d'Alan Turing.

Intervenant 13:04

Le fait qu'on ne puisse pas prédire si un programme va s'arrêter.

Intervenant 23:07

Exactement. Si on lance toutes ces machines à cet état, certaines s'arrêtent vite, d'autres tournent pendant des mois. Mais comment savoir si une machine va finir par s'arrêter demain ou si elle est juste coincée dans une boucle infinie ?

Intervenant 13:20

C'est impossible à savoir. Turing a prouvé mathématiquement qu'aucun algorithme universel ne peut faire ça.

Intervenant 23:26

Voilà. Et c'est là que tout se connecte. Parce que si, par miracle, on connaissait la valeur du castor pour cet état, disons que c'est un milliard, on saurait avec certitude qu'il suffit d'attendre un milliard d'étapes.

Intervenant 13:39

Ah, je vois. Et si une machine ne s'est pas arrêtée à ce stade précis, c'est la preuve absolue qu'elle tourne en boucle à l'infini.

Intervenant 23:45

C'est ça. Connaître ce chiffre nous donnerait en fait la clé pour contourner le problème de l'arrêt.

Intervenant 13:50

Sauf que comme le problème de l'arrêt est irrésoluble, connaître ce castor l'est tout autant. D'ailleurs, l'article relie cet impasse à un autre truc énorme, les théorèmes d'incomplétude de Kurt Gödel.

Intervenant 24:01

Godel, oui, publié en 1931. Pour faire simple, il a démontré que tout système mathématique est comme une boîte fermée. Il y a des vérités à l'intérieur qu'il est juste impossible de prouver sans sortir de la boîte.

Intervenant 14:14

Donc la fonction Busy Beaver, elle évolue de l'autre côté de nos propres murs logiques. L'article donne un super exemple avec le castor à 748 états.

Intervenant 24:23

Oui, pour le calculer, il faudrait prouver la cohérence de l'arithmétique de Peano, le système formel qui décrit nos nombres entiers.

Intervenant 14:31

Or, on vient de le dire, la boîte de l'arithmétique de Peano ne peut pas prouver sa propre solidité de l'intérieur.

Intervenant 24:37

Exactement. Dès qu'on essaye de chasser des castors de plus en plus grands, on percute violemment les murs de notre propre logique. C'est ininfranchissable.

Intervenant 14:46

Mais du coup, face à ces murs-là, comment la discipline mathématique survit-elle ? L'article résume ça avec une image super poétique, je trouve.

Intervenant 24:54

La tour sans sommet, c'est ça ?

Intervenant 14:56

Ouais. L'idée que les mathématiques ne sont pas un édifice achevé. À chaque fois qu'on crée un nouveau système logique plus puissant, on sort de la boîte précédente pour atteindre un étage supérieur.

Intervenant 25:06

On parvient alors à calculer de nouveaux castors, c'est vrai. Mais en faisant ça, on forge instantanément une nouvelle boîte avec un tout nouveau mur de Gödel.

Intervenant 15:15

On n'en a jamais fini, en fait. Sachant que de simples additions et multiplications cachent des monstres inconcevables, quelles autres vérités fondamentales de notre univers pourraient patienter de l'autre côté de cet horizon non calculable, attendant une logique que l'on n'a tout simplement pas encore inventée ?