Ackermann-Péter : comment trois règles font exploser les nombres

Intervenant 10:00

Bienvenue à tous dans le podcast du magazine Tangente. C'est un immense plaisir de lancer cette nouvelle exploration aujourd'hui.

Intervenant 20:07

Salut tout le monde. Eh oui, je suis ravie d'être là. On a un sujet absolument ahurissant au programme.

Intervenant 10:14

Ahurissant et franchement un peu effrayant. Imaginons, juste un instant, trois petites lignes de code.

Intervenant 20:20

Des simples instructions mathématiques, très basiques.

Intervenant 10:23

C'est ça. Des trucs qui ne demandent de faire que des additions et des soustractions. On fait plus un, on fait moins un. Et c'est tout.

Intervenant 20:30

Vraiment le niveau école primaire en apparence.

Intervenant 10:32

Totalement. Mais si on lance ces lignes inoffensives sur le super ordinateur le plus puissant, bah bam, en une fraction de seconde, le truc génère un arbre de calcul tellement massif que ça ferait exploser n'importe quelle machine.

Intervenant 20:47

La mémoire sature complètement, oui. Le système s'effondre.

Intervenant 10:50

Et pour stocker le résultat final, il faudrait plus de disques durs qu'il n'y a d'atomes dans l'univers connu. C'est un truc de fou.

Intervenant 20:56

C'est le paradoxe ultime de l'informatique théorique en fait. Cette plongée qu'on va faire aujourd'hui, elle est basée sur un excellent article d'Angelo Laplace publié dans les pages de Tangente. Oui, un

Intervenant 11:06

article fascinant qui décortique ce fameux monstre.

Intervenant 21:10

Exactement. Il nous présente cette entité qu'on appelle la fonction d'Ackermann-Péter. C'est un objet mathématique qui, disons qu'il repousse tellement loin les limites de l'abstraction qu'il vient percuter les barrières physiques de notre réalité.

Intervenant 11:23

Rien que ça. Mais du coup, avant d'observer ce crash cosmique, il faut absolument qu'on comprenne comment on a pu construire un moteur pareil.

Intervenant 21:30

Ah bah oui, il faut regarder sous le capot.

Intervenant 11:31

Parce que, historiquement parlant, cette fonction n'a pas été conçue par des pirates informatiques qui cherchaient à détruire des serveurs.

Intervenant 21:38

Non, pas du tout. Ce sont des mathématiciens de génie qui essayaient de répondre à des questions fondamentales sur la logique.

Intervenant 11:44

D'après les sources, tout commence dans la première moitié du XXe siècle, avec l'allemand Wilhelm Ackermann, un élève très brillant du légendaire David Hilbert.

Intervenant 21:54

C'est ça. Il faut se replacer un peu dans le contexte des années 1920. À cette époque, David Hilbert, qui est vraiment une figure tutélaire des maths, lance un programme hyper ambitieux.

Intervenant 12:04

Il voulait tout formaliser,

Intervenant 22:06

non ? Exactement. Il veut fonder toutes les mathématiques sur des bases purement logiques, mécaniques et surtout prévisibles. C'est la grande époque où l'on se pose des questions sur la calculabilité.

Intervenant 12:16

C'est-à-dire ?

Intervenant 22:17

En clair, on se demande si tout problème mathématique peut être résolu par un algorithme défini. Un truc qui exécuterait des étapes finies pour donner un résultat.

Intervenant 12:27

Ok, je vois.

Intervenant 22:28

Donc Ackermann, en 1928, propose initialement une fonction à trois variables pour explorer ses limites. Mais comment dire, c'était un outil très lourd à manier.

Intervenant 12:37

Un peu imbuvable quoi.

Intervenant 22:38

Voilà, très complexe à déchiffrer.

Intervenant 12:40

Et c'est là que l'article de Tangente apporte une précision hyper intéressante. La forme de la fonction qu'on utilise aujourd'hui, celle qui met les ordi à genoux, c'est pas exactement celle

Intervenant 22:49

d'Ackermann. Ah, bien vu ! En 1935, c'est Rosa Péter qui s'en mêle.

Intervenant 12:53

Une mathématicienne hongroise, pionnière absolue de la théorie des fonctions récursives.

Intervenant 22:58

Tout à fait. Elle s'empare du concept et réalise une simplification magistrale. Elle réduit la bête de trois à seulement deux variables.

Intervenant 13:06

Qu'on va appeler M et N, du

Intervenant 23:08

coup. Exactement. Et plus tard, en 48, l'américain Raphaël Robinson épure une dernière fois les conditions de départ. C'est pour ça qu'on devrait rigoureusement parler de la fonction d'Ackermann-Péter.

Intervenant 13:20

Bon alors, cette fameuse fonction, elle tient en seulement trois petites règles, c'est ça ?

Intervenant 23:24

Trois petites règles de définition, oui. Et c'est cette architecture super minimaliste qu'il faut disséquer pour comprendre pourquoi ça explose.

Intervenant 13:32

Vas-y, je t'écoute. On imagine notre fonction, notée grand A, avec nos deux paramètres d'entrée, M et N.

Intervenant 23:39

Alors, la première règle, c'est la condition de sortie. Le seul moment où la machine produit enfin un résultat chiffré.

Intervenant 13:45

Le fameux plus 1.

Intervenant 23:46

C'est ça. Si le premier paramètre m vaut 0, la fonction s'arrête et elle donne comme résultat le paramètre n auquel on ajoute 1. Donc a de 0 et n, ça donne n plus 1.

Intervenant 13:58

C'est vraiment la seule opération mathématique du système entier. Tout le reste, c'est juste de la manipulation de variables.

Intervenant 24:04

Absolument.

Intervenant 14:05

Donc, si je donne à la fonction les valeurs 0 et 5, elle regarde la première règle et se dit « ah, m vaut 0, parfait, je prends n qui vaut 5, j'ajoute 1, la réponse est 6 ».

Intervenant 24:17

C'est extrêmement basique, oui. Jusque-là, tout va bien.

Intervenant 14:20

Ça ne va pas faire fondre un processeur, ça.

Intervenant 24:22

C'est précisément l'illusion de la simplicité. Passons à la deuxième règle. Si m est strictement supérieur à 0, mais que n vaut 0. Ok, là

Intervenant 14:31

il se passe quoi ?