1936 年那篇论文的标题说的不是机器，而是数：《论可计算数》。图灵这样定义它们：如果存在一台机器，能一位接一位地写出一个实数的所有数字，而且永远不写错，这个实数就是可计算的。

哪些数是可计算的

学校里出现的数几乎都是可计算的。

  • 分数： $\frac17=0.142857142857\ldots$ 机器做长除法，永远重复这个循环。
  • 根式： $\sqrt2=1.41421356\ldots$ 为了找出下一位，机器从 0 试到 9，看哪个最大的数字添上之后，所得的数平方仍不超过 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$ 不同，在第二位与 $r_2$ 不同，在第 $n$ 位与 $r_n$ 不同。它不在清单上。所以没有任何清单能包含全部实数。

把两个事实放在一起：可计算数能排成清单，实数不能。于是有实数落在所有机器之外，而且它们占了绝大多数。如果你随机挑一个实数，它是可计算数的概率为零。

练习：用一用对角线

清单开头是 $0.1234\ldots$、$0.5555\ldots$、$0.9090\ldots$、$0.3141\ldots$。用“5 变 6，其余变 5”的规则，写出对角线数的前四位。

对角线是 $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；依此类推。因为只有六种可能的余数，六个状态就够了，机器永远写着 $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）。

艾伦·图灵的全部主题 · ← 停机问题：没有机器能回答的问题 · 通用机：程序也是数据 →

图片来源.