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

原文

2. Definitions.

Automatic machines.

If at each stage the motion of a machine (in the sense of ( §1 ) ) is completely determined by the configuration, we shall call the machine an "automatic machine" (or ( a ) -machine).

For some purposes we might use machines (choice machines or ( c ) -machines) whose motion is only partially determined by the configuration (hence the use of the word "possible" in ( §1 ) ). When such a machine reaches one of these ambiguous configurations, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machines to deal with axiomatic systems. In this paper I deal only with automatic machines, and will therefore often omit the prefix ( a ) -.

Computing machines.

If an ( a ) -machine prints two kinds of symbols,of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial ( m ) -configuration,the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.

At any stage of the motion of the machine, the number of the scanned square, the complete sequence of all symbols on the tape, and the ( m ) -configuration will be said to describe the complete configuration at that stage. The changes of the machine and tape between successive complete configurations will be called the moves of the machine.

Circular and circle-free machines.

If a computing machine never writes down more than a finite number of symbols of the first kind, it will be called circular. Otherwise it is said to be circle-free.

A machine will be circular if it reaches a configuration from which there is no possible move, or if it goes on moving, and possibly printing symbols of the second kind, but cannot print any more symbols of the first kind. The significance of the term "circular" will be explained in ( §8 ) .

Computable sequences and numbers.

A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle-free machine.

We shall avoid confusion by speaking more often of computable sequences than of computable numbers.

以下是对原文的中文翻译。

翻译

2. 定义

自动机器

如果在每个阶段，一个计算机器（指上一章 §1 中定义的机器）的动作完全由构型（configuration）决定，就将称该机器为“自动机器”（或 a-机器，这个a是automatic，就是自动的意思）。

某些特定目的下，我们还可能会使用另一种机器（选择机器或 c-机器，这个c是choice，就是选择的意思），这种机器的动作只有部分是由由构型决定（因此 §1 中使用了“可能”一词）。当这样一台机器达到某些模棱两可的构型时，就无法自主地继续运行了，而需要外部操作员做出任意的某种选择。如果我们使用机器来处理公理系统，就会出现这种情况。在本文中，咱们只处理自动机器，因此通常会省略前缀 a-。

计算机器

如果一台自动机器打印两种符号，其中第一类完全由 0 和 1 组成，称为数字（而其他的称为第二类符号），那么这台机器将被称为计算机器。如果给机器提供一条空白纸带并使其开始运转，从正确的初始 m-构型开始，它打印出的第一类符号的子序列将被称为由该机器计算出的序列。通过在这个序列前加上一个小数点而获得的二进制小数所表示的实数，被称为由该机器计算出的数。

在机器运转的任何阶段，被扫描格的编号、纸带上所有符号的完整序列以及 m-构型，将被统称为描述该阶段的“完整构型”。机器和纸带在连续两个完整构型之间的变化被称为机器的“步骤（moves）”。

循环机器与无循环机器

如果一台计算机器写下的第一类符号永远不超过有限个，它将被称作“循环的”（circular）。否则，它被称为“无循环的”（circle-free）。

如果一台机器能够到达一个没有后续步骤的构型，或者如果它继续运转只可能打印第二类符号，但无法再打印任何第一类符号，这样的机器就是循环的。“循环”一词的意义将在 §8 中解释。

可计算序列和可计算数

如果一个序列可以由一台无循环机器计算出来，那么该序列被称为可计算的。如果一个数与由无循环机器计算出的数相差一个整数，那么该数就是可计算的。

为了避免混淆，我们将更多地谈论可计算序列，而不是可计算数。

逐段解析

1. 自动机器 (Automatic machines) vs 选择机器 (Choice machines)

“如果在每个阶段，机器...的动作完全由构型决定，我们将称该机器为‘自动机器’（或自动机器）。”

• 决定性 (Determinism)：这是现代计算机的核心特征。给定当前状态和输入，下一步的动作是唯一确定的。这就是算法的本质。图灵在这里定义的 a-机器 就是我们现在所说的标准图灵机。

“出于某些目的，我们可能会使用...选择机器...其动作仅部分由构型决定...除非外部操作员做出某种任意选择...”

• 非决定性与交互：图灵极其敏锐地预见到了非确定性（Nondeterminism）或交互式计算的概念。
• c-机器 (Choice machine)：可以类比为需要用户输入的程序，或者证明助手（Proof Assistant），在关键步骤需要人来指引方向（比如在公理系统中选择使用哪条公理）。
• 不过图灵明确表示，本文只关注自动机器（a-机器），即不需要人为干预的自动化算法。这就降低了复杂性，将讨论集中于自动的场景。

2. 计算机器 (Computing machines)

“如果一台自动机器打印两种符号，其中第一类（称为数字）完全由 0 和 1 组成...”

• 二进制：图灵直接采用了二进制（0和1）来定义计算产生的数，这与现代计算机的底层表示完全一致。
• 数据 vs 辅助标记：
• 第一类符号 (Figures)：0 和 1。这是真正的“输出”，构成了计算结果（实数的小数部分）。
• 第二类符号 (Symbols of the second kind)：即前文提到的“草稿”或“辅助记忆”。这是图灵机在计算过程中使用的中间变量，用来辅助记忆或标记位置，不作为最终结果输出。

“在机器运转的任何阶段，被扫描格的编号、纸带上所有符号的完整序列以及 m-构型，将被统称为描述该阶段的‘完整构型’。”

• 完整构型 (Complete Configuration)：这是整个系统的快照 (Snapshot)。它包含了：
• 机器在哪里（当前机器内纸带在整个纸带当中的位置）。
• 纸带上有什么（当前机器内纸带上的所有数据）。
• 机器在想什么（m-构型/内部状态）。
• 只要有了“完整构型”，我们就可以完全复原或暂停/重启这台机器。这对应了现代操作系统中的“进程上下文”或“核心转储 (Core Dump)”。

3. 循环机器 (Circular) 与 无循环机器 (Circle-free)

这部分的术语定义可能有些反直觉，需要特别注意。

“如果一台计算机器写下的第一类符号永远不超过有限个，它将被称作‘循环的’（circular）。”

• 术语的直观含义：这里的“循环”指的是机器陷入了某种不再产出新成果的死循环状态。
• 状态解析：如果一台机器在纸带上写了几个数字后，就不再写新的数字了（可能它停机了，也可能它还在空转、移动、写草稿，但就是不再输出结果），那么它就无法完成“计算一个无限小数”的任务。图灵用“循环”来描述这种非生产性的状态。

“否则，它被称为‘无循环的’（circle-free）。”

• 持续生产的能力：与之相对，“无循环”意味着机器能够无限地、持续地产出新的数字（0或1）。
• 计算实数的必要条件：因为无理数（如 $\pi$）的小数位是无限的，要计算它，机器必须是一个“无循环机器”——即它永远不停止工作，并且源源不断地输出下一位数字。这才是图灵定义中“成功”的计算机器。

4. 可计算序列和可计算数

“如果一个序列可以由一台无循环机器计算出来，那么该序列被称为可计算的。”

• 定义核心：可计算性建立在“能够构造出一台不断输出该序列的机器”这一基础上。
• 例子：
• 可计算序列：例如序列 101010...（无限循环的10），我们可以很容易造出一台图灵机，它不停地交替打印1和0。因此，这个序列是可计算的。
• 不可计算序列：如果一个序列是完全随机的（没有任何规律，也不能由任何算法生成），我们就造不出这样的机器。这样的序列就是不可计算的。

“为了避免混淆，我们将更多地谈论可计算序列，而不是可计算数。”

• 严谨性：处理二进制序列（01串）比处理数学上的实数更直接、更纯粹。
• 为什么避谈“数”？
• 实数的复杂性（一数多码问题）：在数学中，同一个实数可能对应不同的符号表示。
  • 经典案例：$0.999... = 1$：
  • 设 $x = 0.999...$
  • 则 $10x = 9.999...$
  • 相减得 $9x = 9$，即 $x = 1$。
  • 这意味着，虽然序列 0.999... 和 1.000... 看起来完全不同，但它们在数学上指向同一个数。
  • 二进制中的情况：同样地，在二进制中，0.111... （即 $\sum_{n=1}^{\infty} 2^{-n}$）也等于 1.000...。
• 图灵机的困境：如果图灵机要判断两个“数”是否相等，它必须比较它们的序列。但面对 0.111...（二进制下的 $1$）和 1.000...（也是二进制下的 $1$），机器只能一位一位地看：
  • 数值背景（二进制小数详解）：
  • 这不是计算机内部存储用的原码/补码，而是纯数学上的二进制小数表示。
  • 小数点：和十进制一样，小数点右边的位表示分数值。
  • 位权：
    • 十进制 0.99...：第一位 $9$ 代表 $9 \times 10^{-1}$，第二位 $9$ 代表 $9 \times 10^{-2}$...
    • 二进制 0.11...：第一位 $1$ 代表 $1 \times 2^{-1}$（即 $0.5$），第二位 $1$ 代表 $1 \times 2^{-2}$（即 $0.25$）...
  • 求和：0.111... = $0.5 + 0.25 + 0.125 + \dots = 1$。
  • 比较过程：
  • 第一位：机器看到一个是 0，一个是 1。
  • 此时机器陷入两难：虽然第一位不同，但如果后面全是一串 1 和一串 0，它们可能还是相等的。
  • 机器不能草率下结论说“不相等”，它必须继续看下去。但由于是无限小数，机器可能永远在等待“反转”的那一刻，从而陷入无限等待，无法给出确定的“相等”判断。
• 图灵的解决方案：为了避开“一数多码”这种数学定义上的歧义，图灵决定只谈序列（Sequence）。
  • 序列 0111... 和序列 1000... 就被当作了两个不同的可计算序列。
  • 至于它们是否代表同一个数学实数，那是后续解释层面的事，不影响图灵机本身的运行机制。
  • 这种关注语法（Syntax，即符号本身）而非语义（Semantics，即符号代表的数）的处理方式，是计算机科学处理复杂问题的核心智慧。

总结与意义

这一章主要完成了形式化定义的铺垫，为后续的证明打下基础：

1. 锁定研究对象：确定只研究自动机器（确定性算法），排除了人为干预。
2. 规定输出格式：使用二进制，并明确区分了结果数据（0/1）和辅助数据（草稿）。
3. 定义“成功”的计算：引入了独特的“无循环” (Circle-free) 概念。
   • 这点非常关键：图灵眼中的“计算实数”，是一个永无止境的过程。
   • 一个好的程序（对于计算实数而言）是不应该停机的，也不应该陷入“只思考不输出”的僵局。
   • 它必须像流水线一样，源源不断地生产出下一位数字。

这一章的定义展示了图灵的在数学和工程两方面的直觉：他既关心数学上的严格性（实数定义），又关心工程上的实现机制（机器状态、纸带快照）。