これはウィキペディアの決定可能性の定義です
計算可能性理論では、決定不可能な問題は、特定のはい/いいえの答えが必要なインスタンスのファミリで構成されているため、入力として問題のインスタンスが与えられた場合、有限数の後に必要な答えを終了して出力するコンピュータープログラムはありませんステップの。より正式には、決定不能な問題とは、言語が再帰集合でない問題です。
再帰セットは、再帰的に列挙可能なセットのサブセットです。再帰セットの外にある、再帰的に列挙可能な言語がいくつかあります。では、再帰的に列挙可能な言語が決定不能ではないのはなぜでしょうか?
再帰的に列挙可能な言語/セットは、半決定可能とも呼ばれます。入力を見て、「はい」または「いいえ」と (正しく) 言うマシンがないため、それらは決定可能ではありません。半決定可能とは、入力を見て、入力がセット内にある場合は「はい」と答え、入力がセット内にない場合は停止に失敗するマシンを作成できることを意味します。半決定可能は、決定可能が再帰的と同等であるのと同じ方法で、再帰的に列挙可能と同等であることが判明しました:-
再帰的に列挙可能な言語を列挙するチューリング マシン R を使用している場合は、言語/セットに含まれる場合と含まれない場合がある入力を受け取る新しいマシン D を作成できます。D は、R がセットの最初の要素を出力するまで R を実行し、次に D はそれをその入力と比較します。一致する場合は、"yes" という結果を返します。一致しない場合は、次の要素を取得するまで R を実行し続けます。R は決して停止しないため (言語は再帰的に列挙可能であり、再帰的ではないため)、D は「はい」と答えるか、停止しないかのいずれかになります。
逆に、「はい」と答えるか停止に失敗するチューリング マシン D がある場合、通常の手法を使用して D の複数のインスタンスを並列に実行し、さまざまな入力を 1 ステップずつ実行する新しいマシン R を作成できます。セットに含まれる場合と含まれない場合があります。D の並列実行の 1 つが "yes" の応答で停止するたびに、R は D のその入力を出力し、残りのすべての入力で D を実行し続けます。R が停止することはありません (D が停止しない入力があるため) が、最終的には、D が「はい」と答えたすべての要素、つまりセット/言語内のすべての要素を出力します。
決定可能、半決定可能、決定不能という 3 種類の (互いに素な) 集合があると考えて混乱しないでください。決定可能と決定不可能の 2 種類があります。決定可能なセットはすべて半決定可能でもあります (そのように言うのは珍しいですが)。決定不能なセットのいくつかは、半決定可能でもあります。これは、すべての列挙可能なセットが再帰的に列挙可能であり、一部の列挙不可能なセットが再帰的に列挙可能であると言っているのとまったく同じです。