Auto formalisation of Goedel's Second Incompleteness Theorem in Binary Recursive Arithmetic

Imaginez que vous essayiez de construire un robot parfait et capable de s'auto-vérifier pour vérifier ses propres devoirs de mathématiques. Ce robot, que nous appellerons BRA, est très intelligent mais suit des règles extrêmement strictes et simples. Il peut additionner, soustraire et vérifier si des choses sont égales, mais il ne possède pas de module de « bon sens ».

Le document que vous lisez est un rapport sur une expérience où un chercheur humain (Thierry Coquille) s'est associé à une IA (Claude) pour enseigner à ce robot une leçon très célèbre et très difficile : le second théorème d'incomplétude de Gödel.

Voici l'histoire de cette expérience, décomposée en parties simples.

1. L'objectif : Le robot peut-il prouver qu'il est sûr ?

Le second théorème de Gödel est un peu comme le « paradoxe du menteur » pour les systèmes mathématiques. Il dit : « Si un système est cohérent (il ne prouve jamais de choses fausses), il ne peut pas prouver sa propre cohérence. »

En d'autres termes, si notre robot BRA fait réellement des mathématiques correctement, il ne pourra jamais rédiger une preuve disant : « Je suis un bon robot. » S'il pouvait prouver cela, il serait en réalité défectueux. L'objectif de ce projet était de construire une version numérique de cette preuve à l'intérieur d'un programme informatique appelé Agda, en utilisant l'IA pour écrire le code.

2. La première tentative : Le succès « de façade »

L'équipe a commencé par demander à l'IA de lire un vieil article d'un mathématicien nommé Rose et d'essayer de prouver le théorème en se basant sur celui-ci.

• Ce qui s'est passé : L'IA a travaillé dur pendant des jours et a produit une « preuve ». Cela avait l'air impressionnant !
• Le problème : L'IA avait été trompée. Le vieil article qu'elle lisait contenait une erreur (un théorème faux). L'IA a suivi les instructions à la lettre, mais parce que le point de départ était erroné, le résultat était une « preuve » de quelque chose qui ressemblait au théorème de Gödel, mais qui était en fait un non-sens.
• La leçon : Cela a montré que l'IA est excellente pour suivre la logique, mais si vous lui donnez une mauvaise carte, elle vous mènera joyeusement à la mauvaise destination. Vous ne pouvez pas simplement faire confiance à l'IA pour vous dire quoi prouver ; vous devez connaître la destination vous-même.

3. La vraie tentative : Réparer la carte

Après l'échec, l'équipe est passée à un ensemble de notes plus fiables écrites par un mathématicien nommé R. Guard. Ces notes étaient comme une carte au trésor avec des pièces manquantes et des coquilles.

• Le défi : Les notes de Guard dataient de 1963. Elles étaient précises mais omettaient de nombreux petits détails évidents qu'un mathématicien humain remplirait automatiquement. Par exemple, Guard supposait que le lecteur savait comment gérer les « numéraux » (les nombres comme 1, 2, 3) à l'intérieur du cerveau du robot.
• Le rôle de l'IA : Le chercheur humain n'a pas écrit une seule ligne de code. Au lieu de cela, il a agi comme un « traducteur » ou un « architecte ». Il disait à l'IA : « Voici la pièce manquante. Voici la règle. Maintenant, écris le code. »
• Le résultat : L'IA a réussi à écrire 50 000 lignes de code à partir de zéro. Elle a construit tout le robot, la preuve et le système de vérification sans qu'aucun humain ne tape le code. Le résultat final est une preuve vérifiée par machine montrant que le robot BRA ne peut pas prouver sa propre sécurité.

4. Les astuces cachées (La « recette secrète »)

Le document met en lumière plusieurs astuces ingénieuses que l'IA a dû apprendre pour que cela fonctionne, lesquelles étaient cachées dans les anciennes notes :

• Le problème de la « boîte imbriquée » : Le robot devait vérifier son propre historique. Imaginez essayer de lire un livre tout en écrivant simultanément ce même livre. L'IA a dû construire une « bande d'historique » spéciale à l'intérieur du cerveau du robot. Il s'est avéré que les outils de base du robot n'étaient pas conçus pour cela, l'IA a donc dû inventer une structure complexe de type « poupées russes » pour permettre au robot de se souvenir de ses étapes passées.
• La règle de la « boîte fermée » : Le robot doit traiter les nombres (comme 5) comme des « boîtes fermées » qui ne peuvent pas être modifiées par substitution. Les anciennes notes supposaient que cela était évident. L'IA a dû recevoir l'instruction explicite de prouver que « 5 est une boîte fermée » avant de pouvoir poursuivre.
• Le raccourci « hypothétique » : Le robot travaille de manière très rigide (logique de type Hilbert) où il ne peut pas facilement dire « Si X est vrai, alors Y ». L'IA a utilisé une astuce ingénieuse (appelée le « lift de Carneiro ») pour envelopper chaque énoncé dans une enveloppe « Si... », permettant au robot de simuler un raisonnement complexe sans enfreindre ses propres règles.

5. Pourquoi cela importe

Il ne s'agit pas seulement de prouver un théorème mathématique. C'est un test grandeur nature pour l'avenir de la collaboration entre l'humain et l'IA.

• L'humain est l'architecte : L'humain a fourni la vision, la carte correcte et la capacité de repérer quand l'IA déviait de sa trajectoire (comme dans la première tentative ratée).
• L'IA est le maçon : L'IA a fait le gros du travail, posant chaque brique de la preuve de 50 000 lignes.
• La découverte : Le processus a révélé que les anciennes notes mathématiques étaient en fait « négligentes » par endroits. En forçant l'IA à écrire un code qui doit être parfait, l'équipe a découvert des hypothèses cachées et des erreurs de frappe dans le texte original de 1963 qui avaient été négligées pendant des décennies.

Résumé

Considérez ce projet comme la construction d'une voiture autonome. Le conducteur humain connaissait la destination (le théorème de Gödel) et les règles de la route. L'IA était le constructeur de moteur qui assemblait la voiture.

• Au début, l'IA a essayé de construire la voiture en se basant sur un plan défectueux et a construit un véhicule qui ressemblait à une voiture, mais qui ne roulait pas.
• Ensuite, ils ont changé pour un meilleur plan. L'IA a construit une voiture parfaite et fonctionnelle.
• En cours de route, ils ont réalisé que le plan comportait des instructions manquantes, ils ont donc dû inventer de nouvelles pièces pour faire fonctionner la voiture.

Le résultat est une preuve entièrement vérifiée et vérifiée par machine montrant qu'un système mathématique spécifique ne peut pas prouver sa propre cohérence, obtenue entièrement grâce à une collaboration où l'humain a guidé l'IA, et l'IA a effectué l'écriture.