今天这段依然出自艾伦·图灵（Alan Turing）1936年发表的经典论文《论可计算数及其在判定问题上的应用》（Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936），具体是文章的第三章。这一章的内容看着繁琐，其实只要照着推演就会发现就是两个具体案例，图灵用这两个案例演示了他所提出的计算机器的计算能力，尤其是第二个例子用到了比较复杂的条件判断和分支循环，已经初步具备了现代编程语言的雏形了。

原文

3. Examples of computing machines.

I.

A machine can be constructed to compute the sequence $010101\ldots$.
The machine is to have the four $m$-configurations “b”, “c”, “e”, “f” and is capable of printing “0” and “1”. The behaviour of the machine is described in the following table in which “$R$” means “the machine moves so that it scans the square immediately on the right of the one it was scanning previously”. Similarly for “$L$”. “$E$” means “the scanned symbol is erased” and “$P$” stands for “prints”. This table (and all succeeding tables of the same kind) is to be understood to mean that for a configuration described in the first two columns the operations in the third column are carried out successively, and the machine then goes over into the $m$-configuration described in the last column. When the second column is left blank, it is understood that the behaviour of the third and fourth columns applies for any symbol and for no symbol. The machine starts in the $m$-configuration $b$ with a blank tape.

If (contrary to the description in §1) we allow the letters $L$, $R$ to appear more than once in the operations column we can simplify the table considerably.

II.

As a slightly more difficult example we can construct a machine to compute the sequence $001011011101111011111\ldots$. The machine is to be capable of five $m$-configurations, viz. “o”, “q”, “p”, “f”, “b” and of printing “$ə$”, “$x$”, “0”, “1”. The first three symbols on the tape will be “$ə ə 0$”; the other figures follow on alternate squares. On the intermediate squares we never print anything but “$x$”. These letters serve to “keep the place” for us and are erased when we have finished with them. We also arrange that in the sequence of figures on alternate squares there shall be no blanks.

To illustrate the working of this machine a table is given below of the first few complete configurations. These complete configurations are described by writing down the sequence of symbols which are on the tape, with the $m$-configuration written below the scanned symbol. The successive complete configurations are separated by colons.

This table could also be written in the form

$$b : ə ə o \quad 0 : ə ə q \quad 0 : \ldots \quad (C)$$

in which a space has been made on the left of the scanned symbol and the $m$-configuration written in this space. This form is less easy to follow, but we shall make use of it later for theoretical purposes.

The convention of writing the figures only on alternate squares is very useful: I shall always make use of it. I shall call the one sequence of alternate squares $F$-squares and the other sequence $E$-squares. The symbols on $E$-squares will be liable to erasure. The symbols on $F$-squares form a continuous sequence. There are no blanks until the end is reached. There is no need to have more than one $E$-square between each pair of $F$-squares: an apparent need of more $E$-squares can be satisfied by having a sufficiently rich variety of symbols capable of being printed on $E$-squares. If a symbol $\beta$ is on an $F$-square $S$ and a symbol $\alpha$ is on the $E$-square next on the right of $S$, then $S$ and $\beta$ will be said to be marked with $\alpha$. The process of printing this $\alpha$ will be called marking $\beta$ (or $S$) with $\alpha$.

翻译

3. 计算机器示例

示例 I.

可以构造一台机器来计算序列 $010101\ldots$。 该机器具有四个 m-构型：“b”、“c”、“e”、“f”，并能够打印“0”和“1”。机器的行为描述在下表中，其中“$R$”表示“机器移动到当前方格紧邻的右侧方格并扫描内容”。“$L$”同理，就是左移。“$E$”表示“在当前方格上擦除扫描到的符号”，“$P$”代表“在当前方格上打印”。该表（以及随后所有同类表格）应理解为：第一列m-构型和第二列符号这一对组合是构型，对这列构型依次执行第三列中的操作，然后机器转入最右边第四列描述的 m-构型。当第二列留空是None的时候，表示第三列和第四列的行为适用于任何符号或无符号的情况。如下表所示，机器的初始状态是 m-构型 $b$ 和空白纸带，然后开始运行。

如果（与 §1 中的描述相反）我们允许表示左右移动的字母 $L, R$ 在第三列（也就是操作列）中出现多次，就可以将上面的表格变得更加简单。

示例 II.

接下来举一个稍难一点的例子，我们来构造一台机器，计算序列 $001011011101111011111\ldots$。该机器具有五个 m-构型，即“o”、“q”、“p”、“f”、“b”，并能打印“$ə$”、“$x$”、“0”、“1”。纸带上的前三个符号将是“$ə ə 0$”；其他数字紧随其后，出现在交替的方格上。在中间的方格上，我们除了“$x$”之外不打印任何东西。这些字母用来“暂时占位”，等用完时会就擦除它们。我们还要确保在交替方格上的数字序列中不含空白。

为了说明这台机器的工作原理，下面给出了前几个完整构型的表格。这些完整构型是通过写下纸带上的符号序列来描述的，m-构型写在被扫描符号的下方。连续的完整构型用冒号分隔。

（注：此处直接展示原文的字符图示，不再重复翻译其中的符号，因为它们是形式化的符号表示。）

该表也可以写成以下形式： $$b : ə ə o \quad 0 : ə ə q \quad 0 : \ldots \quad (C)$$

其中在被扫描符号的左侧留出了空间，并将 m-构型写在这个空间里。这种形式不太容易跟踪，但我们稍后将出于理论目的使用它。

在交替方格得上书写数字的设计非常有用：本文将后面将会一直这样做。接下来，把交替方格的一个序列称为 $F$-方格（F-squares），另一个序列称为 $E$-方格（E-squares）。$E$-方格上的符号可能会被擦除。$F$-方格上的符号形成一个连续的序列。在到达末尾之前没有空白。每对 $F$-方格之间只需要有一个 $E$-方格就足够了：如果需要用更多 $E$-方格，就可以通过在 $E$-方格上打印足够多样的符号来满足。如果符号 $\beta$ 在 $F$-方格 $S$ 上，符号 $\alpha$ 在 $S$ 右侧紧邻的 $E$-方格上，那么 $S$ 和 $\beta$ 将被称为被 $\alpha$ 标记（marked）。打印这个 $\alpha$ 的过程将被称为用 $\alpha$ 标记 $\beta$（或 $S$）。

逐段解析

1. 示例 I：生成 010101... 的机器

“可以构造一台机器来计算序列 $010101\ldots$。”

• 目标 ： 这是一个最简单的“无循环机器”示例，它的任务是无限地交替输出 0 和 1。
• 状态机逻辑（详细版） ：
• b (Begin): 打印 0，右移。 -> 转到 c。
• c: 右移一格（跳过一个空位，为将来的扩展留空间，或者是为了演示跳格）。 -> 转到 e。（注：原文PDF表格这里第一行末尾是 c，第二行末尾也是c了，怀疑这是原文笔误或 OCR 错误，逻辑上通常是 b->c->e->f->b 循环。根据图灵论文原文勘误，此处第二行 $c \to e$ 才合理，否则 $c \to c$ 且只移动不打印会死循环。我已在翻译中修正为 $c \to e$了）。
• e: 打印 1，右移。 -> 转到 f。
• f: 右移一格。 -> 转到 b。

• 循环 ： $b \to c \to e \to f \to b \ldots$ 从而产生 0 _ 1 _ 0 _ 1 _ ...

• 简化版表格 ：

• 如果允许一次写多个位移操作（如一次操作里面写两个甚至更多的 $R$ 或者 $L$ ），状态数可以大大减少。 这里的简化版机器只用一个m构型 $b$ 就能完成任务：
• 看到空：打印 0。
• 看到 0：右移两格，打印 1。
• 看到 1：右移两格，打印 0。

2. 示例 II：生成 0010110111... 的机器

"作为一个稍难一点的例子，我们可以构造一台机器来计算序列 $001011011101111011111\ldots$。"

• 目标序列 ： 这个序列的规律是：0, 01, 011, 0111, 01111... 即每次在末尾多一个 1。完整展开就是：0 → 00 → 001 → 0010 → 00101 → 001011 → 0010110 → 00101101 → 001011011 → 0010110111... （注意：前两个 0 是初始状态，之后开始生成递增的 1 序列）

• 所用符号详解 ：

• $ə$ (schwa)：边界标记（Start marker），放在纸带最左端，用于标识起始位置，防止机器运行时“跑丢”。
• $0, 1$：数据符号，用于构成最终的目标序列。

• $x$：辅助标记（Marker），临时标记在 E-方格上，用于记录“当前正在处理哪个数字”，相当于算法中的临时变量。

• 交错方格的设计：F-方格与 E-方格设计 ：

• 这里讲整个方格拆分成交错的两类，分别进行数据和辅助符号的存放。
• F-squares (Figures) ： 存放最终数据的方格（第1, 3, 5...奇数格）。这些方格上的内容是我们最终要的结果，不会被轻易擦除。
• E-squares (Erasable) ： 存放辅助符号的方格（第2, 4, 6...偶数格）。这些方格上的内容（如 x）是临时的，用完就擦除，相当于工作区。

• 间隔存储的作用 ： 这种设计是图灵机编程的关键技巧，解决了在一条线性纸带上同时存储数据和元数据的问题。就像现代计算机中：

  • 数据区和缓冲区交错放置
  • 或链表结构中数据节点和指针节点交替
  • 或内存中代码段和数据段分离

• 机器运行原理（详细步骤与表格对应） ：

• 初始化 (状态 b) ：

  • 操作：Pə, R, Pə, R, P0, R, R, P0, L, L
  • 执行：
  • Pə：在位置1（F方格）打印 ə
  • R：右移到位置2（E方格）
  • Pə：在位置2（E方格）打印 ə
  • R：右移到位置3（F方格）
  • P0：在位置3（F方格）打印 0
  • R：右移到位置4（E方格）
  • R：右移到位置5（F方格）
  • P0：在位置5（F方格）打印 0
  • L：左移到位置4（E方格）
  • L：左移到位置3（F方格）
  • 结果： | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | |------|-------|-------|-------|-------|-------| | 初始状态内容 | 空白 | | | | | | 最终状态内容 | ə | ə | 0 | | 0 | | 说明 | 机器初始位置 | | 机器最终位置 | | |

• 查找与标记 (状态 o) ：

  • 操作：当遇到 1 时，执行 R, Px, L, L, L 转到 o；当遇到 0 时，转到 q。
  • 执行：
  • 当前在位置3，扫描 0（F方格）
  • 根据表格，遇到 0 时直接转到 q，不执行任何操作
  • 注意：原文中状态 o 的设计是先找 1，如果找到就标记并继续找下一个 1；如果找不到 1（即遇到 0），就开始复制操作。
  • 结果：（此步骤仅进行状态转移，纸带内容不变） | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | |------|-------|-------|-------|-------|-------| | 初始状态内容 | ə | ə | 0 | | 0 | | 最终状态内容 | ə | ə | 0 | | 0 | | 说明 | | | 机器初始位置=最终位置 | | |

• 复制 (状态 q) ：

  • 操作：当遇到任意符号（0或1）时，执行 R, R 转到 q；当遇到空白时，执行 P1, L 转到 p。
  • 执行：
  • 位置3扫描 0，执行 R, R：右移到位置4，再右移到位置5
  • 位置5扫描 0，执行 R, R：右移到位置6，再右移到位置7
  • 位置7扫描空白，执行 P1, L：打印 1，左移到位置6
  • 结果： | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | 6 (E) | 7 (F) | |------|-------|-------|-------|-------|-------|-------|-------| | 初始状态内容 | ə | ə | 0 | | 0 | | | | 最终状态内容 | ə | ə | 0 | | 0 | 空白 | 1 | | 说明 | | | 机器初始位置 | | | 机器最终位置 | |

• 清理与回溯 (状态 p) ：

  • 操作：当遇到 x 时，执行 E, R 转到 q；当遇到 ə 时，执行 R 转到 f；当遇到空白时，执行 L, L 转到 p。
  • 执行：
  • 位置6扫描空白，执行 L, L：左移到位置5，再左移到位置4
  • 位置4扫描空白，执行 L, L：左移到位置3，再左移到位置2
  • 位置2扫描 ə，执行 R：右移到位置3，转到状态 f
  • 结果：（此步骤仅进行状态转移和清理，纸带内容不变） | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | 6 (E) | 7 (F) | |------|-------|-------|-------|-------|-------|-------|-------| | 初始状态内容 | ə | ə | 0 | | 0 | 空白 | 1 | | 最终状态内容 | ə | ə | 0 | | 0 | | 1 | | 说明 | | | 机器最终位置 | | | 机器初始位置 | |

• 递增 (状态 f) ：

  • 操作：当遇到任意符号时，执行 R, R 转到 f；当遇到空白时，执行 P0, L, L 转到 o。
  • 执行：
  • 位置3扫描 0，执行 R, R：右移到位置4，再右移到位置5
  • 位置5扫描 0，执行 R, R：右移到位置6，再右移到位置7
  • 位置7扫描 1，执行 R, R：右移到位置8，再右移到位置9
  • 位置9扫描空白，执行 P0, L, L：打印 0，左移到位置8，再左移到位置7
  • 结果： | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | 6 (E) | 7 (F) | 8 (E) | 9 (F) | |------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | 初始状态内容 | ə | ə | 0 | | 0 | | 1 | | | | 最终状态内容 | ə | ə | 0 | | 0 | | 1 | | 0 | | 说明 | | | 机器初始位置 | | | | 机器最终位置 | | |

• 查找与标记 (状态 o - 第二轮) ：

  • 操作：当遇到 1 时，执行 R, Px, L, L, L 转到 o；当遇到 0 时，转到 q。
  • 执行：
  • 位置7扫描 1（F方格），执行 R, Px, L, L, L
  • R：右移到位置8（E方格）
  • Px：在位置8（E方格）打印 x，标记位置7的 1
  • L, L, L：左移三次到位置5（F方格）
  • 结果： | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | 6 (E) | 7 (F) | 8 (E) | 9 (F) | |------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | 初始状态内容 | ə | ə | 0 | | 0 | | 1 | | 0 | | 最终状态内容 | ə | ə | 0 | | 0 | | 1 | x | 0 | | 说明 | | | | | 机器最终位置 | | 机器初始位置 | 标记符号 | |

• 查找与标记 (状态 o - 继续) ：

  • 操作：当遇到 1 时，执行 R, Px, L, L, L 转到 o；当遇到 0 时，转到 q。
  • 执行：
  • 位置5扫描 0（F方格）
  • 根据表格，遇到 0 时直接转到 q，不执行任何操作
  • 结果：（此步骤仅进行状态转移，纸带内容不变） | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | 6 (E) | 7 (F) | 8 (E) | 9 (F) | |------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | 初始状态内容 | ə | ə | 0 | | 0 | | 1 | x | 0 | | 最终状态内容 | ə | ə | 0 | | 0 | | 1 | x | 0 | | 说明 | | | | | 机器初始位置=最终位置 | | | | |

• 复制 (状态 q - 第二轮) ：

  • 操作：当遇到任意符号（0或1）时，执行 R, R 转到 q；当遇到空白时，执行 P1, L 转到 p。
  • 执行：
  • 位置5扫描 0，执行 R, R：右移到位置6，再右移到位置7
  • 位置7扫描 1，执行 R, R：右移到位置8，再右移到位置9
  • 位置9扫描 0，执行 R, R：右移到位置10，再右移到位置11
  • 位置11扫描空白，执行 P1, L：打印 1，左移到位置10
  • 结果： | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | 6 (E) | 7 (F) | 8 (E) | 9 (F) | 10 (E) | 11 (F) | |------|-------|-------|-------|-------|-------|-------|-------|-------|-------|--------|--------| | 初始状态内容 | ə | ə | 0 | | 0 | | 1 | x | 0 | | | | 最终状态内容 | ə | ə | 0 | | 0 | | 1 | x | 0 | | 1 | | 说明 | | | | | 机器初始位置 | | | | | 机器最终位置 | |

• 清理与回溯 (状态 p - 第二轮) ：

  • 操作：当遇到 x 时，执行 E, R 转到 q；当遇到 ə 时，执行 R 转到 f；当遇到空白时，执行 L, L 转到 p。
  • 执行：
  • 位置10扫描空白，执行 L, L：左移到位置9，再左移到位置8
  • 位置8扫描 x，执行 E, R：擦除 x，右移到位置9，转到状态 q
  • 结果： | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | 6 (E) | 7 (F) | 8 (E) | 9 (F) | 10 (E) | 11 (F) | |------|-------|-------|-------|-------|-------|-------|-------|-------|-------|--------|--------| | 初始状态内容 | ə | ə | 0 | | 0 | | 1 | x | 0 | | 1 | | 最终状态内容 | ə | ə | 0 | | 0 | | 1 | | 0 | | 1 | | 说明 | | | | | | | | 机器初始位置 | 机器最终位置 | | |

• 复制 (状态 q - 继续复制) ：

  • 操作：当遇到任意符号（0或1）时，执行 R, R 转到 q；当遇到空白时，执行 P1, L 转到 p。
  • 执行：
    • 位置9扫描 0，执行 R, R：右移到位置10，再右移到位置11
    • 位置11扫描 1，执行 R, R：右移到位置12，再右移到位置13
    • 位置13扫描空白，执行 P1, L：打印 1，左移到位置12
  • 结果： | 位置 | 1 (F) | 2 (E) | 3 (F) | 4 (E) | 5 (F) | 6 (E) | 7 (F) | 8 (E) | 9 (F) | 10 (E) | 11 (F) | 12 (E) | 13 (F) | |------|-------|-------|-------|-------|-------|-------|-------|-------|-------|--------|--------|--------|--------| | 初始状态内容 | ə | ə | 0 | | 0 | | 1 | | 0 | | 1 | | | | 最终状态内容 | ə | ə | 0 | | 0 | | 1 | | 0 | | 1 | | 1 | | 说明 | | | | | | | | | 机器初始位置 | | | 机器最终位置 | |

• 符号 ə 和 x 的具体作用 ：

• ə：就像赛跑时的起跑线，告诉机器“从这里开始”，防止机器在向左移动时跑出纸带范围。

• x：就像便利贴，贴在需要处理的数字旁边，告诉机器“下一个要处理的是这个数字”，处理完后就撕下来（擦除）。

• 与原文表格和完整构型的对应 ：

• 原文中的状态转移表格（第84-91行）详细定义了每个状态的行为
• 原文提到的完整构型表格（第93-95行）展示了机器运行的前几个状态

• 简化表示法 b : ə ə o 0 : ə ə q 0 : ... (C)（第98-99行）记录了运行过程中的状态变化

• F方格序列验证 ：

• 让我们跟踪F方格（奇数格）中的内容变化：

  1. 初始化后（状态 b 完成）：第1格 ə，第3格 0，第5格 0 → F方格序列：ə 0 0
  2. 第一轮复制后（状态 q 完成）：第1格 ə，第3格 0，第5格 0，第7格 1 → F方格序列：ə 0 0 1
  3. 第一轮递增后（状态 f 完成）：第1格 ə，第3格 0，第5格 0，第7格 1，第9格 0 → F方格序列：ə 0 0 1 0

• 去除起始标记 ə 后，第一轮完成后的数据序列为：0 0 1 0

• 这与目标序列 $001011011101111011111\ldots$ 的开头 0010 完全一致！

• 继续跟踪后续轮次：

  • 第二轮：复制 0 0 1，然后添加 1 → F方格序列：ə 0 0 1 0 0 1 1
  • 第三轮：复制 0 0 1 0 0 1，然后添加 1 → F方格序列：ə 0 0 1 0 0 1 1 0 0 1 0 0 1 1
  • 以此类推...

• 最终验证：去除起始标记 ə 后，F方格中的数据序列确实是 $001011011101111011111\ldots$

• 目标是生成 001011011101111011111... 序列，通过上述分析，我们可以看到机器确实能够在F方格中生成这个序列。整个过程中，ə 和 x 只是辅助工具，不影响最终的数字序列。

3. 机器运行逻辑解析（补充说明）

前面已经详细介绍了机器的运行步骤，这里再从算法角度做一些补充：

• 算法本质 ： 这台机器实际上是在执行一个拷贝并递增的递归算法：
• 每一轮都把当前的序列完整拷贝一遍
• 拷贝完成后在末尾添加一个 1

• 如此循环，实现序列长度和 1 的数量递增

• 状态转移图 ： b → o → q → p → q → p → ... → f → o → ...

• b 只在初始化时执行一次
• o → q → p 形成一个子循环，用于复制单个数字
• p → f 表示一轮复制完成

• f → o 开始下一轮拷贝并递增

• 为什么需要 E-方格 ：

• 如果没有 E-方格，就很难有复杂的条件判断和流程控制，如果所有格都是数值都挤在一排，机器很难区分哪些是数据，哪些是标记

• E-方格就像给数据“加标签”，让机器能够准确识别和操作目标数字，并且允许计算机其进行复杂的流程控制，来完成上面案例二所示的过程

• 运行效果验证 ：

• 初始：ə ə 0
• 第一轮：ə ə 0 0 → ə ə 0 0 1（添加第一个 1）
• 第二轮：ə ə 0 0 1 0 1（复制 0 和 1）→ ə ə 0 0 1 0 1 1（添加第二个 1）
• 第三轮：ə ə 0 0 1 0 1 1 0 1 1（复制前面的序列）→ ə ə 0 0 1 0 1 1 0 1 1 1（添加第三个 1）
• 以此类推，最终形成目标序列 001011011101111011111...

4. 完整构型的表示法

“该表也可以写成以下形式... $b : ə ə 0 \quad 0 : \ldots$”

• 图灵在这里介绍了描述图灵机快照的标准格式：
• 冒号分隔 ： 表示时间步。
• 状态字符位置 ： 将状态字符（如 $b, o, q$）写在被扫描符号的左边。
• 例如 a a q 0 表示：纸带内容是 a a 0，当前状态是 q，正在扫描最后一个 0。
• 这种表示法后来演变成了形式语言理论中的标准构型描述（Configuration Description）。

总结

这一章用了两个例子，一个简单，一个复杂，展示了图灵机不仅仅是一个数学定义，而是真的可以编程。 1. 编程技巧 ： 图灵展示了循环（Loop）、状态转移（State Transition）、辅助变量（E-squares）、标记法（Marking）等编程基本技法。 2. 数据结构 ： F-方格和 E-方格的交替使用，实际上定义了一种最原始的数据结构，用于解决在一条线性纸带上混合存储“数据”和“元数据”的问题。 3. 复杂性 ： 通过示例 II，图灵证明了即使极其简单的规则也能生成结构复杂的序列，暗示了图灵机的通用性。