每台图灵机只做一件事。加 1 的机器就加 1；写 $\frac17$ 的机器就写 $\frac17$。要做别的计算，就得换一台机器。在 1936 年，这是常态：机械计算器、穿孔卡片制表机和潮汐预测机都是为一项任务而造的，换任务就意味着换机器或重新接线。

在同一篇论文里，图灵证明了这并非必要。

读机器的机器

任何机器的规则表都可以作为文字写在纸带上。于是图灵描述了一台特殊的机器 $U$——通用机，它这样工作：

  1. 在纸带上接收一台机器 $M$ 的描述，后面跟着一个输入 $x$。
  2. 在描述中查找与 $M$ 当前状态以及 $M$ 正在读的符号相对应的规则。
  3. 在代表 $M$ 的纸带的那部分上执行这条规则，记下新状态，回到第 2 步。

这样，只要收到任何一台机器的规则表，$U$ 就能一步一步地模仿它。用符号写：

$$U(\langle M\rangle,x)=M(x)\quad\text{对每台机器 }M\text{ 和每个输入 }x.$$

代价是慢：$M$ 的每一步，$U$ 都要用许多步去查找和抄写。但 $U$ 能算的，恰恰是所有机器合起来能算的。

程序放进内存

实际的推论就是存储程序的思想。不必为每项任务造一台机器，只造一台，任务作为数据输入，放在存数字的同一个内存里。换任务就变成了换文字。你在手机上打开一个应用时正是如此：设备总是那一台，变的是它读的描述。

更进一步：如果程序是数据，一个程序就可以读、写、修改别的程序。编译器和操作系统做的就是这件事；从某种意义上说，停机问题证明中那台接收自身描述的机器 $D$ 也是如此。

Pilot ACE，图灵设计的缩小版，在国家物理实验室建成，1950 年投入运行。它现在陈列于伦敦科学博物馆。
Pilot ACE，图灵设计的缩小版，在国家物理实验室建成，1950 年投入运行。它现在陈列于伦敦科学博物馆。Philafrenzy · Wikimedia Commons · CC BY 2.0

从纸上到金属

战后，1945 至 1946 年，图灵在国家物理实验室写出了一台存储程序计算机——ACE（自动计算引擎）——的完整设计。这个设计很大胆：用水银延迟线做内存，每秒一百万个脉冲，甚至设想机器可以编程修改自己的指令。官僚作风和工程师的短缺拖慢了建造。缩小版的 Pilot 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$ 的一步，通用机要把 $M$ 的整个描述（共 $d$ 格）走一遍再走回来。如果 $M$ 要走 $t$ 步，通用机大约要走多少步？

$M$ 的每一步大约花掉 $U$ 的 $2d$ 步，所以总共约 $2dt$ 步。对于加 1 的机器，$d=15$，计算 $111+1$ 需要 $t=4$ 步，大约是 120 步：慢了三十倍，但结果相同。

来源： 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²⁰ 个密钥和一个缺陷 →

图片来源.