décidabilité et indécidabilité

décidabilité
indécidabilité

FONDEMENTS DES MATHEMATIQUES

En logique mathématique le terme décidabilité est lié à la décidabilité logique et à la décidabilité algorithmique.
L’indécidabilité est la négation de la décidabilité.
Une proposition en logique mathématique est décidable si on peut démontrer soit sa négation soit elle-même. D’après le théorème de complétude, 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 d’autres modèles où elle est vraie.