「任意のプログラムが停止するかどうかを100%正確に判定するプログラムは作れるのか」という問いは、計算機科学における有名な問題の一つです。一見すると理屈をこねれば実現できそうにも思えますが、この問題は“停止性問題”として知られ、深い理論的制約が存在します。本記事では、その直感的な疑問を整理しながら、なぜ単純には解決できないとされているのかを説明します。
停止性問題とは何か
停止性問題とは、「任意のプログラムPと入力Iが与えられたとき、そのプログラムが有限時間で停止するかを判定できるか」という問題です。
これを100%正確に判定するアルゴリズムの存在が問われています。
この問題はアラン・チューリングによって、一般には解けないことが証明されています。
一見できそうに思える理由
単純なプログラムであれば、ループ回数を数えたり、処理の構造を解析することで停止するか予測できそうに見えます。
実際、多くの実用的なケースでは静的解析ツールによってある程度の判定は可能です。
しかし、これはあくまで「一部のプログラム」に限った話です。
“屁理屈的アプローチ”の限界
例えば「全てのループを展開すれば良い」「シミュレーションを無限に行えば良い」といった考え方があります。
しかし、自己参照を含むプログラムや無限ループの構造を持つ場合、このような方法は必ず破綻します。
特に“自分自身を解析するプログラム”を扱うと矛盾が発生します。
チューリングの対角線論法による矛盾
停止性問題が解けない理由は、自己参照を利用した論理的矛盾にあります。
もし停止判定プログラムHが存在すると仮定すると、「Hを使ってH自身の挙動を逆転させるプログラム」を構成できてしまいます。
このとき論理的に矛盾が発生し、Hの存在そのものが成立しないことが示されます。
現実のプログラム解析との違い
実務では、静的解析やAIを用いて“停止しそうかどうか”を推測することは可能です。
ただし、それは確率的・限定的な判断であり、100%保証ではありません。
理論的な停止性問題とは別物として扱う必要があります。
まとめ
停止性問題は一見すると工夫次第で解けそうに見えますが、自己参照による論理的矛盾により、一般解は存在しないとされています。
そのため「100%正確に判定するプログラム」を作るという発想自体が、理論上成立しないことになります。
ただし現実の開発では、限定的な解析手法により実用的な判定は行われています。
コメント