[原创] AI 在计算什么？——函数、λ 演算与丘奇-图灵论题-茶余饭后-看雪安全社区

[原创] AI 在计算什么？——函数、λ 演算与丘奇-图灵论题

发表于: 2026-6-22 20:55 1384

[原创] AI 在计算什么？——函数、λ 演算与丘奇-图灵论题

云净天鉴

2026-6-22 20:55

1384

## 0. 承接上篇

上篇文章中，我们从 LLM 的“预测下一个 token”出发，追问到最底层，发现了算法。我们拆解了辗转相除法，从中提炼出机械步骤的骨架——符号系统、内部状态、操作规则——然后见证了图灵如何用七元组将这些组件形式化为一个数学模型：图灵机。

上篇结束时留下了一个论断：**七元组是算法的通用定义。** 任何操作，当且仅当它可被分解为有限状态、有限符号约定与确定性转移规则时，它是一个算法。

但这个论断并不让人放心。图灵机的结构如此简单——一条纸带、一支读写头、有限个状态、一张转移规则表。它怎么能涵盖所有算法？排序、加密、编译、神经网络的前向传播、LLM 的推理——这些复杂操作，真的都能被塞进一个在纸带上读写符号的机械模型里吗？

要解答这个困惑，我们需要换一个视角。图灵机是从“机械操作”的角度定义计算的——纸带、读写头、状态表。但“通用性”这一性质，从机械操作的角度看并不直观：为什么有限的状态和规则能覆盖无限的算法？而如果我们从**数学函数**的角度来看——所有算法归根结底都在计算某个函数——通用性就变得自然得多：因为 λ 演算从一开始就是从“函数”出发构造的。本章将引入 λ 演算，展示它如何通过纯粹的符号代换定义函数，并最终与图灵机汇合于同一片数学疆域。

## 1. λ 演算：从符号代换出发的计算模型

### 1.1 定义：三种构造与一条规则

在图灵于剑桥写下图灵机定义的几乎同时，大洋彼岸普林斯顿的阿隆佐·丘奇正在用完全不同的方式追问同一个问题。

丘奇的出发点不是“机械操作”。他的出发点是**函数本身**。计算是什么？计算就是函数的代入与归约。给定一个函数和它的参数，用参数替换函数体中的形参，然后归约——反复应用这条规则，直到得到一个不能再归约的形式。

丘奇为此设计了一个极简的形式系统——**λ 演算**。它由三种语法构造和一条计算规则构成。

**三种语法构造**

- **变量**：`x`, `y`, `z`, … — 最基本的符号，代表某个值或函数。
- **抽象**（定义函数）：`λx. M` — 读作“λ x 到 M”，表示一个以 `x` 为参数、函数体为 `M` 的匿名函数。
- **应用**（调用函数）：`(M N)` — 表示将函数 `M` 应用于参数 `N`，就像我们写 `f(3)` 一样。

**一条计算规则：β-归约**

$$
(\lambda x. M) N \to M[x := N]
$$

这条规则的意思是：将函数 `λx. M` 应用于参数 `N`，就是把函数体 `M` 中所有参数 `x` 的出现替换为实参 `N`。记号 `M[x := N]` 就表示这个替换操作的结果——它不是一个等式判断，而是一个替换操作的产物。

### 1.2 详细解释：归约、替换与范式

现在我们来理解这套规则如何执行计算。

**从熟悉的函数出发**

在开始之前，将 λ 演算的“抽象”与我们熟悉的函数写法做一个对照会有帮助。数学中写 $f(x) = x + 1$：$f$ 是函数名，$x$ 是参数，$x + 1$ 是函数体。λ 演算做了同样的结构，但去掉了函数名，只保留参数和函数体：`λx. x + 1`。这就是“匿名函数”——它不需要名字，因为它的身份由参数和计算规则完全确定。

**什么是归约？**

“归约”这个词的直觉是：一个复杂的表达式，通过反复应用替换规则，被逐步“约化”为一个更简单的形式。每一步都不改变表达式的“值”，但改变了它的形态。可以想象数学中求函数值的过程：$f(x) = x^2$，求 $f(3)$ 时，我们先将参数代入函数体——$(x^2)[x:=3] \to 3^2 \to 9$。第一步“用 3 替换 x”正是 β-归约的核心操作。λ 演算把这种代入求值推广到所有函数。

**替换记号的含义**

$M[x := N]$ 是一个替换操作：它表示将表达式 $M$ 中所有名为 $x$ 的变量替换为表达式 $N$。例如，如果 $M$ 是 $x + 1$，$x$ 是参数，$N$ 是 $3$，那么 $(x + 1)[x := 3]$ 的结果就是 $3 + 1$。$[\;]$ 的内部指定了替换规则，外部是待替换的表达式。在 λ 演算中，被替换的对象是 λ 项。

**最简单的归约示例：恒等函数**

恒等函数 `λx. x` 接受一个参数并原样返回。将它应用于参数 `y`：

$$
(\lambda x. x) y \to x[x := y] = y
$$

函数体是 `x`，将 `x` 替换为 `y`，得到 `y`。这步 β-归约将应用表达式化简为了一个更简单的形式 `y`。

**稍复杂的示例：函数作为参数**

函数 `λx. x x` 接受一个参数 `x`，并将它应用于自身。将这个函数应用于 `λy. y`：

$$
\begin{aligned}
(\lambda x. x x) (\lambda y. y) &\to (x x)[x := (\lambda y. y)] \\
&= (\lambda y. y) (\lambda y. y) \\
&\to y[y := (\lambda y. y)] = (\lambda y. y)
\end{aligned}
$$

第一步将函数体的 `x` 全部替换为实参 `(λy. y)`，得到一个新的应用 `(λy. y) (λy. y)`；第二步继续 β-归约，将左侧的恒等函数应用于右侧的 `(λy. y)`，最终得到 `λy. y`。每一步都严格遵循替换规则，逐步化简。

**范式：计算的终点**

当没有任何 β-归约规则可以继续应用时，剩下的形式就是**范式**——也就是最终的计算结果。在上面恒等函数的例子中，`y` 是范式。在第二个例子中，`λy. y` 是范式。

λ 演算不涉及任何机器。它没有纸带，没有读写头，没有状态寄存器。它只有符号替换。但丘奇提出：**λ 演算能够定义所有“能行可计算”的函数。** 这个论断被称为“丘奇论题”。

### 1.3 完整构造：λ 演算中的辗转相除法

抽象语法和归约规则终究需要落地。我们以上篇的辗转相除法为例，展示如何用纯粹的 λ 项构造一个完整的算法。这需要分三步：编码数据、定义基本运算、组装算法逻辑。

**第一步：编码自然数——丘奇编码**

λ 演算里没有数字。我们需要用函数来表示自然数。丘奇给出了一个巧妙的方法：自然数 $n$ 被表示为“重复应用 $n$ 次”的函数。

- $0$：应用 0 次 — `λf. λx. x`
- $1$：应用 1 次 — `λf. λx. f x`
- $2$：应用 2 次 — `λf. λx. f (f x)`
- $3$：应用 3 次 — `λf. λx. f (f (f x))`
- 以此类推。

一般地，自然数 $n$ 的丘奇编码是 `λf. λx. fⁿ x`，其中 $f^n$ 表示 $f$ 复合 $n$ 次。可以验证，这种表示下的后继函数 `succ = λn. λf. λx. f (n f x)` 可以将 $n$ 的编码映射为 $n+1$ 的编码。

**第二步：编码条件分支与递归**

条件分支需要布尔值。丘奇编码中：

- **真**：`λa. λb. a` — 从两个选项中选取第一个
- **假**：`λa. λb. b` — 从两个选项中选取第二个

一个判断“是否为零”的函数 `is-zero` 可以这样定义：`is-zero = λn. n (λx. false) true`。如果 $n$ 是 $0$，则 $n$ 应用函数 $0$ 次，直接返回 `true`；否则返回 `false`。

递归需要特殊技巧。λ 演算中函数没有名字，不能直接调用自身。Y 组合子解决了这个问题：

$$
Y = \lambda h. (\lambda x. h (x x)) (\lambda x. h (x x))
$$

它的作用是为任何函数 $h$ 创造一个可以自引用的版本。`Y h` 会归约为 `h (Y h)`，从而实现递归。[^1]

**第三步：组装辗转相除法**

辗转相除法的核心逻辑是：$\mathrm{gcd}(a, b)$ = 如果 $b = 0$ 则返回 $a$，否则返回 $\mathrm{gcd}(b, a \bmod b)$。

我们需要：
- `is-zero` 判断 $b$ 是否为 $0$
- `mod` 计算余数
- Y 组合子提供递归

余数运算 `mod` 可以通过重复减法实现，其定义稍长但在 λ 演算中完全可构造。[^2]

有了 Y 组合子，我们可以将“递归调用自身”这个需求转化为一个显式的参数 $f$。`gcd` 的逻辑就变成了：给定函数 $f$（它将在递归时被替换为整个 `gcd` 自身），返回一个处理 $a$ 和 $b$ 的函数。

将所有这些组装起来，辗转相除法可以定义为一个 λ 项：

$$
\mathrm{gcd} = Y \left( \lambda f. \lambda a. \lambda b. \mathrm{if\mbox{-}zero } b \, a \, (f \, b \, (\mathrm{mod } a \, b)) \right)
$$

读作：如果 $b$ 为零，输出 $a$；否则，用 $b$ 和 $a \div b$ 的余数递归调用自身。

**从 λ 项到 Scheme 代码**

这个 λ 项的执行过程——反复 β-归约——与上篇中图灵机在纸带上反复改写符号的过程，在数学上是同一个算法的两种表述。图灵机通过状态切换和纸带移动来实现，λ 演算通过符号替换来实现。但它们计算的是同一个函数。

用 Scheme 语言来表达，这段逻辑几乎可以逐字翻译：

```scheme
(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (modulo a b))))
```

`define` 对应 λ 抽象，`gcd` 是函数名，`if` 是条件分支，递归调用对应 Y 组合子。这种对应不是巧合。1975 年，Gerald Sussman 和 Guy Steele 正是以 λ 演算为语义核心设计了 Scheme 语言——词法作用域、`lambda` 关键字、函数作为一等公民，这些特性直接继承自丘奇 1936 年的那篇论文。Scheme 及其衍生语言（Common Lisp、Clojure、Racket）的函数式核心，都可以追溯到 λ 演算。λ 演算不是博物馆里的古董——它是活的，活在每一行函数式代码里。

## 2. 等价性：图灵机与 λ 演算定义同一个函数类

### 2.1 图灵的证明

图灵在 1936 年论文的附录中证明了一个关键定理：**图灵可计算函数恰好是 λ 可定义函数。** 这个证明有两个方向——两个模型互相模拟。以下描述的是证明的核心思想，完整的证明需要定义编码方案并验证每一步转移的对应关系，但这两个方向足以揭示等价性为何成立。

### 2.2 方向一：图灵机模拟 λ 演算

λ 演算的计算过程是 λ 项的归约。给定一个 λ 项，一台图灵机可以在纸带上模拟这一归约过程。

具体思路如下：在纸带上维护当前 λ 项的符号表示。机器进入“扫描模式”，在纸带上寻找是否存在一个 β-可约式——即形如 `(λx. M) N` 的子项。如果找到了，机器进入“替换模式”，执行 $M[x := N]$ 的符号替换，将结果写回纸带。然后机器重新进入扫描模式，继续寻找下一个可约式。如果最终达到范式（无可约式），停机并输出范式。

这个模拟的关键在于：λ 项的语法是明确的，β-归约是确定的符号替换规则，图灵机完全可以在纸带上逐步执行这些操作。转移函数 $\delta$ 的状态可以用来编码“扫描”、“匹配”、“替换”等操作阶段。

### 2.3 方向二：λ 演算模拟图灵机

反过来，图灵机的每一步计算也可以被编码为一个函数。

图灵机的“配置”由三部分组成：当前状态、纸带内容、读写头位置。这些信息可以编码为数学对象。纸带内容可以表示为两个列表——读写头左侧的符号序列和右侧的符号序列；状态和当前符号可以作为查表参数。图灵机的每一步计算，就是从当前配置到下一配置的映射——这正是一个函数。

λ 演算可以通过各种编码方案（丘奇编码表示自然数和布尔值，斯科特编码表示列表结构等）来表示所有必要的数据结构。[^3] 图灵机的完整操作语义——初始配置、转移函数、停机判定——都可以在 λ 演算中被定义为一个 λ 项。这个 λ 项接收一个编码后的图灵机配置，输出下一个配置；反复应用，直到达到接受状态或拒绝状态。

如果图灵机最终停机，对应的 λ 项就归约到范式。如果图灵机永不停机，对应的 λ 项就永远无法归约到范式。

### 2.4 等价性的意义

双向模拟意味着：图灵机与 λ 演算定义了完全相同的函数类。图灵机本就是通用的，λ 演算也是通用的——两者独立地提出了自己的通用性论断。等价性定理的意义在于：它证明了这两个独立的论断指向的是同一个函数类。**通用性不是某个模型的特殊性质，而是可计算函数这个数学结构本身的属性。**

此后还出现了其他等价模型，我们将在第 4 节展开。理解了这一点，我们就有权利用最方便的视角来审视算法。而 λ 演算提供的视角，是**函数**。

## 3. 从 λ 演算看算法：函数与映射

λ 演算的核心只有一个：函数。函数的定义（λ 抽象）、函数的应用、函数的归约——这就是整个计算模型的全部内容。在这个框架下，算法就是函数的求值过程。给定一个函数和它的输入，反复应用 β-归约，直到得到范式。

那么，函数又是什么？

在数学中，**映射**是更原始的概念。给定两个集合 $X$ 和 $Y$，一个映射就是一种对应关系：它将 $X$ 中的某些元素指向 $Y$ 中的某个元素。映射只关心“谁对应谁”，不要求这个对应有什么规律可言。

**函数**是映射的一个子类。一个映射如果背后有一套有限的、机械的法则——告诉你从任意输入如何确定唯一输出——那它就是函数。

回到上篇的例子。辗转相除法实现了一个映射：$(21, 15) \to 3$，$(48, 18) \to 6$，$(35, 14) \to 7$……这个映射有法则——带余除法的规则。所以它是一个函数。我们用 $\mathrm{gcd}$ 来命名它：

$$
\mathrm{gcd}: \mathbb{Z}^+ \times \mathbb{Z}^+ \to \mathbb{Z}^+
$$

图灵机版辗转相除法实现了 $\mathrm{gcd}$，λ 演算版的辗转相除法也实现了 $\mathrm{gcd}$。实现的机制不同，但定义的是同一个函数。

## 4. 函数的泛化：揭示统一性的利与弊

我们已经看到，图灵机和 λ 演算这两个看似无关的模型，最终定义了同一个函数类。但它们为什么会汇合？答案藏在数学的一种核心思维方式之中——**泛化**。泛化能揭示深层统一性，但也可能掩盖差异，造成误解。

### 4.1 泛化的示范：加法如何成为函数

要理解什么是泛化，我们可以从一个更熟悉的例子开始：加法本身。

小学加法是具体的：$3 + 5 = 8$。你可以在算术本上摆出三个苹果加上五个苹果的对应操作。但数学家做了一件不同的事。他们把加法定义为一个映射：$(3, 5) \to 8$，$(2, 4) \to 6$，$(7, 1) \to 8$……无数个具体的算式，被统一为一种对应关系——每一对自然数指向它们的和。

这还不够。数学家进一步追问：这个对应关系背后的法则是什么？答案是：十进制下的逐位相加和进位规则。这是一个有限的、机械的法则。有了这个法则，映射就升级为**函数**——一个有法则的映射。

最后一步是剥离。这个函数不关心被加的是苹果还是金币，不关心是十进制还是二进制，不关心是写在纸上还是存在内存里。它只关心结构的法则：加法定义了一个从两个输入到一个输出的映射，这个映射满足结合律、交换律，有一个单位元 $0$，每个元素 $a$ 都有一个相反数 $-a$。在数学上，满足这些条件的集合和运算被称为**群**（即满足封闭性、结合律、有单位元、每个元素有逆元的集合与运算）。满足这些条件的运算，数学家就叫它“加法”。

这就是泛化：从具体操作出发，抽出映射关系，抽出核心法则，剥离实现细节，将法则应用到一切满足条件的对象上。

### 4.2 泛化之利：揭示深层统一性

泛化的核心力量在于统一。十进制加法、向量加法、椭圆曲线上的“点加法”——这些操作在实现上毫无共同之处，但泛化让我们看到，它们共享同一个群结构。

图灵机和 λ 演算同样如此。图灵从“机械操作”出发，抽出了纸带、状态和转移规则。丘奇从“符号代换”出发，抽出了抽象、应用和归约。他们的出发点不同，所用的语言不同，但最终划出的边界完全重合。十进制加法和椭圆曲线点加法满足同一个群结构，图灵机和 λ 演算定义同一个函数类——两者的逻辑是相通的：**数学不关心内容，只关心结构。**

### 4.3 泛化之弊：掩盖差异，造成误解

然而，泛化也有其代价。它用统一的结构覆盖了截然不同的实现细节，而这些细节，恰恰是初学者理解和操作的入口。

初学者翻开密码学教材，看到“椭圆曲线上的点加法”，脑子里浮现的是 $3 + 5 = 8$，然后一头雾水。椭圆曲线上的“加法”操作是这样的：给定曲线上两点 $P$ 和 $Q$，画一条穿过它们的直线，这条直线与曲线交于第三点 $R$，然后取 $R$ 关于 $x$ 轴的对称点，记作 $P + Q$。这与十进制逐位相加毫无关系。

数学家坚持叫它“加法”，是因为椭圆曲线上的点连同这个几何操作，恰好满足阿贝尔群的所有公理。但从学习者的角度看，这个命名极易产生误导——它让人误以为椭圆曲线上的操作与算术加法有某种“实现上的”相似性。实际上，两者的相似性只存在于抽象的公理层面。

这种“泛化带来的误导”在 λ 演算中也同样存在。λ 演算从函数中抽出了抽象和应用，剥离了所有实现细节——没有纸带，没有状态寄存器，没有指令集，没有内存布局。任何可计算函数，只要能被定义，就可以被编码为 λ 项。这揭示了计算最纯粹的本质结构，但同时也掩盖了“具体计算需要消耗多少时间和空间”这一事实——后者正是复杂度理论研究的对象，是算法在工程实践中不可回避的约束。

### 4.4 在利与弊之间：理解泛化的分寸

泛化的利与弊，本质上是一枚硬币的两面。它通过剥离细节来揭示统一性，而这种剥离必然会导致某些具体信息的丢失。数学家的任务，不是在“泛化”和“具体”之间二选一，而是在恰当的层次上使用泛化，同时清醒地认识到它丢失了什么。

图灵机与 λ 演算的关系正是泛化分寸的典范。它们证明了“可计算函数”这一结构独立于任何具体模型而存在——这是泛化最深刻的胜利。但与此同时，它们保留了对“计算”的完整定义：图灵机保留了机械操作的直觉，λ 演算保留了符号代换的直觉。它们没有过度泛化到丢失定义本身，而是在各自的道路上，抵达了同一个数学结构。

## 5. 丘奇-图灵论题与算法-函数等价性

此后，哥德尔和克林尼从函数构造的角度提出了**部分递归函数**——从几个极简的初始函数（常数函数、后继函数、投影函数）出发，通过代入、原始递归和极小化来构造新函数。这个体系也被证明与图灵机和 λ 演算等价。

图灵机、λ 演算、部分递归函数——三个独立的数学体系，三种完全不同的直觉——机械操作、符号代换、函数构造——最终在同一条边界上汇合。这一事实引出了理论计算机科学中最著名的论题：

> **丘奇-图灵论题**：能行可计算函数恰好是图灵可计算函数，也恰好是 λ 可定义函数。

之所以称为“论题”而非“定理”，是因为“能行可计算”是一个非形式化的直觉，无法给出严格的数学定义。我们无法“证明”图灵机覆盖了所有可计算函数——我们只能通过反证法证明某些函数不可图灵计算。

令人瞩目的是，八十多年来，所有后来提出的、形式化程度不同的计算模型——while-程序、马尔可夫算法、元胞自动机、寄存器机——无一例外地被证明与这三种模型等价。**至今未发现任何反例**——没有任何一个被直觉上认为“能行可计算”的函数，被证明超越了图灵机的能力。这一事实使得丘奇-图灵论题在理论计算机科学中被普遍接受，但它终究是一个论题而非定理。是否存在我们尚未发现的、非图灵可计算但仍在某种意义下“机械可执行”的计算模式？这个问题至今开放，值得持续追问与探索。

从丘奇-图灵论题可以直接推出本文的核心命题：

> **所有算法都是函数求值器。**

一个算法，就是某个函数的机械实现。一个函数是可计算的，当且仅当存在一个算法（图灵机、λ 项、或等价模型）实现它。这不是一个比喻，也不是一个哲学立场。这是刻在可计算性理论大厦地基上的数学事实。

## 6. 收束：LLM 的函数本质与“函数之镜”

### 6.1 LLM 是函数求值器

现在，回到这个系列最初的问题：LLM 是什么？

上篇揭示了 LLM 的机械骨架——它是算法，是图灵机。本篇从 λ 演算的视角出发，揭示了算法的数学本质——算法是函数的机械实现。

因此，LLM 是一个函数求值器。它的输入是上文 token 序列（编码为数值向量），它的输出是下一个 token 的概率分布。它的前向传播过程——从嵌入层到 Transformer 层的逐层计算——是确定的、有限步的。在数学上，这个计算过程可以被一台图灵机执行，也可以被一个 λ 项定义。它计算的是一个**函数** $f_\theta$：

$$
f_\theta: \text{上文 token 序列} \rightharpoonup \text{下一个 token 的概率分布}
$$

训练 LLM，就是用一个优化算法（梯度下降）在函数空间中搜索参数 $\theta$，使得 $f_\theta$ 逼近人类文本的条件概率分布。推理 LLM，就是反复调用 $f_\theta$，每次把新生成的 token 拼回上文，再调用一次。

### 6.2 函数之镜

希尔伯特的形式化梦想、欧几里得的辗转相除法、图灵机的纸带操作、丘奇的 λ 演算（其结构清晰地回响在 Sussman 和 Steele 的 Scheme 语言中）、哥德尔与克林尼的部分递归函数、当代的神经网络与 LLM——这些来自不同时代、不同领域的思想创造，在最底层汇聚到了同一个点上：它们都在定义函数，实现函数，求值函数。

图灵机和 λ 演算，表面上是两种不同的计算模型，但它们最终回答了同一个问题：**什么是可计算函数？** 它们划定了函数的边界——在这个边界之内，函数是可计算的；在这个边界之外，是不可计算的。

“可计算函数”这个数学结构，就是一面镜子。在这面镜子里，古希腊的算术操作、20 世纪的数理逻辑、21 世纪的深度学习，显现为同一个东西——**函数的求值器。**

**脚注**

[^1]: 此形式适用于正规序归约。在按值调用的 λ 演算中，需使用 Z 组合子以避免无穷归约：$Z = \lambda h. (\lambda x. h (\lambda v. x x v)) (\lambda x. h (\lambda v. x x v))$。Scheme 等语言通过 `letrec` 或内置递归机制实现递归，而非直接翻译 Y 组合子。

[^2]: 丘奇编码下，加法、乘法、前驱、减法、比较谓词和取余运算均有标准定义。例如，取余运算 `mod` 可通过重复减法实现。这些构造的细节超出本文范围，但它们的存在保证了 λ 演算足以表达辗转相除法的全部操作。

[^3]: 丘奇编码通常指自然数和布尔值的编码方案。列表等结构的编码有更高效的方案（如斯科特编码）。此处统称“各种编码方案”以涵盖所有必要的数据结构。

冰与火的战歌：Windows内核攻防实战高级班！从零到实战，融合AI与Windows内核攻防全技术栈，打造具备自动化能力的内核开发高手。

收藏・0

点赞・0

打赏