indécidable

Indécidable désigne, en logique et en théorie de l’informatique, un problème de décision pour lequel il n’existe pas d algorithme capable de déterminer, pour tout jeu d’entrées, si l’instance appartient à la solution. Autrement dit, aucune procédure ne s’arrête et ne renvoie une réponse correcte pour toutes les entrées.

On distingue les problèmes décidable (il existe un algorithme qui s’arrête pour toute entrée et renvoie oui ou non) des problèmes semi-décidables, ou récursivement énumérables: il existe une procédure qui s’arrête et accepte les instances positives, mais peut boucler sur les négatives.

Exemples: le problème de l’arrêt (HALT) est indécidable: il n’existe pas d’algorithme qui, pour un programme et son entrée, détermine s’il s’arrêtera. Le problème de la validité en logique du premier ordre, autrement dit de décider si une formule est vraie dans tous les modèles, est également indécidable. Les résultats de Gödel et de Turing montrent les limites fondamentales de l’automatisation et de la formalisation.

Conséquences: l’indécidabilité fixe des frontières à ce qui peut être automatisé dans le raisonnement mathématique et informatique. Des fragments plus restreints (par exemple la logique propositionnelle ou les automates) sont décidable, tandis que les systèmes expressifs et complets restent, en général, indécidables.