今天这段依然出自艾伦·图灵（Alan Turing）1936年发表的经典论文《论可计算数及其在判定问题上的应用》（Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936），具体是文章的第五章。

原文

5. Enumeration of computable sequences.

A computable sequence $\gamma$ is determined by a description of a machine which computes $\gamma$. Thus the sequence $001011011101111\ldots$ is determined by the table on p. 234, and, in fact, any computable sequence is capable of being described in terms of such a table.

It will be useful to put these tables into a kind of standard form. In the first place let us suppose that the table is given in the same form as the first table, for example, I on p. 233. That is to say, that the entry in the operations column is always of one of the forms $E: E, R: E, L: Pa: Pa, R: Pa, L: R: L:$ or no entry at all. The table can always be put into this form by introducing more $m$-configurations. Now let us give numbers to the $m$-configurations, calling them $q_1, \ldots, q_R$, as in §1. The initial $m$-configuration is always to be called $q_1$. We also give numbers to the symbols $S_1, \ldots, S_m$ and, in particular, blank $= S_0$, $0 = S_1$, $1 = S_2$. The lines of the table are now of form

Lines such as

are to be written as

and lines such as

to be written as

In this way we reduce each line of the table to a line of one of the forms ($N_1$), ($N_2$), ($N_3$).

From each line of form ($N_1$) let us form an expression $q_i S_j S_k L q_m$; from each line of form ($N_2$) we form an expression $q_i S_j S_k R q_m$; and from each line of form ($N_3$) we form an expression $q_i S_j S_k N q_m$.

Let us write down all expressions so formed from the table for the machine and separate them by semi-colons. In this way we obtain a complete description of the machine. In this description we shall replace $q_i$ by the letter "$D$" followed by the letter "$A$" repeated $i$ times, and $S_j$ by "$D$" followed by "$C$" repeated $j$ times. This new description of the machine may be called the standard description (S.D). It is made up entirely from the letters "$A$", "$C$", "$D$", "$L$", "$R$", "$N$", and from ";".

If finally we replace "$A$" by "1", "$C$" by "2", "$D$" by "3", "$L$" by "4", "$R$" by "5", "$N$" by "6", and ";" by "7" we shall have a description of the machine in the form of an arabic numeral. The integer represented by this numeral may be called a description number (D.N) of the machine. The D.N determine the S.D and the structure of the machine uniquely. The machine whose D.N is $n$ may be described as $\mathcal{M}(n)$.

To each computable sequence there corresponds at least one description number, while to no description number does there correspond more than one computable sequence. The computable sequences and numbers are therefore enumerable.

Let us find a description number for the machine I of §3. When we rename the $m$-configurations its table becomes:

Other tables could be obtained by adding irrelevant lines such as

Our first standard form would be $q_1 S_0 S_1 R q_2; q_2 S_0 S_0 R q_3; q_3 S_0 S_2 R q_4; q_4 S_0 S_0 R q_1;$.

The standard description is $DADDCRDAA;DAADDRDAAA;$ $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad DAAADDCCRDAAAA;DAAAADDRDA;$

A description number is $31332531173113353111731113322531111731111335317$

and so is $3133253117311335311173111332253111173111133531731323253117$

A number which is a description number of a circle-free machine will be called a satisfactory number. In §8 it is shown that there can be no general process for determining whether a given number is satisfactory or not.

翻译

5. 可计算序列的枚举

一个可计算序列 $\gamma$ 由计算 $\gamma$ 的机器的描述所决定。因此，序列 $001011011101111\ldots$ 由第 234 页（第三章的第二个例子）的表格决定，实际上，任何可计算序列都可以用这样的表格来描述。

将这些表格转换成一种标准形式是很有用的。首先，让我们假设表格的形式与第一个表格（例如第 233 页第三章的第一个例子）相同。也就是说，操作列中的条目总是 $E: E, R: E, L: Pa: Pa, R: Pa, L: R: L:$ 形式之一，或者压根没有条目。通过引入更多的 m-构型，就始终可以将表格转换成这种形式。现在让我们给 m-构型编号，称为 $q_1, \ldots, q_R$，如 §1 第一章所述。初始 m-构型总是被称为 $q_1$。我们也给符号编号 $S_1, \ldots, S_m$，特别是，空白 $= S_0$，$0 = S_1$，$1 = S_2$。表格的行现在是这样的形式：

像 $q_i S_j E, R q_m$ 这样的行要写成 $q_i S_j P S_0, R q_m$，而像 $q_i S_j R q_m$ 这样的行要写成 $q_i S_j P S_j, R q_m$。

通过这种方式，我们将表格的每一行都简化为 ($N_1$)、($N_2$)、($N_3$) 形式之一的一行。

对于每一行形式 ($N_1$)，形成一个表达式 $q_i S_j S_k L q_m$；对于每一行形式 ($N_2$)，形成表达式 $q_i S_j S_k R q_m$；对于每一行形式 ($N_3$)，形成表达式 $q_i S_j S_k N q_m$。

然后接着写下从机器表格形成的所有表达式，并用分号将它们隔开。这样就得到了机器的完整描述。在这个描述中，我们将用字母“$D$”后跟重复 $i$ 次的字母“$A$”来替换 $q_i$，用“$D$”后跟重复 $j$ 次的“$C$”来替换 $S_j$。这个机器的新描述可以被称为标准描述（standard description，缩写为S.D）。它完全由字母“$A$”、“$C$”、“$D$”、“$L$”、“$R$”、“$N$”和“;”组成。

如果最后把“$A$”换成“1”，“$C$”换成“2”，“$D$”换成“3”，“$L$”换成“4”，“$R$”换成“5”，“$N$”换成“6”，“;”换成“7”，我们将得到一个阿拉伯数字形式的机器描述。由这个数字表示的整数可以被称为机器的描述数（description number，缩写为D.N）。D.N 唯一地决定了 S.D 和机器的结构。D.N 为 $n$ 的机器可以记作 $\mathcal{M}(n)$。

每个可计算序列至少对应一个描述数，而每个描述数至多对应一个可计算序列。因此，可计算序列和可计算数都是可枚举的。

让我们找出 §3 第三章例1中机器 I 的描述数。当我们重命名其 m-构型时，其表格变为：

通过添加无关行，还可以得到其他表格，例如：

我们的第一个标准形式将是： $q_1 S_0 S_1 R q_2; q_2 S_0 S_0 R q_3; q_3 S_0 S_2 R q_4; q_4 S_0 S_0 R q_1;$.

标准描述是： $DADDCRDAA;DAADDRDAAA;$ $\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad DAAADDCCRDAAAA;DAAAADDRDA;$

一个描述数是： $31332531173113353111731113322531111731111335317$

而下面这个也是描述数： $3133253117311335311173111332253111173111133531731323253117$

一个是无循环机器的描述数的数字将被称为满意（satisfactory）数。在 §8 中将会表明，不存在通用的过程来确定一个给定的数是否是满意的。

逐段解析

1. 标准化（Standardization）

“将这些表格转换成一种标准形式是很有用的。”

• 抽象归纳：图灵首先将所有可能的图灵机操作抽象归纳为三种基本格式：
• 打印并左移 ($P S_k, L$)
• 打印并右移 ($P S_k, R$)
• 打印并不动 ($P S_k, N$)
• 等价转换：
• “擦除 ($E$)” 被视为 “打印空白 ($P S_0$)”。
• “只移动不打印 ($R$)” 被视为 “重打印当前符号并移动 ($P S_j, R$)”。
• 目的：这样做的目的是为了让机器的指令减少，这样需要编码的指令就减少了，方便后续的编码。

2. 编码（Encoding）与哥德尔数（Gödel Numbering）

这一段是整篇论文中最精彩的数学技巧之一。图灵要把“一台机器”变成“一个整数”。

• 步骤 1：字符编码
• 状态 $q_i$ |$\to$ D + A...A ($i$个)。例如 $q_1 \to DA$, $q_3 \to DAAA$。
• 符号 $S_j$ |$\to$ D + C...C ($j$个)。例如 $S_0 \to D$, $S_1 \to DC$。
• 步骤 2：指令编码
• 每一条指令（如 $q_1 S_0 S_1 R q_2$）都被转换成一串字母。
• 所有指令用分号 ; 连接起来，形成标准描述 (S.D)。这本质上就是这台机器的源代码。
• 步骤 3：数字化 (D.N)
• 将 S.D 中的 7 个字符 ($A, C, D, L, R, N, ;$) 分别映射为数字 $1 \sim 7$。
• 这样，一整串代码就变成了一个巨大的整数。
• 这个整数就是描述数 (Description Number, D.N)。

3. 意义：代码即数据

“描述数唯一地决定了标准描述和机器的结构。”

• 万物皆数：任何算法、任何程序、任何逻辑系统，最终都可以被编码为一个整数。
• 可枚举性：因为整数是可枚举的（可以一个个数出来：1, 2, 3...），所以所有可能的算法（图灵机）也是可枚举的。
• 我们可以说“第 313325... 号机器”。
• 这为后续证明“有些数是不可计算的”铺平了道路：实数是不可枚举的，而机器（算法）是可枚举的。两个集合的大小不一样（无穷大的阶不同），所以必然存在没有对应机器的实数。

一点引申：无穷大的分阶（康托尔的超限数理论）

德国数学家格奥尔格·康托尔（Georg Cantor, 1845-1918）在19世纪末创立了集合论，并提出了一个革命性的观点：无穷大是有大小之分的。他用希伯来字母 $\aleph$（aleph，阿列夫）来标记不同阶的无穷大。

第一阶无穷：可数无穷 $\aleph_0$（阿列夫零）

可数无穷是指那些可以与自然数集 $\mathbb{N} = {0, 1, 2, 3, ...}$ 建立一一对应关系的集合。康托尔证明了以下集合都是 $\aleph_0$ 阶的：

关键洞察：虽然直觉上"有理数比自然数多得多"，但它们实际上是同样大小的无穷！康托尔用对角线枚举法证明了这一点：

按对角线方向枚举所有正有理数（表格中的数字表示枚举顺序）：

枚举路径：① → ② → ③ → ④ → ⑤ → ⑥ → ⑦ → ⑧ → ⑨ → ⑩ → ...（跳过重复值如 2/2 = 1/1）

第二阶无穷：不可数无穷 $\aleph_1$（阿列夫壹）

实数集 $\mathbb{R}$（包括所有有理数和无理数）属于更高阶的无穷。康托尔用著名的对角线论证法证明了这一点：

假设实数是可数的，那么所有实数可以列成一张表。但我们可以构造一个不在表中的实数：取第1位小数不同于第1个数的第1位，第2位小数不同于第2个数的第2位……这个"对角线构造"出的数一定不在表中，产生矛盾。

无穷阶梯一览

为什么这证明了"存在不可计算的数"

1. 图灵机是可数的：每个图灵机对应一个描述数（整数），所以所有图灵机的集合大小是 $\aleph_0$。

2. 实数是不可数的：实数集的大小是 $\aleph_1$（或 $2^{\aleph_0}$）。

3. 鸽巢原理：如果把图灵机"放进"实数中，必然有"装不下"的实数——那些没有对应图灵机的实数就是不可计算数。

用数学语言说：存在一个从自然数到可计算实数的满射，但不存在双射。可计算实数只是实数海洋中的一滴水！

连续统假设

康托尔猜测 $\aleph_1 = 2^{\aleph_0}$，即实数集是最小的不可数集合。这就是著名的连续统假设。1940年哥德尔证明了它不能被证伪，1963年科恩证明了它不能被证明——它是独立于标准集合论公理（ZFC）的。

4. 满意数 (Satisfactory number)

“一个是无循环机器的描述数的数字将被称为满意数。”

• Bug 的定义：并不是所有的整数都代表一个“有用”的机器。
• 有些整数解压后可能格式错误（语法错误）。
• 有些机器运行后会死循环或停止输出（逻辑错误/Circular）。
• 满意数：特指那些格式正确且能无限打印出二进制序列的机器编号。
• 停机问题的伏笔：图灵最后提到，“不存在通用的过程来确定一个给定的数是否是满意的”。这就是著名的不可判定性（Undecidability）的预告。我们无法写一个程序来检查另一个程序是否会“死循环”（在这里指不再产出数据）。

总结

这一章完成了从具体机器到抽象数字的飞跃。 1. 程序被数字化：任何图灵机都可以被编码为一个唯一的整数（D.N）。 2. 程序集是可数的：所有可能的程序构成的集合与自然数集一样大（$\aleph_0$）。 3. 不可判定性的种子：区分“死循环”机器和“好”机器（满意数）的问题，将成为后文的关键。