どのチューリング機械も一つのことしかしない。1 を足す機械は 1 を足し、$\frac17$ を書く機械は $\frac17$ を書く。別の計算をするには別の機械が要る。1936 年には、それが当たり前だった。機械式計算機も、パンチカードの集計機も、潮汐予測機も一つの仕事のためにつくられ、仕事を変えるには機械を替えるか配線をし直すしかなかった。

同じ論文で、チューリングはその必要がないことを示した。

機械を読む機械

どんな機械の規則の表も、文章としてテープに書くことができる。そこでチューリングは特別な機械 $U$、万能機械を記述した。$U$ は次のように動く。

  1. テープの上で、機械 $M$ の記述と、そのあとに続く入力 $x$ を受け取る。
  2. 記述の中から、$M$ の現在の状態と、$M$ が読んでいるはずの記号に対応する規則を探す。
  3. テープのうち $M$ のテープを表す部分でその規則を実行し、新しい状態を書きとめて 2 に戻る。

こうして $U$ は、表さえ与えられれば、どんな機械でも一歩ずつまねする。記号で書けば、

$$U(\langle M\rangle,x)=M(x)\quad\text{すべての機械 }M\text{ とすべての入力 }x\text{ について}.$$

代償は遅さである。$M$ の一歩ごとに、$U$ は探したり写したりするのに何歩もかかる。しかし $U$ が計算できるものは、すべての機械を合わせて計算できるものとちょうど同じである。

メモリの中のプログラム

実際上の帰結は、プログラム内蔵という考え方である。仕事ごとに機械をつくるかわりに、機械は一台だけつくり、仕事はデータとして、数を入れるのと同じメモリに入れる。仕事を変えることは、文章を変えることになる。携帯電話でアプリを開くときに起きているのはまさにそれである。装置はいつも同じで、変わるのはそれが読む記述のほうである。

さらに、プログラムがデータなら、プログラムがほかのプログラムを読み、書き、書き換えることもできる。コンパイラーやオペレーティングシステムがしているのはそれであり、ある意味では、停止問題の証明で自分自身の記述を受け取った機械 $D$ もそうである。

パイロット ACE。チューリングの設計を縮小した版で、国立物理学研究所でつくられ、1950 年に動きだした。現在はロンドンの科学博物館にある。
パイロット ACE。チューリングの設計を縮小した版で、国立物理学研究所でつくられ、1950 年に動きだした。現在はロンドンの科学博物館にある。Philafrenzy · Wikimedia Commons · CC BY 2.0

紙から金属へ

戦後の 1945 年から 1946 年にかけて、チューリングは国立物理学研究所で、プログラム内蔵式計算機 ACE（自動計算機関）の完全な設計を書いた。大胆な設計だった。水銀遅延線のメモリ、毎秒百万パルスの速さ、そして機械が自分の命令を書き換えるようにプログラムできるという考えまで含まれていた。官僚主義と技術者不足のせいで建造は遅れた。縮小版のパイロット ACE がようやく動いたのは 1950 年で、しばらくのあいだ世界で最も速い計算機の一つだった。

その間、マンチェスターでは、フレデリック・ウィリアムズとトム・キルバーンが、1948 年 6 月 21 日、ベビーというあだ名の機械で、電子メモリに保存した最初のプログラムを動かした。チューリングは数か月後にマンチェスターに来て、それに続く機械の仕事にかかわった。

マンチェスターの「ベビー」の複製。1948 年、電子メモリに保存されたプログラムを実行した最初の計算機で、マンチェスターの科学産業博物館に展示されている。
マンチェスターの「ベビー」の複製。1948 年、電子メモリに保存されたプログラムを実行した最初の計算機で、マンチェスターの科学産業博物館に展示されている。Parrot of Doom · Wikimedia Commons · CC BY-SA 3.0
練習：機械を文章として書く

1 を足す機械を、五つ組（状態、読む、書く、動く、次の状態）の列として符号化せよ。足すを A、停止を H、空白を B、左へを L、動かないを N とする。

$$\text{A1 0 L A}\quad\text{A0 1 N H}\quad\text{AB 1 N H}$$

記号は 15 個である。テープに書かれたこれが、万能機械がもとの機械をまねするために読む記述 $\langle M\rangle$ である。

練習：まねするには何歩かかるか

$M$ の一歩をまねするのに、万能機械は $d$ マスある $M$ の記述全体を往復しなければならないとする。$M$ が $t$ 歩かかるとき、万能機械はおよそ何歩かかるか。

$M$ の一歩ごとに $U$ はおよそ $2d$ 歩かかるので、合計はおよそ $2dt$ 歩である。1 を足す機械では $d=15$、$111+1$ に $t=4$ 歩なので、約 120 歩になる。30 倍遅いが、結果は同じである。

出典： Alan Turing, “On computable numbers”（1936）および “Proposed electronic calculator”（1946）· B. Jack Copeland（編）, Alan Turing’s Automatic Computing Engine（2005）· The Manchester Baby, Science and Industry Museum。

アラン・チューリングの全トピック · ← 計算可能数：ほとんどの数は計算できない · エニグマ：1.59×10²⁰ 通りの鍵と一つの欠陥 →

画像クレジット.