【ていしもんだい】
停止問題 とは？
最終更新:
💡 すべてのプログラムの「終わる？」は決められない
プログラムと入力を受け取り、その実行が停止するかを判定する問題。あらゆる組み合わせに対し、必ず有限時間で正解する汎用アルゴリズムは存在しない。
📌 このページのポイント
ひよこ 終わるかどうか、実行すれば分からない？
ペンギン先生 実際に停止すれば、その実行は停止すると分かるよ。でも、まだ動いている場合は「もう少しで終わる」のか「永遠に続く」のか、待っているだけでは区別できないんだ。
ひよこ どんなプログラムでも判定する道具は作れない？
ペンギン先生 すべてのプログラムと入力について、判定器自身も必ず有限時間で答え、答えが正しいという道具は作れないよ。計算機を速くすれば解決する、という限界ではないんだ。
ひよこ どうして作れないと分かるの？
ペンギン先生 万能な判定器Hがあると仮定するよ。Dは、入力xをプログラムとしてH(x,x)に尋ね、停止すると言われたら無限に続け、停止しないと言われたら停止する。DにD自身を渡すと、どちらの予測にも反するので矛盾するんだ。
ひよこ では、プログラムを調べる意味はない？
まとめ：ざっくりこれだけ覚えればOK！
「停止問題」って出てきたら「すべてのプログラムが終わるかを万能には判定できない問題」と思えばだいたいOK！
📖 おまけ：英語の意味
「Halting Problem」 ＝ 実行が停止するかを判定する問題
💬 haltは実行が止まること。特定のプログラムを止める操作ではなく、止まるかを調べる問題だよ。