1936 年には計算機というものはなかった。英語の computer は、保険会社や天文台や役所で、鉛筆と紙で計算することを職業とする人を意味していた。チューリングはこの人から出発した。計算するとき、人は本当は何をしているのかを問い、本質的でないものをすべて取り除いていった。

計算する人から残るもの

論文「計算可能数について」のチューリングの推論は、ほとんど単純化の一覧である。

  • 紙は、マス目に区切られたテープに置き換えられる。方眼紙の上の計算は、マスごとに一行に写せるからである。
  • 各マスには、有限の一覧から選んだ一つの記号が入る。数字、文字、空白。
  • 計算する人は一度に少しのマスしか見ない。一マス見れば十分である。いくつかを見るというのは、一つを見て、次に隣を見ることだからである。
  • 計算する人には「足し算をしている」「繰り上げている」といった心の状態がある。そうした状態は有限個しかない。
  • 各ステップは、現在の状態と読んでいる記号だけで決まる。ステップとは、記号を書き、一マス左か右に動き、状態を変えることである。

残るのは一つの機械である。テープ、読み書きするヘッド、そして規則の表。表の各行はこう言う。「この状態でこの記号を読んだら、これを書き、そちらへ動き、この状態に移れ」。

1 を足す機械

二進法で書かれた数に 1 を足す機械をつくってみよう。手で $1011+1$ を計算するときは右から左へ進む。最後の 1 は 0 になって「1 繰り上がる」。その前の 1 も 0 になって繰り上がる。次の 0 は 1 になり、計算は終わる。結果は $1100$、つまり $11+1=12$ である。

機械はまさにそれを行う。必要な状態は「足す」一つと、終わりの状態「停止」だけである。ヘッドは最後の桁から始める。

状態 読む 書く 動く 次の状態
足す 1 0 左へ 足す
足す 0 1 動かない 停止
足す 空白 1 動かない 停止

一行めは繰り上がりである。1 を 0 に替えて左へ進む。二行めは 0 を見つけたら計算を終える。三行めは、$111+1=1000$ のように桁がすべて 1 だった場合を扱う。ヘッドは数の左の空白に着き、そこに新しい 1 を書く。

なぜこれほど貧弱なのか

チューリング機械はばかばかしいほど限られて見える。二つの数を一度に足すこともできず、テープ以外に記憶もなく、一マスずつしか動かない。しかし、この貧しさは意図されたものである。チューリングが求めたのは、人がそれを実行できることを誰も疑えないほど単純で、しかもどんな計算も含むほど一般的な「機械的な計算」の定義だった。

この賭けの後半はチャーチ＝チューリングのテーゼと呼ばれる。機械的な手続きで計算できるものは、すべてチューリング機械で計算できる、というものだ。これは定理ではない。チューリング以前、「機械的な手続き」は数学の概念ではなかったからである。これは一度も覆されたことのないテーゼである。それ以後につくられたすべての計算機は、いちばん単純なものからいちばん速いものまで、チューリング機械とまったく同じ関数を計算する。ただ速いだけである。

練習：111 で機械を追う

テープ $111$、ヘッドは最後の 1 から始める。1 歩め：1 を読み、0 を書いて左へ。テープは $110$。2 歩め：1 を読み、0 を書いて左へ。テープは $100$。3 歩め：1 を読み、0 を書いて左へ。テープは $000$ で、ヘッドは数の前の空白にある。4 歩め：空白を読み、1 を書いて停止。テープは $1000$。$7+1=8$ を 4 歩で計算した。

練習：何歩かかるか

最後の $k$ 桁が 1 で、その前の桁が 0 である数に 1 を足すには、機械は何歩かかるか。

$k$ 個の 1 が 0 になるのに一歩ずつ、さらに 0 を 1 にするのに一歩で、$k+1$ 歩である。0 で終わる偶数なら一歩で済む。最悪の場合は、1 だけからなる $n$ 桁の数で、$n+1$ 歩かかる。

出典： Alan Turing, “On computable numbers, with an application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society（1936）· Charles Petzold, The Annotated Turing（2008）。

アラン・チューリングの全トピック · ← アラン・チューリングの生涯 · 停止問題：どの機械にも答えられない問い →

画像クレジット.