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

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

发表于: 1天前 533

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

云净天鉴

1天前

533

0. 承接上篇

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

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

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

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

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

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

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

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

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

三种语法构造

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

一条计算规则：β-归约

$(λ 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：

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

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

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

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

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

第一步将函数体的 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 = λh . (λ x . h (xx)) (λ x . h (xx))$

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

第三步：组装辗转相除法

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

我们需要：

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

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

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

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

$gcd = Y (λ f . λa . λb . if \mbox - zero b a (f b (mod a b)))$

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

从 λ 项到 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]$ 的符号替换，将结果写回纸带。然后机器重新进入扫描模式，继续寻找下一个可约式。如果最终达到范式（无可约式），停机并输出范式。

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

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

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

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

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

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

2.4 等价性的意义

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

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

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

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

那么，函数又是什么？

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

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

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

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

图灵机版辗转相除法实现了 $gcd$ ，λ 演算版的辗转相除法也实现了 $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_{θ}$ ：

$f_{θ} : 上文 token 序列 ⇀ 下一个 token 的概率分布$

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

6.2 函数之镜

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

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

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

脚注

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