Ces derniers temps, recenser les exploits en informatique se réduisait à narrer les derniers progrès de l’intelligence artificielle. Le 2 juillet, l’annonce de la démonstration d’une conjecture vieille de plus de trente ans est venue bouleverser cette litanie. En plus, l’exploit, raconté par le média américain Quanta Magazine, n’est issu ni du monde académique ni de l’industrie. Il a été accompli par une équipe internationale constituée d’une vingtaine de personnes, collaborant à distance, en partie « amateurs », et réunie par le jeune Français Tristan Stérin.
Cofondateur de l’entreprise de logiciels PRGM, il a lancé, en mars 2022, le défi de résoudre un problème qui en a épuisé plus d’un : savoir quel programme informatique, parmi une famille de plus de 16 000 milliards, s’arrête pour donner sa réponse, éliminant de fait les programmes « inutiles » qui continuent ad vitam aeternam. Et surtout trouver la perle rare, celui qui stoppe après le plus grand nombre d’étapes. Le problème a été baptisé « compétition du castor affairé » par le mathématicien hongrois Tibor Rado, en 1962, en hommage aux vertus de l’animal.
« C’est comme la chasse au Pokémon ! » plaisante Tristan Stérin. Quel intérêt ? Ce « jeu », qui illustre comment la complexité jaillit de la simplicité, touche à de profondes questions en mathématiques et en informatique.
Le ruban de Turing
Pour saisir l’enjeu, des rappels s’imposent. En 1936, le Britannique Alan Turing démontre que tout programme, depuis le simple « afficher “bonjour” » aux plus complexes, comme les énormes ChatGPT et consorts, peut se représenter « simplement » par une machine qui porte son nom : un ruban infini, marqué de 0 ou de 1 lorsqu’il passe sous une tête de lecture/écriture. La tête ne peut que changer les symboles 0 ou 1, faire avancer ou reculer le ruban d’une case et changer d’état. Cet « état », qui contient ces trois instructions (écrire 0 ou 1, avancer/reculer, changer d’état), est le logiciel de la machine. Il peut en avoir un, deux ou plus… Une machine à un état peut générer 25 programmes différents. De une à deux, 6 561, et de une à cinq, plus de 16 000 milliards.
Avec ce concept, Turing montre qu’il est impossible de trouver un programme qui dise si un autre programme va s’arrêter ou non. Le problème du castor affairé (« busy beaver » en anglais ou BB pour les intimes) présente une autre impossibilité : calculer le plus grand programme « utile », celui qui fait bouger le plus le ruban avant de s’arrêter et de donner la réponse. Tibor Rado a démontré que cette fonction n’était pas calculable : il est impossible de trouver toutes ces valeurs par une suite d’opérations.
Il vous reste 57.18% de cet article à lire. La suite est réservée aux abonnés.
