第22章:自指与涌现——当推理系统开始推理关于自身
Curry-Howard 对应告诉我们:证明即程序。那么,程序在证明什么?
第21章的最后一段把我们带到了这里:一个强大到足以开始包含关于自身命题的推理系统。在这个时刻,第15章的哥德尔结构重新出现。
但第22章不是第15章的重复。哥德尔说的是边界——你永远无法抵达的那些真命题。第22章说的是开口——在这个边界周围涌现的新事物。
下卷九章的逻辑演绎走到这里,我们终于站得足够高,可以向下俯瞰。这是最诚实的几章之一:有些问题,我们只能陈述,无法解决。
22.1 Curry-Howard:证明即程序
第14章建立了一个形式系统:命题、推理规则、证明。第19章发现,计算与逻辑在复杂度层面是等价的:SAT 是 NP 完全的,而在命题逻辑中寻找一个证明,最坏情况下与 SAT 一样难。
但这种等价有多深?
Curry-Howard 对应(也叫命题即类型对应)给出答案:深到不能再深。
精确地说,它建立了以下对应:
| 逻辑 | 类型论 / 程序 |
|---|---|
| 命题 | 类型 |
| 命题 | 类型 |
| 函数类型 | |
| 积类型 | |
| 和类型 | |
| 空类型(无居民类型) | |
| 假言推理 | 函数应用 |
| 演绎定理 | 函数抽象( |
这不是比喻——而是同构:逻辑推导的每一步,对应程序中的一个计算步骤;证明的规范化(化简到最简形式),对应程序的求值(运行至终止)。
很多人会在这里点头,然后继续把“逻辑”和“程序”当成两回事。同构意味着:你在逻辑里证明的每一步,就是编程语言里的一个计算步骤;你写的每一个函数,都在“证明”某个命题。如果这没让你感到震撼,你还没有真正理解这个对应在说什么。
一个命题“有证明”,当且仅当它对应的类型“有程序”——对应类型是“有居民的”。证明即程序,命题即类型,验证即运行程序。
在 Curry-Howard 对应之前,数学和计算机科学是两个相邻但分离的领域。对应告诉我们:它们是同一件事的两种语言。每一个数学定理都可以被理解为一个程序;每一个程序都在“证明”某个命题——证明它的输出类型可以从输入类型构造出来。这不是哲学上的相似性,而是可以用形式化手段精确验证的等价。Lean、Coq、Agda 这些证明助手正是建立在这个等价之上:写程序就是写证明,类型检查就是证明验证。
22.2 不动点:自指的代数
第15章的哥德尔句
但自指并不只出现在哥德尔定理中。它有一个更一般的代数结构:不动点。
定义(不动点):给定函数
在 λ 演算(程序的最简核心语言)中,有一个著名的不动点组合子
对任意函数
展开来看,这个等式表明
Y 组合子与 λ 演算:程序的“最简核心”
λ 演算(Lambda Calculus)是阿隆佐·丘奇(Alonzo Church)与图灵同时代(1930 年代)提出的计算模型,比图灵机更紧凑:只有三类元素——变量、函数抽象(
def f(x): return f(x-1),但在纯 λ 演算中,函数没有名字,因此无法直接引用自身。
这与自指有什么关系?
用这套语言来说,哥德尔的对角化引理就是“可证性谓词”的不动点:存在命题
自指、不动点与对角化,是同一个数学结构在不同语境下的不同名字。
22.2.3 实操:三步展开 Y 组合子
Y 组合子的定义:
用阶乘函数的递归定义来追踪展开过程。设
注意,self 参数是一个函数——给
现在计算
第0步(定义):
设
第1步(展开一层):
把 self 参数。展开
现在
第2步(在
计算
第3步(继续展开):
收集结果:
关键观察:每一步,self,然后调用它。但 self 就是
将此与哥德尔句
: —— 是 的不动点; 的每一次展开都把自身重新传给 : —— 是谓词“不可证”的不动点, 断言了一个关于自身可证性的命题
两者是同一个数学结构:找到一个对象,使得对它施加某种变换后的结果,在等价意义下就是这个对象本身。
手工展开 Y 组合子三步,你会获得一种无法从定义中得到的感觉:自指不是黑魔法,而是可以一步步追踪的机制。
22.2.5 MP 游戏:证明序列作为动力系统
假言推理(Modus Ponens,MP)是命题逻辑最基本的推理规则:有
教科书给出证明的静态定义:一个有限公式序列
但如果我们动态地看它呢?
游戏设定:定义函数
轨道的三种命运:
- 表面停止:序列到达某个
,使得 ——形式上是一个不动点。但这只说明后继项等于自身,并不保证 是真正的 QED。 可能是一个自指构造;“停止”只是周期为 1 的循环这一特殊情形。 - 有限循环:存在
使得 ——轨道绕圈,没有新内容涌现。 - 无限延伸:序列永不终止——这对应不可判定性。没有算法能对任意给定的
和初始公式判定轨道是否会停止。
柯西条件与停机的微妙之处:判断第一种命运是否“真正完成”,等价于问:序列是否成为柯西序列?
在
退化为“序列最终为常数”——即最终不动。
现实计算机的栈空间有限,所以我们手工施加一个截断条件——不是在极限处自动停止,而是从外部施加的停机。这个外部条件,在足够强的系统中,无法被系统自身内化。
不动点是证明的终点——但只有当极限点有意义时才是。当
这不只是比喻。对角化引理说:对任意公式
Curry-Howard 的视角:在 CH 同构下,公式对应类型,证明序列对应程序的归约序列,
MP 游戏把三件事统一在同一个框架里:证明的结构、动力系统的轨道、递归类型的不动点。它们是同一个数学对象在逻辑、分析、类型论三种语言中的不同读法。
这个游戏的真正危险在第三种命运:无限延伸的轨道。你无法从外部判断一条轨道是否会停止——这不是因为你的计算能力不够,而是因为它在原则上不可判定。每当你写下一个证明,你实际上是在声称:这条轨道会停止,而且会停在我希望的地方。在足够强的系统中,这个声称无法被系统自身验证。
22.2.6 代码中的 MP 游戏
这些轨道足够小,可以直接运行。下面的程序展示了轨道的全部三种命运——表面停止、有限循环、无限延伸——然后是柯西陷阱,最后是镜子的一个微缩版:哥德尔句作为变换“不可证”的不动点。
#!/usr/bin/env python3
"""
mp_game.py -- the MP Game of Chapter 22: proof sequences as orbits.
Book reference: The Reasoning Kingdom, Volume 2, Chapter 22, Section
22.2.5 "The MP Game: Proof Sequences as Dynamical Systems."
A proof is usually a finished object: a finite sequence of formulas. The
MP game reads it dynamically: p_{n+1} = f(p_n), one modus ponens per
step, and a proof becomes an orbit of a dynamical system. An orbit has
exactly three fates -- and this program runs all three, plus the two
subtleties the book warns about:
1. apparent stopping: f(p) = p, but is p a TRUE QED?
2. finite cycle: no new content ever appears;
3. infinite extension: the orbit never ends (undecidable, in general);
4. the Cauchy trap: a converging sequence whose limit point is not
where the transformation rests;
5. the mirror: the Goedel sentence as a fixed point of the
transformation F(phi) = "not provable(phi)",
built here as a tiny self-referential program
(Chapter 15's companion script runs the full
numbering machinery; this is the miniature).
Run: python3 mp_game.py
"""
def orbit(f, x0, n):
"""The first n+1 points of the orbit x0, f(x0), f(f(x0)), ..."""
out = [x0]
x = x0
for _ in range(n):
x = f(x)
out.append(x)
return out
def demo():
print("=" * 70)
print(" THE MP GAME -- proof sequences as dynamical systems")
print(" The Reasoning Kingdom, Volume 2, Chapter 22 (Sec. 22.2.5)")
print("=" * 70)
# Fate 1: apparent stopping.
f1 = lambda x: x if x <= 0 else x - 1
print("\nFate 1 -- apparent stopping: f(x) = max(x-1, 0), start at 5")
print(" orbit:", orbit(f1, 5, 8))
print(" f(0) = 0, a fixed point. But 'stopping' only says the")
print(" successor equals itself -- it does not guarantee 0 is a TRUE")
print(" QED. Apparent stopping is a cycle of period 1.")
# Fate 2: finite cycle.
f2 = lambda x: (x + 1) % 3
print("\nFate 2 -- finite cycle: f(x) = (x+1) mod 3, start at 0")
print(" orbit:", orbit(f2, 0, 7))
print(" round and round; no new content ever emerges.")
# Fate 3: infinite extension.
f3 = lambda x: x + 1
print("\nFate 3 -- infinite extension: f(x) = x+1, start at 0")
print(" orbit (first 8 points):", orbit(f3, 0, 7))
print(" it never terminates. And for an arbitrary f, no algorithm")
print(" can decide whether the orbit will ever stop -- that is")
print(" undecidability in principle, not slow hardware.")
# The Cauchy trap.
print("\nThe Cauchy trap:")
print(" sequence p_n = 1/n is Cauchy and converges to 0,")
print(" but under the transformation f(x) = x + 1, f(0) = 1.")
print(" the limit exists; the transformation does not rest there.")
print(" The Cauchy condition guarantees the limit EXISTS -- not that")
print(" the limit point is the TRUE answer.")
# The mirror: fixed point of "not provable".
THEOREMS = {"T1", "T2"} # a toy provability predicate over strings
def provable(s):
return s in THEOREMS
q = "q = %r; content = not provable(q %% q)"
G = q % q
scope = {"provable": provable}
exec(G, {"__builtins__": {}}, scope)
print("\nThe mirror -- G as a fixed point of F = 'not provable':")
print(f" G = {G}")
print(f" what G says, computed: {scope['content']}")
print(f" provable(G) = {provable(G)}")
print(" so G <-> not provable(G): G is a fixed point of the")
print(" transformation F(phi) = not Prov(<<phi>>). The diagonalization")
print(" lemma in Chapter 15 is the same fixed point, grown to full")
print(" arithmetic; the miniature here shows its shape.")
print("=" * 70)
if __name__ == "__main__":
demo()22.3 依赖类型:命题作为对象
Curry-Howard 对应在简单类型论中成立。但如果我们把类型系统变得足够强——允许类型依赖于值——会发生什么?
依赖类型允许这样的表达:类型
依赖类型:让类型携带“证明”(前人工作:Martin-Löf, 1975)
在普通编程语言中,类型和值是分离的:int 是类型,42 是值,类型并不知道具体的值是什么。
依赖类型打破了这种分离:类型可以依赖于值。
例子:
- 普通类型:
Vec<int>(整数向量,长度未说明) - 依赖类型:
Vec<int, 5>(恰好 5 个整数的向量;长度被编码进类型)
为什么有用? 因为更精确的类型 = 更强的编译期检查。如果函数签名是 concat : Vec<A, m> -> Vec<A, n> -> Vec<A, m+n>,编译器会自动验证拼接后的长度是正确的——不需要运行时检查,越界不可能发生。
与 Curry-Howard 的关系:在依赖类型中,“
在依赖类型下,Curry-Howard 对应扩展到一阶逻辑:
| 一阶逻辑 | 依赖类型 |
|---|---|
依赖类型系统(如 Martin-Löf 类型论)实现了数学的一个古老梦想:数学对象的构造与数学命题的证明,在同一种语言中统一处理。证明一个命题,就是构造一个具有对应类型的程序;构造一个数学对象,就是写出对应类型的一个居民。
这不是形式上的把戏,而是一种深刻的统一:数学与计算、命题与数据、证明与程序——在足够精确的语言中,它们是同一件事。
22.4 推理系统推理自身:边界重现
现在来到本章最核心的问题。
一个推理系统——无论是形式逻辑系统、学习算法,还是大语言模型——一旦它足够复杂并开始推理关于自身,第15章的模式就不可避免地出现。
在形式系统层面:哥德尔定理说,任何足够强的一致系统都拥有它无法证明的真命题(包括关于自身一致性的命题)。把
在学习系统层面:第21章的结论是,一个学习系统的归纳偏置无法从数据内部确定——它是外部输入。一个学习系统无法从自己的训练数据中推断自己的归纳偏置是否合适,正如一个形式系统无法从自身的公理中证明自身的一致性。
把这句话读两遍。这不是说归纳偏置很难选择;而是说,从原则上讲,数据无法告诉你,你的归纳偏置是否合适——正如一个形式系统无法从内部证明自身的一致性。第21章与第15章之间真正的联系就在这里:学习的盲点与逻辑的不完备性,是同一个结构性限制的两种语言。
在大语言模型层面:这是前沿,也是最未解决的问题。通过训练,大语言模型获得了语言结构的某种内部表示。这种表示是否包含“推理规则”的某种近似?当模型“推理”自己的推理过程时(例如思维链),它在做什么?
研究界讨论的一个非正式猜想:Transformer 的注意力机制,在足够的规模与足够的训练下,实现了某种隐式因果推断——通过在上下文中选择相关位置,它执行了一种近似的条件独立性测试,这与第18章的 d-分离具有结构性相似。这不是一个被证明的定理,而是一个需要精确数学刻画的猜想。如果它在某种意义上成立,那么大语言模型就不只是模式匹配器,而是在执行某种近似的因果推断——这个结论将深刻重塑我们对 AI 推理能力的理解。但“在某种意义上”是一个很大的逃生舱;现有的理论工具还无法把这个猜想变成定理。
22.5 涌现:当量变引发质变
自指与不动点解释了“系统推理关于自身”的代数结构。但还有另一个现象,在复杂系统中广泛存在,而且更难形式化:涌现。
涌现说的是:当部分足够多、相互作用足够丰富时,系统会展现出任何单个部分都不具备、也无法从部分的简单求和中预测的性质。
在大语言模型的训练实践中,涌现已经被观察到:当模型规模越过某个阈值时,某些能力(如算术推理、多步推理)会突然出现,而在更小的模型中完全不存在。这些“突然出现”的能力被称为涌现能力。
涌现的三个层次
涌现不是单一现象;它至少发生在三个层次上,每个层次对应不同的理论工具。
第一层:组合涌现。简单的原子组合出新的行为能力,即使没有任何单个原子独自具备这种能力。水分子由氢和氧组成——氢和氧各自都不“湿”,但组合起来就获得了“湿”这一宏观性质。这是涌现最基本的形式,相变理论可以大致描述它——在临界点附近,系统的行为发生剧烈变化。
第二层:计算涌现。图灵机的单条规则(
第三层:表示涌现。在大语言模型中,数十亿参数经过训练后产生的能力(如类比推理、情感识别、代码生成)不是任何单个参数的功能,也不在设计者的计划之中。训练目标(下一个 token 预测)不包含“理解情感”或“写代码”的明确指令——但这些能力在足够大的规模上显现出来。
问题:是否存在涌现的理论?
但涌现在形式理论中极难处理。它不是一个可以被精确定义的数学概念——至少,现有的数学工具还不够。我们有描述,没有解释;有观察,没有预测。
信息论提供了一些线索。涌现可以被理解为:系统的总描述长度短于其各个部分的描述长度。一团气体由
动力系统理论提供了另一种视角:涌现对应相变——当某个参数越过某个临界值时,行为发生剧烈而质的变化。这种视角对物理系统具有解释力,但对于神经网络的涌现(能力随规模增长而突然出现),目前还没有精确的预测框架。
有研究者指出:所谓的“涌现”,可能部分地是测量方式的产物。如果用连续的(而非离散的)性能指标来衡量,一些被认为突然涌现的能力实际上是在平滑增长的——只是在某个阈值处,平滑增长越过了任务所要求的最低能力门槛,从而被观察者注意到。这并不否认涌现的存在,但要求更精确的刻画:性能曲线是真的存在不连续点,还是我们的测量工具引入了虚假的不连续?目前尚无共识。
22.6 下卷的边界,也是开口
从第14章到第22章,这条路是这样的:
从形式系统的基础,到一致性与完备性的极限,到对资源敏感的线性逻辑,到概率对真值的扩展,到因果推断对干预的形式化,到复杂度理论对推理代价的几何刻画,到启发式的形式契约,到学习作为逆推断,最后到自指与涌现。
每一章都是被前一章留下的问题逼出来的。每一章的结尾都留下一个问题,而那个问题让下一章成为必然。
沿着这条路,我们触及了几个边界:
- 哥德尔边界:足够强的系统拥有无法从内部看见的真命题。
- 图灵边界:某些问题原则上无法被任何算法回答。
- 复杂度边界:某些问题原则上无法被高效解决。
- 归纳偏置边界:学习系统无法从内部确定自己的归纳偏置是否合适。
这些边界不是障碍,而是地图。它们告诉我们:在推理这件事中,哪些地方是人类和机器都无法抵达的,哪些地方可以抵达但代价高昂,哪些地方可以用近似换取可行性。
最后,有一个问题,这本书没有回答,也无法回答:
AI 系统目前展示的推理能力,在这张地图上处于什么位置?
它已经走了多远,它的边界在哪里,它是否在逼近某些形式理论的边界,还是在完全不同的地方工作?这不是一个用现有工具就能回答的问题——不是因为问题不重要,而是因为我们还没有足够精确的语言来陈述它。
建立这样的语言,是接下来几十年的工作。
22.7 从逻辑到动力学:三个遗留问题
MP 游戏给了我们一个新视角:证明序列
一条轨道有三种命运:有限停止(不动点)、有限循环、无限延伸。
但这个游戏留下了三个逻辑工具无法回答的问题:
问题一:轨道停在哪里?
不动点
问题二:收敛的能量是什么?
如果轨道确实收敛,就一定存在某个单调递减的量——某种“能量”。逻辑中没有能量的概念。但如果我们把信念空间
问题三:能量从何而来?
传统做法是手工猜测一个能量函数,并验证它递减。但如果我们已经观测到系统收敛到某个先验锚点
这三个问题里,前两个在第12章已经有了严格答案:永霖定理把收敛方向钉在先验锚点
MP 游戏是逻辑与动力学之间的渡船。在逻辑这一岸,我们问“证明存在吗?”;在动力学那一岸,我们问“系统去哪里?”。不动点是两岸共享的地标——在逻辑中它是证明的终点,在动力学中它是吸引子。渡过去,你会发现那个吸引子有一个名字:永霖极限。
悬而未决
Curry-Howard 对应能延伸到多远? 目前,这个对应在简单类型论和一阶逻辑层面是精确的。高阶逻辑(二阶逻辑、高阶逻辑)、模态逻辑和线性逻辑(第16章)都有不同形式的 Curry-Howard 对应,但精确程度和完备程度各不相同。是否存在一个统一的框架,把所有形式逻辑系统都纳入“命题即类型”的视角?这是同伦类型论(Homotopy Type Theory,HoTT)试图回答的问题,但 HoTT 本身仍在发展之中。
是否存在关于涌现的数学理论? 复杂性科学、相变理论和信息论各自提供了对涌现的部分刻画,但没有一个统一的、可预测的涌现理论。大语言模型的涌现能力能否在某个形式框架内被预测和解释,还是说它本质上是一种理论无法预先捕捉的经验现象?
自指推理的能力边界:当一个 AI 系统推理自己的推理过程时,它能发现哪些关于自身的真命题,又必然会从内部看不见哪些边界?这不仅是一个哲学问题,而是一个关于 AI 安全与可解释性的实际问题——一个无法推理自身极限的系统,会在什么情况下用自信的错误替代诚实的不确定性?
MP 游戏留下的动力学缺口:如果证明序列是一条轨道,那么不动点只是“停止”的名字,而不是“停在正确地方”的保证。第12章用 KL 能量面和压缩映射回答了“能量是什么、为什么递减”;第23章接着回答“收敛得多快、这个速率如何随规模变化”。逻辑语言到此为止,后面交给动力学。
思考题
★ 热身
Curry-Howard 对应的核心是:命题对应类型,证明对应程序。对以下每个逻辑命题,写出它在类型论中对应的类型(使用函数类型
(同一律) (弱化) (合取消去) (析取引入)
对第1条,写出一个“居住”在这个类型中的具体程序(函数),并验证它所对应的确实是“
★★ 推导
不动点展开:
组合子满足 。手工展开 的前三步(把这读作阶乘函数的递归定义)。追踪展开过程,并清楚解释 是如何“创造”递归的。 哥德尔句与 Y 组合子:哥德尔句
说“我不可证”; 满足 。两者都是自指构造,但结果不同: 导致不可判定性, 导致无限循环(或递归展开)。列出它们在以下方面的异同:(1) 自指的机制;(2) 自指的后果;(3) 自指被“解决”的方式(如果有的话)。
★★★ 挑战
依赖类型系统(如 Martin-Löf 类型论)把“
考虑这个命题:“对所有自然数
- 在依赖类型论中,这个命题对应什么类型?用
-类型的语言写出来。 - 这个命题的“证明”(即居住在这个类型中的程序)是什么样子?它接受什么输入,返回什么?
- 现在考虑:类型检查(验证一个程序具有给定类型)等价于验证一个证明。这个验证操作是可判定的吗?(提示:依赖类型使类型检查变得更难——与简单类型系统相比,复杂度如何变化?)
第3个问题触及依赖类型系统的实际极限:功能越强大,类型检查的代价越高;某些依赖类型系统的类型检查甚至是不可判定的——这又是贯穿全书的律令“越强大,代价越高”的一次体现。
第3个问题没有标准答案。它是下卷在技术层面提出的最后一个开放问题——边界处的形式工具开始触及那些超出形式化范围的问题。在那个边界上,逻辑与直觉、证明与猜想、形式与意义,以一种我们尚未完全理解的方式彼此纠缠。
