Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Indécidable

Le terme d'indécidabilité recouvre plusieurs concepts liés en logique mathématique, formalisant l'idée qu'on ne peut pas conclure en un sens comme dans l'autre.

Indécidabilité d'une proposition dans un système logique

Aspect syntaxique

Une proposition (un énoncé mathématique) est dite indécidable dans un système logique s'il est impossible de la déduire, ou de déduire sa négation, à l'aide des règles du système.

En termes plus concrets, cela veut dire qu'on demande au système de fournir une conclusion sans qu'on n'ait fourni suffisamment d'hypothèses. Ainsi, l'âge du capitaine d'un bateau est indécidable en fonction du tonnage et de la vitesse du navire.

Le théorème d'incomplétude de Gödel montre que dans tout système logique suffisamment puissant pour représenter l'arithmétique de Peano (l'arithmétique usuelle), il existe forcément des propositions indécidables.

Une proposition indécidable, ou sa négation, peut être ajoutée à un système cohérent pour former un autre système cohérent. C'est ainsi que l'on ajoute souvent l'axiome du choix aux axiomes de Zermelo-Fraenkel (ZF) pour former le système ZFC.

Une théorie est dite complète si elle n'admet pas de proposition indécidable.

Aspect sémantique

Une proposition est indécidable dans une théorie s'il existe des modèles de la théorie où la proposition est fausse et des modèles où elle est vraie.

Dans une théorie où il y a équivalence entre être démontrable et être vrai dans tout modèle (voir théorème de complétude), l'aspect sémantique est équivalent à l'aspect syntaxique.

Indécidabilité d'un problème de décision

Un problème de décision est dit indécidable s'il n'existe pas d'algorithme (ou de machine de Turing) qui le décide. Par exemple, le problème de l'arrêt est indécidable.

Les deux concepts sont liés : l'ensemble des propositions dérivables à partir d'une théorie finiment axiomatisée est récursivement énumérable, de même que l'ensemble des propositions de négation démontrable. L'ensemble des propositions décidables est donc décidable. On en déduit donc que dans un système sans proposition indécidable, le problème de décider si une proposition est démontrable est décidable.