可计算数：几乎每个数都无法计算
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.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”的规则，写出对角线数的前四位。
对角线是 $1,5,9,1$。改动后：$1\to5$，$5\to6$，$9\to5$，$1\to5$。这个数是 $0.5655\ldots$，它在对角线那一位与这四个数各不相同。
