停止性問題とは、任意のプログラムと入力が与えられたとき、そのプログラムが有限時間で終了するか、それとも無限ループに陥るかを有限の時間内で完全に判定するアルゴリズムが存在しないとする計算機科学の根本的な定理です。
停止性問題とは
一言でいうと、コンピュータプログラムが「いつか必ず終わるか」を自動で完全に見分けることは、数学的に不可能であるという問題です。
詳しく解説
計算機科学の父であるアラン・チューリングが1936年に証明しました。この問題は人工知能の発展においても重要です。AIが作成したプログラムのバグや無限ループを完全に検出する究極の静的解析ツールを作ることが、理論的に不可能であることを意味しているためです。
具体例・使われ方
例えば、AIエージェントに「このプログラムが正しく終了するか検証してほしい」と依頼した際、AIは多くのケースで予測できますが、数学的にすべてのプログラムを完璧に判定する汎用的な仕組みを作ることはできません。
似た用語との違い
計算量理論における「P対NP問題」などが効率性や計算の難しさを扱うのに対し、停止性問題は計算が「そもそも完了するかどうか」という存在そのものを扱います。
注意点
停止性問題は「すべてのプログラムに対して万能な判定機が存在しない」ことを示しているにすぎず、特定の限定されたプログラムや単純なアルゴリズムであれば停止性を証明することは可能です。
この解説は役に立ちましたか？誤りが含まれる場合はご報告いただけますと幸いです。
更新日時: 2026年9月20日 06:00