停止問題とは（全体像）
停止問題は、「あるプログラムを動かしたら、いつか止まるか、それとも永遠に動き続ける（無限ループ）か」を判定する問題のこと。
これに対するチューリングの答えは、「どんなプログラムでも判定できる万能ツールは作れない」だった。つまり、コンピュータには原理的に解けない問題があることを示したのだ。
ここで大事なのは、特定のプログラムなら止まるか分かることもあるということ。判定できないのは「どんなプログラムでも見分けられる万能ツール」のほうで、個別に調べれば分かる場合はある。「一つひとつは分かることもあるが、ぜんぶに効く万能判定は作れない」と整理するとよい。
詳しく：決定不能の意味とNP困難との違いだけ覚えれば戦える
ここが記事の心臓部。まず決定不能の意味を押さえよう。
停止問題と決定不能
| 言葉 | 意味 |
|---|---|
| 停止問題 | プログラムが止まるか無限ループかを判定する問題 |
| 決定不能 | どんな入力にも有限時間で答えを出すアルゴリズムが存在しないこと |
| チューリングの結論 | 停止問題を判定する万能アルゴリズムは存在しない |
よく混同されるのがNP困難との違い。NP困難は「解くのにとても時間がかかる」という難しさだが、停止問題はそれ以上で、「そもそも解くアルゴリズムが存在しない」という別格の難しさだ。
NP困難との違い
| NP困難 | 決定不能（停止問題） | |
|---|---|---|
| 難しさ | 解けるが、とても時間がかかる | そもそも解く方法が存在しない |
| アルゴリズム | ある（ただし遅い） | ない |
つまり、NP困難は「遅い」、決定不能は「不可能」。停止問題は後者で、どんなに速い計算機を使っても万能判定は作れない、というわけだね。
この事実は現実にも効いてくる。たとえば「このプログラムにバグがないか」を完璧に判定するツールは作れない。だからテストや人の目によるチェックが必要になる。
わかりやすく言い換えると
要するに、停止問題は「ぜんぶに効く万能の停止判定は作れない」という話だ。
①停止問題 … プログラムが止まるか・無限ループかを見分ける問題
②結論 … どんなプログラムでも見分ける万能ツールは作れない（決定不能）
③NP困難との違い … NP困難は「遅いけど解ける」、決定不能は「そもそも解けない」
「特定のものは分かることもあるが、万能判定は不可能」と覚えるのがコツ。
試験のツボ
🔴 一番出る：万能の停止判定は作れない
①任意のプログラムが止まるか見分ける万能ツールは存在しない
②これを示したのがチューリング
🔴 次に出る：決定不能の意味
①どんな入力にも有限時間で答えを出すアルゴリズムがない
②NP困難（遅いが解ける）よりさらに手ごわい
🟡 押さえると安定：特定と任意の違い・現実への影響
①特定のプログラムは判定できることもある
②完璧なバグ検出ツールは作れない
よくある間違い
①「停止問題はNP困難と同じ難しさ」→ ✗ NP困難は遅いが解ける。停止問題は解く方法そのものが存在しない（決定不能）。
②「どんなプログラムも、止まるか絶対に分からない」→ ✗ 特定のプログラムなら分かることもある。作れないのは万能の判定ツール。
③「停止問題はいつか高性能な計算機で解ける」→ ✗ 計算機の速さの問題ではなく、原理的に万能判定が存在しない。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（停止問題の結論）
停止問題に関する次の記述のうち、正しいものはどれか。
- どんなプログラムでも止まるか無限ループかを見分ける万能ツールは必ず作れる
- 任意のプログラムが止まるか無限ループかを見分ける万能なツールは存在しない
- 停止問題は計算機が遅いせいで解けないだけで、速い計算機があれば解けるものだ
- 停止問題とは、プログラムをどれだけ速く止められるかを競うための問題のことだ
解答は 2 だよ。
停止問題の結論は「任意のプログラムが止まるか無限ループかを見分ける万能ツールは存在しない」なんだ。チューリングが示した有名な定理だよ。
選択肢1の「必ず作れる」、選択肢3の「速い計算機なら解ける」、選択肢4の「速く止める競争」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 万能ツールは作れない |
| 2 | ✓ | 万能判定は存在しない |
| 3 | ✗ | 速さの問題ではない |
| 4 | ✗ | 止まるか否かの判定の問題 |
オリジナル問題2（NP困難との違い）
決定不能とNP困難の違いに関する次の記述のうち、正しいものはどれか。
- NP困難は解く方法が存在せず、決定不能は遅いが解けるという、逆の関係である
- 決定不能もNP困難もまったく同じ意味で、両者には少しの違いも存在していない
- NP困難は遅いが解ける、決定不能はそもそも解く方法が存在しないという違いがある
- 決定不能もNP困難も、どちらも速い計算機さえあればすぐに解けるものとされている
解答は 3 だよ。
NP困難は遅いが解ける、決定不能はそもそも解く方法が存在しないんだ。停止問題は決定不能のほうで、別格の難しさだよ。
選択肢1は関係が逆。選択肢2の「同じ意味」、選択肢4の「速い計算機なら解ける」はどちらも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 遅いが解けるのがNP困難 |
| 2 | ✗ | 意味が異なる |
| 3 | ✓ | NP困難＝遅い・決定不能＝不可能 |
| 4 | ✗ | 決定不能は速さの問題ではない |
オリジナル問題3（特定と任意の違い）
停止問題における特定と任意の違いに関する次の記述のうち、正しいものはどれか。
- 特定のプログラムなら止まるか分かることもあるが、万能の判定ツールは作れない
- どんなプログラムも、止まるか無限ループかは絶対に判定できないものとされている
- 万能の判定ツールは作れるが、特定のプログラムだけはなぜか判定できないものだ
- 停止問題は特定のプログラムにも任意のプログラムにも、いっさい関係のない話だ
解答は 1 だよ。
特定のプログラムなら止まるか分かることもあるけど、どんなプログラムにも効く万能の判定ツールは作れないんだ。ここを取り違えやすいよ。
選択肢2の「絶対に判定できない」、選択肢3の「万能は作れる」、選択肢4の「関係ない」はどれも誤りだよ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 特定は可・万能は不可 |
| 2 | ✗ | 特定なら分かることもある |
| 3 | ✗ | 万能ツールは作れない |
| 4 | ✗ | まさにその関係を扱う問題 |
まとめ
押さえどころ
- 🔴 停止問題の結論 ＝ 任意のプログラムが止まるか見分ける万能ツールは存在しない（決定不能）。
- 🔴 決定不能の意味 ＝ どんな入力にも有限時間で答えを出すアルゴリズムがない。NP困難より手ごわい。
- 🟡 特定と任意・現実への影響 ＝ 特定なら判定できることも。完璧なバグ検出ツールは作れない。
次に学ぶ
執筆: SikakuQuest編集部