決定不可能な言語

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

例

• チューリングマシンの停止問題
• 死亡率の問題
• 致命的な行列の問題
• ポスト対応問題等