決定できない言語

決定不能な言語の場合、言語を受け入れ、すべての入力文字列 w に対して決定を行うチューリングマシンはありません（TMは一部の入力文字列に対して決定を行うことができます）。 P に対するすべてのyesインスタンスの言語 L が決定可能でない場合、決定問題 P は「決定不能」と呼ばれます。決定不可能な言語は再帰的な言語ではありませんが、再帰的に列挙可能な言語である場合があります。