計算可能数：ほとんどの数は計算できない
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.d_1d_2d_3\ldots$ と書き、一覧の $n$ 番めの機械が空白のテープで止まるなら $d_n=1$、止まらないなら $d_n=0$ とする。この数は完全に定義されている。しかし、もしある機械がその桁を書き出せたなら、その機械は停止問題を解いてしまうことになり、それは不可能である。存在しているのに、誰もけっして書き出すことのない数なのである。 練習：対角線を使う一覧は $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$ で、四つの数のどれとも対角線の桁で異なる。
