決定不可能な言語

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

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