決定論的プログラム（つまり、ステートマシン）が停止問題を解くことと同等の無限ループにあるかどうかを検出していますか？
私は解決策を思いついたが、なぜそれが機能しないのかわからない：
これはうまくいかないと思います...しかし、なぜですか？
プログラムが無限ループにあるかどうかを検出するのは完全に合理的な方法のようです（たとえば、メモリ自体ではなくハッシュを格納する場合、100％正確ではありませんが）...もしあれば、何が問題になっていますか？
理論的には、実際のコンピューターには有限の数の可能な状態があるため、停止問題と同等ではありません（それは巨大ですが）。停止問題が適用されるチューリングマシンには、無限のストレージがあります。
しかし、あなたのアイデアをさらに探求しましょう。また、「非表示」状態のスナップショットを作成する必要があります。CPUのプログラムカウンターとその他のレジスターであり、各単一命令の前にスナップショットを作成する必要があります。（メモリスナップショットが同じで、同じ命令が実行されようとしている場合、プログラムは無限ループになります。メモリの内容が同じである場合は役に立ちませんが、最後のもの以外のものが実行されます。同じスナップショットを見たとき。）
実際には、非常に小さなコンピューターでさえ、非常に多くの潜在的な状態を抱えているため、すべてのスナップショットを保存することはできません（ハッシュすらできません！）。たとえば、64kBのRAMを搭載した古代のコモドール64のようなミニコンピューターでさえ、256 ^ 65536の潜在的な状態があります（5つのCPUレジスターは含まれません）。非常に長い可能性のある追跡サイクルは、時間と空間の両方で絶対に実行不可能です。
原則としても解決策は機能しません。チューリングマシンは、無限ループに入るのに正確に同じ状態（同じ構成のテープを使用）である必要はありません。
アルゴリズムは状況依存言語と線形拘束オートマトンで機能する可能性がありますが、TMに必要なテープの量がわからない場合は、無限ループが発生したのか、それともトップに到達しようとしていたのかがわかりません。 。あなたの方法は、さまざまな理由で実際のコンピューターで明らかに機能することに注意してください...その主なものは、コンピューターが（大きな）有限オートマトンよりも強力ではないということです。