ライアン、答えは間違いなくイエスです。
最初の答えに反して、停止問題は何も証明しません。実際、ライアン、あなたが提案していることは、停止問題が間違っていることを証明しており、実際のデジタル コンピューターには適用されません。
決定論的デジタル システム (つまり、実際のデジタル ハードウェアで実行されるプログラム) では、可能な状態の数は有限であるため、可能な状態はすべて列挙可能です。
ハッシュに必要なメモリの正確な量は次のようになります。
(2)*(program state size)*(number of initial states)
初期状態はハッシュ キーになり、最終状態はハッシュ値になり、初期状態ごとにキーと値のペアができます。
オペレーティング システムの場合、「プログラム状態のサイズ」は 2^(すべてのシステム デバイスの総メモリ ギガビット) です。明らかに、このような大規模な汎用プログラムは、ハッシュに非現実的な量のメモリを必要とし、システムが自己参照/還元不可能なほど複雑であるため (つまり、次のユーザー入力は前のシステム出力に依存する)、とにかく役に立ちません。
説明：
これは非常に便利です。可能性のあるすべての初期状態にインデックスを付け、それを終了状態に関連付けると、任意のプログラムの実行時間を効果的にゼロにすることができるからです。ゼロとは、非常に高速な O(1) 実行時間、つまり終了状態を検索するのにかかる時間 (終了した場合) を意味します。
可能なすべての状態から開始してプログラムを実行すると、サイクルを示す一種の状態マップが提供されます。 したがって、可能な初期状態が与えられると、3 つ (実際には 4 つが 3 つに崩壊) の可能性しかないため、停止問題は解決されます。
- プログラムは、すべての可能な状態を使い果たす前に、以前に遭遇した状態 (初期状態以降) に再び入るため、論理的に永久にループします。
- プログラムは、以前に遭遇した状態に再び入るか、(初期状態以降の) 考えられるすべての状態を使い果たす前に、「終了中」と識別される状態に到達します。
または 4. 最も単純なプログラムは、初期状態から開始し、考えられるすべての状態に 1 回だけ入り、(3) 停止するか、(4) 前に遭遇した状態に再び入って永久にループする以外に選択肢はありません。
for (int i = 0; true; i++); //i は最大値に達し、ロールオーバーしてゼロに戻り、その時点で初期状態に戻ります
したがって、基本的に、インデックスは次のように記述できます。
- 各初期状態には、ちょうど 1 つまたはゼロの終了状態があります。
つまり、初期状態ごとに、プログラムは終了状態に到達するか、初期状態以降に既に遭遇した状態に再び入り、無限に循環します。
したがって、決定論的なデジタル ハードウェア上で実行されるプログラムでは、そのすべての状態と、プログラムが停止するか永久にループするかを判断することは絶対に可能です(ただし、多くの場合、実用的ではありません)。
- 実用性は、有効な初期状態の数 (入力制約を使用して大幅に減らすことができます) と、それらのそれぞれについてプログラムを実行して終了し、結果の状態をハッシュに格納するのにどれだけ時間がかかるかにのみ依存します。テーブル。
プログラムの実行時に O(1) 操作を強制する以外に、状態をキャプチャする他の用途には、ゲーム コンソール エミュレーターの状態保存機能やコンピューターの休止状態機能が含まれます (ただし、システム メモリを使用する必要があるため、状態の完全な復元ではありません)。状態を復元するコードの場合、一部のメモリは保存されない場合があります (GPU メモリなど)。
これが証明しているのは、どんなプログラムもハッシュテーブルで表現できるということです。どのプログラムも、初期状態から最終状態への状態遷移マップで表すことができます。
すべてのプログラムは、大量のメモリ フットプリントを持つ 1 つの大きな関数に簡素化できます。