décidables

Les problèmes décidados? Non. Le terme correct en informatique théorique est « problèmes décidables ». Un problème de décision est décidable s’il existe une machine de Turing (ou un algorithme) qui, pour tout motif d’entrée, s’arrête et donne une réponse oui ou non qui est toujours correcte. Autrement dit, la langue associée au problème est appelée récursive ou décidable.

En termes de théorie des langages, une langue L est dite décidable si elle est récursive: il existe une fonction de décision totale qui détermine, en temps fini, si un mot appartient à L. Cette notion est distincte, mais liée, à celle de langages récursivement énumérables (semi-décidables), où la machine peut s’arrêter lorsque l’entrée est dans L mais peut boucler sinon.

La classe des langages décidables est fermée sous union, intersection et complément, et elle est contenue dans la classe des langages récursivement énumérables. Cependant, elle est strictement plus petite que celle des langages énumérables; certains problèmes sont semi-décidables mais non décidables.

Exemples de problèmes et de classes décidables: les langages finis et les langages réguliers, pour lesquels les méthodes de mise en forme ou d’automates déterministes permettent une décision rapide. Les langages hors contexte (context-free) ont aussi des problèmes de décision bien connus, comme l’appartenance à un CFG (algorithme CYK). Le test de primalité des nombres entiers est décidable (existe un algorithme polynomial). À l’inverse, des problèmes célèbres comme le problème d’arrêt (HALT) et l’équivalence ou l’inclusion générales entre langages de Turing sont non décidables.

En résumé, les problèmes décidables forment une catégorie centrale de la théorie de la calculabilité, caractérisée par l’existence d’un algorithme total qui répond correctement à chaque instance.