Langages indécidables

Pour un langage indécidable, il n'y a pas de machine de Turing qui accepte le langage et prend une décision pour chaque chaîne d'entrée w(TM peut cependant prendre une décision pour une chaîne d'entrée). Un problème de décisionP est dit «indécidable» si la langue L de toutes les instances oui à Pn'est pas décidable. Les langages indécidables ne sont pas des langages récursifs, mais parfois, ils peuvent être des langages récursivement énumérables.

Exemple

• Le problème de l'arrêt de la machine de Turing
• Le problème de la mortalité
• Le problème de la matrice mortelle
• Le problème de la correspondance postale, etc.