停止問題は、論理と数学の計算可能性理論における重要な問題で、1936 年にイギリスの数学者アラン チューリングによって提案されました。該当する論文はチューリングの有名な論文「計算可能な数について、Entscheidungs 問題への応用を伴う」で、この論文では停止問題とチューリングマシンの概念が初めて提案されました。 Proceedings of the London Mathematical Society に発表されたこの論文は、現代のコンピューター科学の基礎を築きました。チューリングの元の論文は、停止問題として知られるようになったものについて直接議論していませんでしたが、彼の研究はコンピューティングの基礎を築くのに貢献しました。停止問題の解決不可能性はコンピューティング理論の中核となる概念であり、一部の問題は本質的にアルゴリズム的に解決できないことを示唆しています。
停止問題では、プログラムが限られた時間内に動作を終了できるかどうかを判断する問題を検討します。言い換えれば、プログラムと入力が与えられた場合、プログラムが常に実行されているのではなく、実行中に最終的に停止するかどうかを判断できます。チューリングは、停止問題は解決不可能であること、つまり、プログラムの実行が停止するか、すべてのプログラムと入力に対して無限ループするかを決定できる普遍的なアルゴリズムは存在しないことを、対角線の議論を通じて証明しました。この問題の証明はコンピューター サイエンス理論の基礎の 1 つであり、コンピューターの限界を明らかにします。