1936 年の論文の題名が語っているのは機械ではなく、数である。「計算可能数について」。チューリングはこう定義した。ある実数のすべての桁を、一つずつ、けっしてまちがえずに書き出す機械が存在するとき、その実数は計算可能である。

どの数が計算可能か

学校で出てくる数は、ほとんどすべて計算可能である。

  • 分数： $\frac17=0.142857142857\ldots$ 機械は筆算で割り算をし、その循環を永遠にくり返す。
  • 平方根： $\sqrt2=1.41421356\ldots$ 次の桁を求めるために、機械は 0 から 9 までを試し、付け加えても 2 乗が 2 を超えない最大の数字を選ぶ。
  • $\pi$ と $e$： いくらでも近づける級数がある。たとえば $e=1+\frac1{1!}+\frac1{2!}+\frac1{3!}+\cdots$ であり、それを使えば機械は遅かれ早かれどの桁でも書き出せる。

「ちゃんとした」数はすべて計算可能であるように思える。そしてここで驚きが来る。ほとんどどれも計算可能ではないのである。

機械は数え上げられる

どのチューリング機械も、有限の規則の表で記述される。その表は決まった文字を使った文章として書けるので、一つの整数としても書ける。チューリングはそれを記述数と呼んだ。記号を一つずつ数字に置き換えればよい。

だから機械は一覧に並べられる。記述数がいちばん小さい機械、その次、というように。どの機械も記述しない数はたくさんあり、どんな数も書かない機械もたくさんあるが、それはかまわない。大事なのは、計算可能数は一覧 $c_1,c_2,c_3,\ldots$ に収まるということである。専門用語では、それらは可算である。

実数は数え上げられない

1891 年、ゲオルク・カントールは、実数は一覧に収まらないことを示した。証明は対角線である。0 と 1 のあいだのすべての実数の一覧があるとしよう。

$$\begin{aligned} r_1&=0.\underline{5}\,1\,3\,9\ldots\\ r_2&=0.2\,\underline{7}\,0\,4\ldots\\ r_3&=0.8\,8\,\underline{1}\,6\ldots\\ r_4&=0.3\,0\,2\,\underline{2}\ldots \end{aligned}$$

対角線上の数字を取り替えて数 $d$ をつくる。5 があれば 6 にし、ほかの数字なら 5 にする。ここでは $d=0.6555\ldots$ である。この $d$ は $r_1$ と 1 桁めで、$r_2$ と 2 桁めで、$r_n$ と $n$ 桁めで異なる。一覧に載っていない。したがって、どんな一覧もすべての実数を含むことはできない。

二つの事実を合わせよう。計算可能数は一覧に収まり、実数は収まらない。どの機械からもはずれる実数が残り、しかもそれが圧倒的多数なのである。実数を無作為に一つ選べば、それが計算可能である確率はゼロである。

練習：対角線を使う

一覧は $0.1234\ldots$、$0.5555\ldots$、$0.9090\ldots$、$0.3141\ldots$ で始まる。「5 は 6 に、それ以外は 5 に」という規則を使って、対角線の数の最初の 4 桁を書け。

対角線は $1,5,9,1$。取り替えると $1\to5$、$5\to6$、$9\to5$、$1\to5$。数は $0.5655\ldots$ で、四つの数のどれとも対角線の桁で異なる。

練習：1/7 は計算可能

$\frac17$ の桁を書き出す機械をことばで説明せよ。

機械は割り算の余りを覚えておく。余りは 1、3、2、6、4、5 のどれかである。各ステップで、余りを 10 倍し、7 で割った商を書き、新しい余りを覚える。$10=1\cdot7+3$ で 1 を書き、$30=4\cdot7+2$ で 4 を書き、$20=2\cdot7+6$ で 2 を書く、というように続ける。余りは 6 通りしかないので状態は 6 つで足り、機械は $142857$ を永遠に書きつづける。

出典： Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem”（1936）· Georg Cantor, “Über eine elementare Frage der Mannigfaltigkeitslehre”（1891）· Charles Petzold, The Annotated Turing（2008）。

アラン・チューリングの全トピック · ← 停止問題：どの機械にも答えられない問い · 万能機械：プログラムもデータである →

画像クレジット.