停止問題とは、任意のコンピュータプログラムと入力値を与えられたとき、そのプログラムが有限時間で終了するか、あるいは無限ループに陥らずに実行を完了するかを判定するアルゴリズムが存在しないことを示した計算機科学の著名な命題です。
停止問題とは
一言でいうと、任意のプログラムが必ず終了するかどうかを、事前に100%正確に見分けるプログラムを作ることは理論的に不可能であるという証明です。
詳しく解説
計算機科学の父であるアラン・チューリングが1936年に数学的に証明しました。AIやプログラムの自動生成、コードの検証（フォーマルモデリング）において、バグのない完璧な自動テストや、無限ループを完全に防ぐ汎用的なチェッカーを作ることが理論的限界により不可能であることを示しています。AIエージェントが生成したコードが安全に停止するかどうかを検証する上でも、根本的な壁となります。
具体例・使われ方
AIに「絶対に無限ループしないコードを書いて」と依頼したり、プログラム解析ツールが「このコードは必ず終了する」と100%確実に保証しようとしたりする場面が挙げられます。実際には特定の条件下でのみ判定する近似的なアプローチが取られます。
似た用語との違い
計算量理論における「P対NP問題」や「決定問題」と混同されやすいですが、停止問題は「計算が可能か不可能か（計算可能性）」を問うものであり、効率性を問う問題とは異なります。
注意点
「すべてのプログラムに対して判定する汎用的なアルゴリズムが存在しない」のであって、特定の限定されたプログラムや簡単なループであれば判定できるケースもあります。過度にすべての自動検証を諦める必要はありません。
この解説は役に立ちましたか？誤りが含まれる場合はご報告いただけますと幸いです。
更新日時: 2026年9月19日 17:30