Propriété d'un problème de décision qui signifie l'existence d'une procédure effective (algorithme), dans le modèle de calcul choisi, qui s'arrête toujours et répond correctement si une entrée appartient au langage.

Principe

Un problème est décidables s'il existe une méthode mécanique terminante donnant une réponse oui/non pour chaque instance ; la décidabilité se conserve sous opérations booléennes quand on dispose de procédures effectives pour les composants.

Démonstration

Le langage reconnu par un automate fini déterministe est décidables car la procédure de transition s'exécute sur l'entrée et s'arrête en donnant l'acceptation ou le rejet.

Mauvaise application

Prendre une procédure de semi-décision (qui s'arrête seulement sur les instances positives) pour une procédure de décision complète, ou inférer l'existence d'un algorithme haltant universel parce que de nombreux cas pratiques sont résolus.

Conséquence

Si un problème est décidables, on peut construire un algorithme général pour classer les instances ; les complémentaires, intersections et unions de langages décidables restent décidables via des constructions effectives.

Inversion

Indécidabilité : il n'existe aucun algorithme qui s'arrête toujours et décide correctement l'appartenance pour toutes les entrées du domaine du problème.

Limite

S'applique aux problèmes de décision encodés dans un modèle de calcul précis (typiquement machines de Turing) ; n'aborde ni les limites de ressources, ni les approximations probabilistes, ni l'indépendance par rapport à un système d'axiomes.

Tension sémantique

Souvent confondue avec la faisabilité (décidabilité en temps polynomial) ou avec la complétude syntaxique d'une théorie ; la décidabilité concerne uniquement l'existence d'une procédure terminante correcte, pas son efficacité ni son statut proof-théorique.

Synthèse

La décidabilité identifie les problèmes pour lesquels existe un algorithme effectif et haltant permettant de décider l'appartenance ; elle distingue la résolubilité algorithmique exacte des notions plus faibles comme la semi-décidabilité ou les contraintes de complexité.