Case study: solving P-99 with LPTP and an LLM

Imaginez un monde où les ordinateurs ne se contentent pas de suivre des instructions rigides et robotiques, mais peuvent réellement comprendre la manière confuse et imprécise dont les humains décrivent les problèmes. C'est la frontière de l'Intelligence Artificielle, et plus précisément d'une branche appelée Modèles de Langage de Grande Taille (LLM). Considérez un LLM comme un étudiant super intelligent et incroyablement cultivé qui a lu presque tout ce qui existe sur Internet. Si vous lui demandez d'écrire une histoire, il peut le faire ; si vous lui demandez d'écrire du code, il peut le faire aussi. Mais il y a un piège : cet étudiant est sujet aux « hallucinations », ce qui signifie qu'il peut inventer des faits avec assurance ou écrire du code qui semble parfait mais qui, secrètement, plante lorsque vous essayez de l'exécuter.

Pour corriger cela, les scientifiques utilisent la Vérification Formelle, qui est comme un professeur de mathématiques extrêmement strict qui vérifie chaque étape du devoir d'un élève pour s'assurer qu'il est logiquement impossible de se tromper. Dans le monde de l'informatique, il existe un ensemble de défis célèbres appelés les 99 Problèmes Prolog (ou P-99). Ceux-ci sont comme des « entraînements de musculation » pour la programmation logique, un style de codage où l'on décrit ce que l'on veut qu'il se passe plutôt que comment le faire étape par étape. La grande question que les chercheurs se posent est la suivante : pouvons-nous laisser l'étudiant IA écrire le code à partir d'une simple description en anglais, puis faire en sorte que le professeur de mathématiques vérifie instantanément s'il est réellement correct ? Ce document explore exactement cette expérience, mêlant la liberté créative de l'IA à la sécurité de fer de la logique formelle.

---

L'Expérience : Un Duo de Codage avec un Professeur Strict

Dans cette étude, une équipe de chercheurs a décidé de tester une nouvelle façon de travailler appelée « vibe-coding » mélangée au « vericoding ». Imaginez le « vibe-coding » comme le fait de demander à un ami créatif de vous construire une cabane dans un arbre à partir d'un croquis sommaire que vous avez dessiné sur une serviette en papier. Vous dites : « Je veux une cabane avec un toboggan et une porte secrète », et il commence simplement à construire. C'est rapide et amusant, mais le résultat peut être bancal. Le « vericoding » est l'opposé : c'est comme embaucher un architecte qui exige des plans, des tests de résistance et des inspections de sécurité avant de planter le moindre clou.

Les chercheurs voulaient voir s'ils pouvaient combiner ces deux approches. Ils ont utilisé un modèle d'IA nommé Claude (spécifiquement la version Opus 4.6) pour jouer le rôle du constructeur créatif. Ils lui ont donné les 33 premiers problèmes de la célèbre liste P-99, qui sont écrits en anglais simple et informel. Par exemple, un problème dit simplement : « Trouver le dernier élément d'une liste ».

Le travail de l'IA consistait à :

1. Écrire le code Prolog pour résoudre le problème.
2. Écrire un fichier de test pour vérifier si le code fonctionne sur des exemples.
3. Écrire une preuve formelle pour garantir mathématiquement que le code est sûr, correct et qu'il s'exécutera toujours jusqu'au bout.

Pour vérifier les preuves, ils ont utilisé un outil appelé LPTP (Logic Program Theorem Prover). Considérez LPTP comme le professeur de mathématiques strict qui refuse d'accepter un « ça a l'air correct » comme réponse. Il exige une dérivation logique étape par étape pour chaque affirmation.

Les Résultats : Un Mélange de Magie et de Mathématiques

L'expérience a été un succès, mais ce n'était pas une baguette magique. L'équipe a réussi à résoudre 33 exercices sur 88 (environ 37,5 %) en utilisant cette méthode. Voici ce qui s'est passé en coulisses :

• La Partie Créative (Vibe-Coding) : L'IA était étonnamment douée pour le codage initial. Elle a écrit 58 procédures logiques (le code réel) et 508 cas de test en seulement quelques minutes par problème. Elle comprenait les instructions en anglais et générait un code qui fonctionnait correctement.
• La Partie Stricte (Vericoding) : C'est là que le vrai travail a commencé. L'IA devait prouver que son code était correct. Elle a généré 257 lemmes (petits faits mathématiques) et a écrit un nombre colossal de 11 800 lignes de preuve.
• La Touche Humaine : Les chercheurs ne se sont pas contentés de laisser l'IA agir librement. Ils ont vérifié manuellement chaque fichier. Ils ont exécuté les tests, lu les énoncés logiques et relancé les preuves avec LPTP. Si l'IA bloquait ou écrivait une preuve qui n'avait pas de sens, les humains intervenaient pour lui donner un indice. Par exemple, pour un problème concernant la recherche du dernier élément d'une liste, les humains ont dû demander à l'IA : « Hé, comment cela se connecte-t-il à la fonction append ? » pour l'aider à formuler la bonne preuve.

Les Grandes Découvertes

Le document révèle plusieurs points clés sur cette nouvelle façon de travailler :

1. L'IA devient douée pour le « Vibe-Coding » : L'IA pouvait prendre une description vague en anglais et la transformer très rapidement en un code Prolog fonctionnel. Elle a même évité les astuces « impures » que l'on trouve souvent dans le code Prolog du monde réel, en s'en tenant à un style logique strict que le professeur de mathématiques (LPTP) pouvait comprendre.
2. L'IA a besoin d'un coup de pouce pour le « Vericoding » : Bien que l'IA puisse générer le code facilement, prouver pourquoi il était correct était plus difficile. Pour les propriétés fonctionnelles complexes (comme prouver que le code fait exactement ce qu'il est censé faire), l'IA avait parfois besoin que les chercheurs humains lui expliquent d'abord la logique en langage clair. Une fois que les humains lui avaient donné un indice, l'IA pouvait le formaliser et le prouver.
3. Ce n'est pas encore un problème « résolu » : L'équipe n'a pas résolu l'ensemble des 99 problèmes. Certains n'ont pris à l'IA que 15 minutes (comme le simple problème du « dernier élément »), tandis que d'autres ont nécessité plusieurs heures (comme le problème de la « décomposition en facteurs premiers »). Les chercheurs notent que pour les problèmes les plus difficiles, l'IA a encore du mal à élaborer des stratégies de preuve par elle-même sans guidage humain.

Un Aperçu du Futur : La Connexion « MCP »

Le document décrit également un nouvel outil qu'ils construisent appelé le Model Context Protocol (MCP). Actuellement, l'IA et le professeur de mathématiques (LPTP) communiquent via des fichiers et des documents texte, ce qui ressemble un peu à l'envoi de lettres aller-retour. Le nouvel outil MCP est comme de donner une ligne téléphonique directe. Cela permet à l'IA de demander de l'aide au professeur de mathématiques en temps réel, de vérifier son propre travail instantanément et de corriger les erreurs sans attendre l'intervention d'un humain. Ils ont testé cela avec d'autres modèles d'IA (comme Gemini) et ont constaté que, bien que certains modèles puissent générer les idées de preuves, seul Claude était capable de générer avec succès les preuves valides qui passaient les contrôles stricts.

L'Essentiel à Retenir

Ce document montre que nous entrons dans une ère où l'IA peut agir comme un partenaire créatif dans l'écriture de code logique complexe, mais qu'elle a encore besoin d'un « pilote » humain pour la guider à travers les parties les plus difficiles. L'IA peut écrire le code et même rédiger les preuves mathématiques, mais elle se perd parfois dans les détails. En combinant la vitesse et la créativité de l'IA avec un vérificateur de preuves formelles comme LPTP, les chercheurs ont créé un système qui attrape les erreurs de l'IA avant qu'elles ne deviennent de vrais bugs. Ce n'est pas encore une machine de « réparation automatique totale », mais c'est un nouvel outil puissant qui rend l'écriture de logiciels fiables plus rapide et plus sûre que jamais.