décidabilité

Cet article est extrait de l'ouvrage Larousse « Dictionnaire de la philosophie ».

Logique

1. Propriété satisfaite par une formule qui est démontrable ou réfutable dans une théorie (ce n'est pas une propriété intrinsèque : une formule peut être décidable dans une théorie et pas dans une autre). – 2. Propriété satisfaite par un ensemble lorsqu'il y a un algorithme (« procédure de décision ») permettant de déterminer mécaniquement en un nombre fini d'étapes si un objet donné appartient ou non à cet ensemble ; ainsi, l'ensemble des nombres premiers est décidable. – 3. Propriété satisfaite par une propriété lorsque l'ensemble des objets qui la satisfont est décidable ; ainsi, la propriété « être un nombre premier » est décidable. – 4. Propriété d'une théorie ou d'un système d'axiomes dans lesquels l'ensemble des théorèmes est décidable ; ainsi, le calcul propositionnel est décidable, et l'arithmétique de Peano ne l'est pas.

Parmi les propriétés indécidables, certaines sont semi-décidables, c'est-à-dire qu'il existe une procédure effective qui délivre un verdict positif lorsqu'on l'applique à un objet qui possède la propriété, mais qui peut ne donner aucune réponse lorsqu'on l'applique à un objet qui ne la possède pas ; ainsi, la propriété « être un théorème du calcul des prédicats » est semi-décidable.

Jacques Dubucs

→ arithmétique, calculabilité, Church (thèse de), effectivité