停止問題とは何ですか？

あるプログラムが与えられた入力に対して有限時間で停止するか、永遠に動き続けるかを事前に判定することは、一般的には不可能であるという計算理論上の問題。

停止問題のポイントは？

アラン・チューリングが1936年に証明した計算理論の根本的な限界。背理法（対角線論法）を用いて「万能な停止判定器は作れない」ことを示した。コンパイラの最適化や静的解析が完璧にはなれない理論的根拠でもある

【ていしもんだい】

💡 「このプログラム、いつか止まる？」に万能な答えは存在しない

📌 このページのポイント

停止問題のイメージ

ひよこ

停止問題って何？プログラムが止まるかどうか、動かしてみればわかるんじゃないの？

ペンギン先生

止まるプログラムなら待てばわかるけど、止まらない場合はいつまで待っても「まだ動いてるだけ」なのか「永遠に止まらない」のか区別がつかないんだよ

ひよこ

たしかに...。じゃあ動かさずに判定する方法はないの？

ペンギン先生

チューリングが証明したのはまさにそこで、「あらゆるプログラムについて停止するか判定できる万能な装置は作れない」ということなんだ

ひよこ

どうやって証明したの？

ペンギン先生

背理法だよ。もし万能判定器Hがあると仮定して、Hを使って「自分自身が停止すると判定されたら無限ループする」プログラムDを作ると、Hが矛盾に陥るんだ

ひよこ

自分で自分を判定しようとすると矛盾するんだね！

ペンギン先生

そうそう、「この文は嘘である」というパラドックスに似ているね。対角線論法とも呼ばれる手法だよ

ひよこ

これって実際の開発にも影響あるの？

ペンギン先生

あるよ。たとえばコンパイラが「この変数は絶対使われない」と完璧に判定することも、静的解析ツールがすべてのバグを漏れなく検出することも、理論上は不可能なんだ。だから実用的には「よくあるパターンだけ検出する」という近似的アプローチが使われているよ

まとめ：ざっくりこれだけ覚えればOK！

「停止問題」って出てきたら「プログラムが止まるかどうかを完璧に判定する方法は存在しない、という理論的限界」と思えればだいたいOK！

📖 おまけ：英語の意味

「Halting Problem」＝停止問題

💬 Halt（停止する）から来ていて、プログラムがhaltするかどうかを判定できるか？という問いそのものが名前になっているよ