[原创] AI的底层是什么？——从机械步骤到图灵机-茶余饭后-看雪安全社区

## 0. 引子

用户向 ChatGPT 输入一段文本，模型逐字逐句生成回复。这一过程在表象上呈现出理解与思考的特征，但如果拆开其内部机制，观察到的核心操作极为简单：**预测下一个符号。**

输入"1, 2, "——模型预测"3"。输入"if it rains, the ground will be "——模型预测"wet"。输入"柏拉图是古希腊著名的"——模型预测"哲学家"。模型并不理解这些符号的语义内涵。它不具备意识，也不进行自觉的推理。它所做的，是在统计意义上习得了一个条件概率分布：给定前文 token 序列，下一个 token 最可能是什么。[^1]

在 LLM 的用户界面之下，集成了反向传播、梯度下降、注意力机制、Transformer 架构等一系列复杂的数学工具。这些工具各自都是当代数学与计算机科学的结晶。但抛开这些具体实现，在最底层，**LLM 究竟是什么？**

## 1. 希尔伯特的形式化设想

1920 年代，大卫·希尔伯特提出了一个宏大的数学设想。

这一设想的核心是：将整个数学形式化为纯粹的符号系统。公理是初始符号串，推理规则是符号的改写规则。例如，从"$A \to B$"与"$A$"这两个符号串出发，可机械地推导出"$B$"。定理即为最终推导得到的符号串。在此框架下，判定一个数学命题是否为真，等价于执行一套机械的符号操作——操作者只需识别符号的形态，依照规则进行改写，无需理解符号的语义。

1928 年，希尔伯特将这一设想提炼为一个明确的问题：是否存在一个通用的**机械步骤**，能够对任意数学命题执行这种判定？这就是"判定问题"。

与 LLM 的预测行为相对照，两者在操作结构上呈现出形式上的相似性。希尔伯特追求的是逻辑保真——每一步改写必然保留真值，规则本身是铁定的。LLM 实现的则是统计推测——每一步预测基于训练数据中涌现的概率分布，规则是学出来的，不承诺保真。尽管规则的性质不同，但两者的底层操作对象是同一类实体：**无意义的符号，以及符号之间的变换规则。** [^2]

但"机械步骤"这一概念，在 1928 年尚无严格的数学定义。什么样的操作算是机械的？什么不算？机械性的边界在哪里？希尔伯特提出了问题，却没有给出"机械步骤"的定义。

这一基础性空缺，由艾伦·图灵在 1936 年填补。而图灵的回答，需要从最基础的地方开始。

## 2. 拆解一个机械步骤

要看清机械步骤的骨架，不能从抽象定义出发，而应当从最基础的实例入手。

有记载的最早的、具有明确操作步骤的计算过程，出现在公元前 300 年左右。欧几里得在《几何原本》中记录了一个求两个正整数最大公约数的方法——辗转相除法。它的操作规则如下：给定两个正整数，用较小的数除较大的数，取余数；若余数为零，则较小的数即为最大公约数；若余数不为零，则将原来的较小数与余数作为新的两个数，重复上述过程。

例如，求 $21$ 和 $15$ 的最大公约数：

- $21 \div 15 = 1$ 余 $6$。余数不为零，继续。
- $15 \div 6 = 2$ 余 $3$。余数不为零，继续。
- $6 \div 3 = 2$ 余 $0$。余数为零，停止。最大公约数为 $3$。

这个操作过程包含了一个机械步骤的全部要素：明确的输入与输出、有限条精确的操作规则、不需要直觉或创造力、必然在有限步内终止。拆解这个两千多年前的算法，我们就能看到：一个机械步骤，至少需要哪些组件。

### 2.1 计算的前提

在动手执行辗转相除法之前，有三个前提已经就位。

**纸。** 一块可以写入符号、读取符号、擦除重写的平面。操作者需要在纸上记录当前的两个数、中间计算结果（商和余数），以及最终的答案。草稿纸的容量理论上需要"足够"，用完可以再取。图灵将此理想化为一条无限长的纸带——纸带长度不是物理约束，而是数学抽象。

**笔。** 一支一次只能对准一个位置的笔。它的功能是读取当前位置的符号，擦除并写入新的符号，然后向左或向右移动一格。笔尖一次只能处理一个位置，正如人的笔尖无法同时书写两个字。这一装置在后续的模型中被称为读写头。

**约定符号。** 纸上可用的符号是预先约定的。对于辗转相除法，至少需要数字 $0$ 至 $9$、分隔符（用于区分两个操作数）、等号 $=$，以及表示"此处为空"的空白符 $\sqcup$。这一约定的符号集合，即为字母表。

在纸带上，我们可以这样编码辗转相除法的输入：两个操作数用分隔符隔开，等号标记答案区域的开始。以求 $21$ 和 $15$ 的最大公约数为例，纸带初始内容为：

$$
[2][1][|][1][5][=][\sqcup][\sqcup][\sqcup]
$$

读写头初始对准操作数区域的起始位置。

### 2.2 操作过程与关键组件

操作开始。操作者读取纸带上的两个数——$21$ 和 $15$。比较大小：$21 > 15$。用 $21$ 除以 $15$：商 $1$，余数 $6$。余数不为零，因此用 $15$ 和 $6$ 替换原来的两个数。纸带更新，读写头回到操作数区域起始位置。重复上述过程。

每一步的操作取决于两个因素：**当前纸带上的符号**（这是可读取的信息），以及**当前所处的操作阶段**（这是操作者心里的记忆——是"正在比较大小"，还是"正在做除法取余"，还是"正在判断是否终止"）。

在这个操作过程中，三个组件浮现出来。

**组件一：符号系统。** 操作对象是有限的、预先约定的符号集合——数字、分隔符、等号、空白符。这些符号本身没有意义，它们的"意义"完全由操作规则赋予。

**组件二：内部状态。** "当前处于哪个操作阶段"未被写在纸带上。它存储于操作者的短期记忆中。在辗转相除法中，可能的状态包括：比较两个数的大小、执行带余除法、判断余数是否为零、写入结果并停机。这一记忆的取值有限，但它决定了每一步做什么。在数学建模时，我们将其抽象为一个有限集：所有可能的内部记忆状态。

**组件三：操作规则。** 操作的每一步，取决于两个因素：当前的内部状态，以及当前读取到的符号。不同的状态-符号组合触发不同的动作——写入什么、向哪移动、切换到哪个新状态。这套规则必须是确定的：给定当前状态和当前符号，下一步的动作是唯一确定的。此外，这套规则还必须有一个终止条件。在辗转相除法中，终止条件是余数为零。

## 3. 图灵机：算法的数学定义

图灵的目标，是为希尔伯特的"机械步骤"提供一个严格的数学定义。他将前一节从辗转相除法中拆解出的组件——符号系统、内部状态、操作规则——连同纸带和读写头，一起抽象为一个数学模型。

需要明确区分的是：**图灵机是概念本身，七元组是该概念的形式定义。** 七元组之于图灵机，正如建筑蓝图之于建筑——蓝图刻画了结构，但蓝图本身不是建筑。

下表给出了辗转相除法中的直觉组件与图灵机形式化组件的对应关系：

| 辗转相除法中的直觉组件 | 图灵机的形式化对应 |
| :--- | :--- |
| 符号系统（数字、分隔符、等号、空白符） | $\Sigma$（输入字母表）、$\Gamma$（纸带字母表） |
| 内部状态（比较大小、做除法、判断余数等） | $Q$（有限状态集） |
| 操作规则（读-比较-除-替换-判断-移动） | $\delta$（转移函数） |
| 起始的内部状态 | $q_0$（初始状态） |
| 操作完成，成功停机 | $q_{\text{accept}}$（接受状态） |
| 异常终止 | $q_{\text{reject}}$（拒绝状态） |

一台图灵机 $M$ 的形式定义由这七个组件构成：

$$
M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})
$$

其中：

- $Q$ 是有限状态集。状态的个数是有限的，每个状态对应机械步骤执行过程中一种可能的内部记忆配置。
- $\Sigma$ 是输入字母表，包含允许在输入中出现的符号。$\Sigma \subseteq \Gamma$ 且 $\sqcup \notin \Sigma$。
- $\Gamma$ 是纸带字母表，包含所有可能在纸带上出现的符号。$\sqcup \in \Gamma$。
- $\delta$ 是转移函数：$\delta: (Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}) \times \Gamma \to Q \times \Gamma \times \{L, R\}$。给定当前状态 $q$（非终止状态）与当前读取符号 $a$，$\delta(q, a) = (q', b, D)$ 规定了下一步的状态 $q'$、写入符号 $b$ 和读写头移动方向 $D$（$L$ 左，$R$ 右）。
- $q_0 \in Q$ 是初始状态，计算机械步骤起始时的内部记忆配置。
- $q_{\text{accept}} \in Q$ 是接受状态，表示计算成功终止。
- $q_{\text{reject}} \in Q$ 是拒绝状态，表示计算异常终止。$q_{\text{accept}} \neq q_{\text{reject}}$。在本文展示的辗转相除法实例中，因输入均为合法正整数且算法必然停机，该状态不会出现；它在后续讨论"部分函数"与不可判定性时将作为关键角色登场。

每一步计算的定义如下：读写头读取当前格子的符号 $a$，当前状态为 $q$（非终止状态）。转移函数 $\delta(q, a) = (q', b, D)$ 给出三个信息——状态更新为 $q'$，当前格子写入符号 $b$，读写头沿方向 $D$ 移动一格。

这就是图灵机计算步骤的全部。没有理解，没有直觉，没有思考——只有符号的读取、符号的改写、状态的切换。

这里值得注意一个细节：$Q$、$\Sigma$、$\Gamma$、$\delta$ 的具体内容不是固定的。比较大小/做除法/判断余数只是 $Q$ 的一种可能设计，十进制数字只是 $\Sigma$ 的一种可能约定。这些组件的内容可以根据机械步骤的需求任意替换——只要保持有限性，结构就依然成立。

图灵提出这一模型，是为了回答希尔伯特 1928 年的问题。希尔伯特问：是否存在一个通用的机械步骤，能够判定任意数学命题的真假？图灵用图灵机证明了：这样的通用机械步骤不存在（停机问题不可判定）。但在给出这一否定回答之前，他必须先定义"什么叫机械步骤"。图灵机，就是"算法"这一概念的数学定义。[^3]

## 4. 验证：逐帧演算

为验证这一定义，我们用辗转相除法求 $21$ 和 $15$ 的最大公约数，运行一遍完整的图灵机演算。

需要说明的是，以下展示的是逻辑步骤。在物理图灵机中，"比较两个数的大小"和"做除法取余数"需要分解为多次读取、比较和写入操作。图灵已经证明：任何可以被高级语言描述的机械操作，都可以被编译为图灵机的基本步骤序列。这里为了集中展示状态切换和纸带变换的逻辑，将它们合并为单步描述。

**初始配置**

$$
\begin{aligned}
\text{纸带: } & [2][1][|][1][5][=][\sqcup][\sqcup][\sqcup] \\
\text{状态: } & q_{\text{start}} \\
\text{读写头: } & \text{位于操作数区域起始位置}
\end{aligned}
$$

约定纸带编码方案如下：两个操作数用分隔符 $|$ 隔开，$=$ 标记答案区域的开始。每一步逻辑上包括读取两个操作数、比较大小、执行带余除法、判断余数、替换操作数、重复或终止。

**步骤1：第一次辗转**

$$
\begin{aligned}
\text{当前状态: } & q_{\text{compare}} \\
\text{读取: } & \text{操作数 }A = 21\text{，操作数 }B = 15 \\
\text{比较: } & A > B\text{，执行 }A \div B \\
\text{计算: } & 21 \div 15 = 1 \text{ 余 } 6 \\
\text{判断: } & \text{余数 } 6 \neq 0\text{，继续} \\
\text{动作: } & \text{新操作数为 } 15 \text{ 和 } 6\text{，写入纸带，读头回到起始位置，转 }q_{\text{compare}}
\end{aligned}
$$

$$
\text{纸带: } [1][5][|][6][=][\sqcup][\sqcup][\sqcup][\sqcup]
\quad \uparrow \quad q_{\text{compare}}
$$

**步骤2：第二次辗转**

$$
\begin{aligned}
\text{当前状态: } & q_{\text{compare}} \\
\text{读取: } & A = 15\text{，}B = 6 \\
\text{比较: } & A > B\text{，执行 }A \div B \\
\text{计算: } & 15 \div 6 = 2 \text{ 余 } 3 \\
\text{判断: } & \text{余数 } 3 \neq 0\text{，继续} \\
\text{动作: } & \text{新操作数为 } 6 \text{ 和 } 3\text{，写入纸带，读头回到起始位置，转 }q_{\text{compare}}
\end{aligned}
$$

$$
\text{纸带: } [6][|][3][=][\sqcup][\sqcup][\sqcup][\sqcup][\sqcup]
\quad \uparrow \quad q_{\text{compare}}
$$

**步骤3：第三次辗转**

$$
\begin{aligned}
\text{当前状态: } & q_{\text{compare}} \\
\text{读取: } & A = 6\text{，}B = 3 \\
\text{比较: } & A > B\text{，执行 }A \div B \\
\text{计算: } & 6 \div 3 = 2 \text{ 余 } 0 \\
\text{判断: } & \text{余数 } 0 = 0\text{，终止} \\
\text{动作: } & \text{将 } B = 3 \text{ 写入答案区域，转 }q_{\text{accept}}
\end{aligned}
$$

$$
\text{纸带: } [6][|][3][=][3][\sqcup][\sqcup][\sqcup][\sqcup]
\quad \uparrow \quad q_{\text{accept}}
$$

**步骤4：停机**

$$
\begin{aligned}
\text{当前状态: } & q_{\text{accept}} \\
\text{动作: } & \text{停机}
\end{aligned}
$$

$$
\text{最终纸带: } [6][|][3][=][3][\sqcup][\sqcup][\sqcup][\sqcup]
$$

停机时，$=$ 右侧的内容为 $3$，即 $21$ 和 $15$ 的最大公约数，与手工执行辗转相除法的结果一致。

整个演算过程中，读写头在纸带上移动，读取符号，改写符号，内部状态在比较大小、执行除法、判断余数之间切换。每一步严格受转移函数 $\delta$ 的规定。纸带即草稿纸，内部状态即短期记忆，转移函数即操作规则。辗转相除法这一机械步骤的所有要素，均被图灵机精确刻画。

值得注意的是：辗转相除法的每一步都严格缩小了操作数的值（余数必然小于除数），因此对所有正整数输入都必然在有限步内停机。这是它作为"算法"的一个重要数学性质——并非所有机械步骤都具备这种必然停机的保证。

对于熟悉编程的读者，刚才的逐帧演算展示的正是编写一个函数时在底层发生的逻辑结构——纸带上的每一步改写对应变量值的更新，状态的每一次切换对应分支逻辑的跳转，而最终进入 $q_{\text{accept}}$ 停机，正如同函数执行到 `return` 语句后终止返回。编写一个保证对所有合法输入都停机的函数，就是在用图灵机的思维构造算法。

## 5. 收束：LLM 的机械骨架

七元组不是辗转相除法的模具。它是算法的通用定义：任何操作，当且仅当它可被分解为有限状态、有限符号约定与确定性转移规则时，它就是一个算法。[^4]

至于是否存在"一台能模拟所有机器的通用机器"，以及它与现代计算机的关联，我们留待后续再揭晓。回到 LLM：在最底层，其推理过程（前向传播）是确定的符号变换，数学上必存在一台（极其庞大的）图灵机与之等价执行。训练不过是借助数据搜索这套转移规则的过程。统计学习的外壳之下，是纯粹的机械骨架。[^5]

这引出一个更深的问题：图灵机究竟计算了什么？辗转相除法的每一步都是映射，三步串联即成输入到输出的函数。它对所有输入停机，是全函数。但有些机器会永不停机，它们计算的是**部分函数**。这种差异并非缺陷，而是可计算性深处某种结构的必然显现，它关乎一台机器能力的上限。而答案，正潜藏在另一条思想河流之中——在那里，函数不是被机器执行，而是被符号代换所定义。

---

**脚注**

[^1]: token（词元）是文本被切分后的基本单位，在数学抽象层次上可被视为符号——无意义的、等待被规则操作的符号。本文后续使用"符号"一词，以与图灵机的"纸带符号"保持术语一致。

[^2]: 这种相似性是操作结构层面的对应，不暗示历史继承关系。LLM 的直接学术谱系是连接主义传统（从 McCulloch-Pitts 神经元模型、感知机、反向传播到 Transformer），而非希尔伯特的形式化计划。两者在"对无意义符号执行有限规则变换"这一抽象层次上表现出结构上的对应性，这种对应性根源于图灵机所定义的"机械步骤"的一般框架。

[^3]: 严格而言，"算法即图灵机可执行的机械步骤"这一等同关系是丘奇-图灵论题的推论——该论题断言能行可计算函数与图灵可计算函数的等价性。该论题虽未被数学证明，但自1936年以来被所有试图形式化"可计算性"的尝试所印证，在理论计算机科学中被普遍接受。

[^4]: 需要明确的是，图灵机的七元组本身并不承诺停机。一个任意的图灵机可能在纸带上永远游荡。只有当这台机器对所有合法输入都在有限步内进入接受状态时，它才完全契合我们日常所说的"算法"（即总能给出答案的机械步骤）。辗转相除法恰好具有这一优良品质——我们称之为全函数。而不具备这一保证的机器，正是后续将要登场的部分函数的源头。

[^5]: 尽管现代 LLM 在生成阶段常使用采样策略（如 top-p 采样、温度调节）引入随机性，但前向传播过程——从输入序列到 logits 的计算——是确定性的。采样策略属于外部决策机制，不影响模型核心计算的确定性。

传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！！

最后于 2026-6-17 08:57 被云净天鉴编辑，原因：补充关于图灵机和C语言的关联说明

#杂谈