on July 26, 2025
En attendant Gödel, les logiciens pensaient que chaque assertion pouvait, sur la base d’un système d’axiomes, être démontrée fausse ou correcte. Or, la philosophe grec Épiménide avait énoncé un paradoxe troublant. Quand il prononce la phrase autoréférentielle : “Je mens”, si c’est un mensonge, alors il dit la vérité et il ne ment pas, mais s’il ne ment pas, alors il dit la vérité et il ment… Impossible de déterminer la vérité ou la fausseté de la phrase. De telles propositions, dites “indécidables”, expriment quelque chose au sujet d’elles-mêmes. En 1931, Gödel mit de l’ordre dans les systèmes d’axiomes mathématiques par le second théorème d’incomplétude : “il existe des énoncés que l’on ne saura ni démontrer ni réfuter dans une théorie donnée”.
Le mathématicien Jean-Paul Delahaye nous fait parcourir l’univers des propositions indécidables, y compris une “preuve” de l’existence de Dieu, énoncée pour la première fois par Anselme de Cantorbery. Certaines sont encore examinées aujourd’hui.
L’auteur montre comment les logiciens Alan Turing ou Alonzo Church, inspirés par les travaux de Gödel, ont élargi le champ des indécidables pour répondre par la négative à la question de Hilbert : “Existe-t-il un algorithme capable de déterminer, pour tout énoncé mathématique bien formulé donné en entrée, si ce dernier est vrai ou faux ?” D’autres domaines mathématiques, comme la théorie de la complexité, ont apporté leur pierre à l’édifice.
Les propositions indécidables sont rares et de construction difficile : l’une d’entre elles, fondée sur ce qui était un amusement, les nombres “fusibles”, est un chef-d’œuvre de concision et de facilité de compréhension.
Partez pour ce voyage initiatique qui s’aventure dans des contrées de la logique dont l’exploration continue.
Jean-Paul Delahaye, professeur émérite en informatique (Université de Lille), chercheur CRIStAL, auteur de la rubrique Logique et calcul dans Pour la Science
More...
français
English