Logique et ensemblesNotion · Glossaire
décidabilité et indécidabilité
En logique mathématique, une proposition est décidable dans une théorie formelle donnée si cette théorie démontre la proposition ou sa négation ; elle est indécidable si elle ne démontre ni l’une ni l’autre. En informatique, un problème de décision est décidable s’il existe un algorithme qui, pour toute instance, termine en un nombre fini d’étapes et répond correctement « oui » ou « non » ; sinon, il est indécidable. Cette distinction sépare ce qu’une théorie permet de prouver de ce qu’un algorithme peut toujours décider.
Sommaire
Ce que vous allez apprendre
- Séparer l’indécidabilité relative à une théorie de l’indécidabilité d’un problème algorithmique.
- Suivre la contradiction qui interdit un décideur universel du problème de l’arrêt.
- Éviter de confondre absence de preuve connue, vérité dans un modèle et indécidabilité.
En clair
Imaginez un programme chargé d’examiner n’importe quel autre programme et d’annoncer s’il finira par s’arrêter. Pour certaines familles de programmes, cette vérification est possible. Mais aucune recette universelle ne donne toujours la bonne réponse et ne termine elle-même à chaque fois : le problème général de l’arrêt est indécidable.
En logique, l’idée est voisine mais différente. Une proposition est décidable lorsqu’une théorie permet d’en démontrer la vérité ou la fausseté. Elle est indécidable dans cette théorie lorsqu’aucune des deux démonstrations n’y est possible.
Définition
La décidabilité possède deux sens qu’il faut préciser. En logique mathématique, on fixe d’abord une théorie formelle, notée T, et une proposition, notée φ. La proposition φ est décidable dans T lorsque T démontre φ ou démontre sa négation. Elle est indécidable dans T lorsque T ne démontre ni φ ni sa négation. Le verdict est donc relatif à la théorie choisie.
Pour une théorie consistante du premier ordre en logique classique et une phrase φ, le théorème de complétude de Gödel relie cette absence de preuve aux modèles : si φ est indécidable dans T, certains modèles de T satisfont φ et d’autres satisfont sa négation. Cette formulation ne dit pas que φ est dépourvue de sens. Elle dit que les axiomes et les règles de T ne tranchent pas la question.
En informatique théorique, un problème de décision est décidable lorsqu’il existe un algorithme qui, pour chaque instance admise, s’arrête après un nombre fini d’étapes et fournit la bonne réponse « oui » ou « non ». Il est indécidable lorsqu’un tel algorithme universel n’existe pas. Les résultats de Church et de Turing en 1936 placent le problème de l’arrêt au cœur de cette limite. Le dixième problème de Hilbert, qui porte sur l’existence de solutions d’équations diophantiennes, est un autre exemple d’indécidabilité algorithmique.
Un exemple, pas à pas
Supposons qu’un algorithme universel H existe. Ses données sont la description d’un programme P et une entrée e. H doit toujours terminer et annoncer correctement si P s’arrête lorsqu’il reçoit e.
Étape 1. Construisons un programme D qui soumet à H la description d’un programme prise aussi comme entrée de ce programme.
Étape 2. D fait volontairement le contraire du verdict de H : si H annonce un arrêt, D boucle ; si H annonce une boucle, D s’arrête.
Étape 3. Exécutons D avec sa propre description. Si H prévoit que D s’arrête, D boucle. Si H prévoit que D boucle, D s’arrête. Chaque réponse possible de H est donc contredite.
Le schéma résume les deux branches de ce raisonnement diagonal : la règle de D inverse exactement le verdict annoncé par H.
L’hypothèse de départ est impossible : aucun H ne peut décider correctement l’arrêt de tout programme sur toute entrée. Le contrôle est refaisable en examinant séparément les deux seuls verdicts possibles, « arrêt » et « boucle » ; chacun produit sa propre contradiction.
En pratique
En logique, on commence par nommer la théorie formelle utilisée. On cherche ensuite une preuve de la proposition ou de sa négation. Si aucune n’existe dans cette théorie, le bon constat est l’indécidabilité relative à cette théorie, et non une absence générale de vérité.
En informatique théorique, on vérifie qu’un algorithme proposé termine pour toutes les instances admises. Quelques essais réussis ne suffisent pas. Face à un problème général indécidable, on peut chercher une famille d’instances plus restreinte pour laquelle une procédure de décision existe.
Pour une équation diophantienne, le dixième problème de Hilbert demande une méthode universelle décidant l’existence d’une solution entière. Son indécidabilité interdit une procédure unique qui termine correctement dans tous les cas ; elle n’interdit pas de résoudre certaines équations particulières.
À ne pas confondre
Indécidable et non encore démontré. Une recherche inachevée signifie seulement qu’aucune preuve n’est connue à ce stade. L’indécidabilité dans une théorie exige davantage : ni la proposition ni sa négation ne sont démontrables dans cette théorie.
Décidabilité logique et décidabilité algorithmique. La première porte sur ce qu’une théorie prouve à propos d’une proposition. La seconde porte sur l’existence d’un algorithme qui termine et répond correctement pour chaque instance d’un problème. Le problème de l’arrêt relève du second sens.
Vérité et démontrabilité. Dans un modèle donné, une proposition reçoit une valeur de vérité. Être démontrable signifie qu’elle découle des axiomes et des règles de la théorie. Pour une théorie consistante du premier ordre en logique classique et une phrase φ indécidable dans cette théorie, certains modèles de la théorie satisfont φ et d’autres satisfont sa négation.
Limites et pièges
Oublier de préciser la théorie. Une proposition peut être indécidable dans une théorie donnée et devenir décidable après l’ajout d’un axiome. Le symptôme est une affirmation absolue sans cadre formel ; il faut toujours nommer la théorie concernée.
Confondre modèle et théorie. L’indécidabilité logique ne signifie pas qu’une proposition est simultanément vraie et fausse dans un même modèle. Elle signifie que la théorie admet des modèles qui ne lui attribuent pas tous la même valeur de vérité.
Accepter un algorithme qui ne termine pas toujours. Pour décider un problème, la bonne réponse ne suffit pas : la procédure doit aussi s’arrêter sur chaque instance admise. Une seule instance sur laquelle elle boucle empêche de la qualifier d’algorithme de décision.
Étendre abusivement un résultat général. L’indécidabilité du problème de l’arrêt concerne les programmes et entrées arbitraires. Elle n’empêche pas de décider l’arrêt pour des familles particulières. Il faut donc vérifier le domaine exact avant de conclure qu’aucune analyse n’est possible.
Pour aller plus loin
Problème de l’arrêt. Retrouvez la question algorithmique qui fournit l’exemple fondateur d’un problème indécidable.
Algorithme. Précisez ce qu’exigent une procédure finie, ses entrées et son résultat avant d’étudier sa décidabilité.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres