Dans la préface du Principia Mathematica de Newton, Voltaire écrivait « [qu’]il a fallu que les modernes créassent de nouveaux mots pour rendre ces nouvelles idées ». Aussi sait-on depuis longtemps que le langage, quelle qu’en soit la forme, permet de faire germer les idées tout comme les idées font naître de nouveaux langages.

Au début du XX^e siècle, le mathématicien allemand David Hilbert s’est demandé s’il existait des algorithmes pour résoudre les problèmes de décisions mathématiques.

Définir la décidabilité d’un problème est lui-même un problème binaire.

Par exemple, « cette formule arithmétique est-elle vraie ? ». Oui ? Non ? Nous vous laissons en débattre.

Un problème est décidable dès lors qu’il existe une machine qui renvoie « oui » à toute proposition valide au problème, et « non » à toutes les autres. C’est là que les ennuis commencent, car parfois le langage rend les choses in fine indécidables . Dans certains cas, le nombre infini de propositions ou la complexité du problème ne permet de définir sa décidabilité, il est donc indécidable.

La suite de notre périple a lieu en 1931, lorsque Kurt Godël publie un article intitulé Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. Il y énonce puis démontre le théorème suivant : « Dans n’importe quelle théorie […] cohérente et capable de formaliser l’arithmétique, on peut construire un énoncé arithmétique qui ne peut être ni démontré, ni réfuté dans cette théorie ». Ce qui en substance, signifie que le problème de décision pris en exemple plus haut « cette formule arithmétique est-elle vraie ? » peut être indécidable par son énoncé dans la langue avec laquelle on exprime l’arithmétique.

Néanmoins, si un problème est indécidable dans les limites d’une langue, il ne l’est pas nécessairement dans une autre.

Ce théorème mit fin, d’une part au rêve de David Hilbert, et d’autre part montra les limites de nos langues et langages, y compris en mathématiques qui se trouvent pourtant être une version extrêmement minimaliste des langages naturels que nous utilisons tous les jours.

Il existera toujours des problèmes que nous ne pourrons résoudre si nous ne changeons pas la manière de les exprimer. Peut-être qu’au-delà de ce que disait Voltaire, il aurait fallu que nous créassions de nouvelles langues pour rendre ces nouvelles idées.

IP7

Image :

Portrait de Kurt Gödel lorsqu’il était étudiant à Vienne. Crédit : Wikimedia Commons.