1928 年、ドイツのダフィット・ヒルベルトは、Entscheidungsproblem、すなわち「決定問題」と呼ぶ課題を出した。論理の言葉で書かれたどんな数学の命題についても、それが真か偽かを有限の時間で答える機械的な手続きを見つけよ、というものである。もしそれがあれば、数学は組み立てラインになる。問いを書き込み、ハンドルを回せばよい。

ヒルベルトは答えは「ある」だと信じていた。八年後、チューリングとアメリカのアロンゾ・チャーチが、それぞれ別の道筋で、答えは「ない」ことを示した。

もっと簡単な問い

チューリングはヒルベルトの問いに正面から挑んだのではなかった。まず、どの機械にも答えられない、もっとささやかな問いを見つけた。今日ではこう語られる。

プログラムと入力が与えられたとき、そのプログラムはいつか停止するか、それとも永遠に動きつづけるか。

すぐにわかる場合もある。数に 1 を足すプログラムはすぐ止まる。出口のないまま $1,2,3,\ldots$ と数えるプログラムはけっして止まらない。しかし、ごく短いのに誰も答えを知らないプログラムもある。たとえば次のプログラムは、2 より大きいどの偶数も二つの素数の和である、という有名なゴールドバッハ予想を調べる。

  1. $n=4$ から始める。
  2. $n$ が二つの素数の和でなければ、停止する。
  3. そうでなければ、$n$ に 2 を足して 2 に戻る。

このプログラムが停止するのは、予想が誤りであるとき、かつそのときに限る。それが止まるかどうかを知ることは、1742 年から未解決の問題を解くことである。プログラムが止まるかどうかを判定する一般的な方法があれば、この問題も、ほかの多くの問題も一挙に片づく。

証明

背理法で、その仕事をする機械 $P$ があるとしよう。$P$ はプログラム $M$ の記述と入力 $x$ を受け取り、つねに有限の時間でこう答える。

$$P(M,x)=\begin{cases}\text{「止まる」}&M\text{ が入力 }x\text{ で止まるとき},\\ \text{「止まらない」}&M\text{ が永遠に動くとき}.\end{cases}$$

$P$ を使って、新しい機械、あまのじゃくの $D$ をつくる。$D$ はプログラム $M$ の記述を受け取り、次のように動く。

  • $M$ が自分自身の記述を入力として受け取ったらどうなるかを $P$ に尋ねる。
  • $P$ が「止まる」と言ったら、$D$ は無限ループに入る。
  • $P$ が「止まらない」と言ったら、$D$ は停止する。

ここで致命的な問いが来る。$D$ が自分自身の記述を受け取ったら、どうなるか。

  • $D(D)$ が止まるなら、$P$ は $D(D)$ について「止まらない」と答えたことになり、$P$ はまちがえた。
  • $D(D)$ が止まらないなら、$P$ は「止まる」と答えたことになり、$P$ はやはりまちがえた。

どちらにしても $P$ はまちがえる。したがって機械 $P$ は存在しない。$\blacksquare$

対角線

この証明はカントールの対角線の近い親戚である。行 $i$ がプログラム $M_i$、列 $j$ が入力「$M_j$ の記述」で、各マスにそのプログラムが止まるかどうかが書かれた無限の表を思い描こう。機械 $D$ は対角線、つまりマス $(i,i)$ だけを見て、それぞれの逆を行う。だから $D$ はどの行とも一致しない。少なくともマス $(i,i)$ で行 $i$ と異なるからである。

1936 年の論文で、チューリングは「止まる」という言葉そのものは使っていない。彼の問いは、機械が無限に多くの桁を印刷するか、途中で行き詰まるか、というものだった。「停止問題」という名前は、のちの 1950 年代に生まれた。考え方は同じである。そしてチューリングはそこからヒルベルトへの答えを引き出した。どんな論理の命題でも判定できる方法があれば、「機械 $M$ は止まる」という命題も判定できてしまうが、それは不可能である。

練習：このプログラムは止まるか

プログラム：$n=7$ から始める。$n\neq1$ のあいだ、$n$ が偶数なら $n\leftarrow n/2$、そうでなければ $n\leftarrow3n+1$。

たどると $7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1$。16 歩で止まる。どんな初期値 $n$ についても止まるかどうかは誰も知らない。これがコラッツ予想で、1937 年から未解決である。計算機は巨大な数まで確かめているが、例を確かめることは証明ではない。

練習：証明は機械 P をどこで使っているか

この証明が「どんなプログラムも分析できない」とは言っていない理由を説明せよ。

証明が示すのは、すべてのプログラムについて正しい答えを出すただ一つの方法はない、ということだけである。個々のプログラムについては、止まるかどうかの判定がやさしいことも多く、それを毎日行う道具もある。存在しないのは、けっしてまちがえず、けっして答えに詰まらない万能の機械 $P$ である。

出典： Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem”（1936）· Alonzo Church, “An unsolvable problem of elementary number theory”, American Journal of Mathematics（1936）· Martin Davis, The Universal Computer（2000）。

アラン・チューリングの全トピック · ← チューリング機械：鉛筆とテープと規則で計算する · 計算可能数：ほとんどの数は計算できない →

画像クレジット.