Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements
这是什么
这是一篇 2003 年的理论论文(arXiv cs/0309048,S2 引用 99 次),提出 Gödel Machine:一台与环境交互、目标是最大化期望累积 reward 的通用机器,其初始软件 p(1) 由两部分组成——一个(通常次优的)初始问题求解器 e(1)(比如任意传统 RL 算法),和一个证明搜索器。证明搜索器系统地枚举 proof techniques(输出证明的程序),一旦找到某个 switchprog 的"目标定理"——立即用 switchprog 改写 p 的期望效用严格高于保持 p 不变——就执行 switchprog,后者可以改写机器的任何部分,包括证明搜索器本身。
核心卖点是 Global Optimality Theorem:这种策略不是贪心的,因为"保持 p 不变"的效用已经隐含评估了未改动的 p 之后可能找到的所有替代 switchprog,所以第一次被证明有用的自改写就相对于初始证明搜索策略和资源限制是全局最优的,且所有 meta-meta-...层级自动坍缩为一层。收录它的原因是谱系溯源:2024-2025 年的 Darwin Gödel Machine、Huxley-Gödel Machine 等经验性 RSI 工作都以它命名,读那些工作前需要知道原版假设了什么、为什么 20 多年没人真正造出来。
机制与做法
机器的构造与目标定理
形式化设定:硬件是有单一生命周期的(可能空间受限的)通用图灵机,状态 s 中划出 time、输入 x、输出 y、代码 p 等变量;效用函数 u(s, Env) 定义为对未来 reward 之和的条件期望(公式 1),并把证明搜索本身的计算开销也计入。初始代码里编码了公理系统 A,包括:(a) 每条硬件指令如何改变状态,(b) p(1) 自身的描述(论文论证这不引入循环),(c) 环境的随机性质,(d) 效用函数 u。proof techniques 通过特殊指令(生成公理、应用推理规则、check 目标定理等)来延长当前 proof,目标定理的形式是"立即执行当前 switchprog 比保持 p 不变效用更高"。
BIOPS 与最优性声明
初始证明搜索器用 Bias-Optimal Proof Search(BIOPS),即 Levin Universal Search 的在线变体,按 2^{-l(w)} 的时间预算系统测试 proof techniques,阶(order)意义上 O()-最优;而与 Hutter 的 AIXItl、HSEARCH 等"硬编码搜索器"不同,Gödel Machine 原则上还能通过自改写消掉 O() 记号里隐藏的巨大常数/加性慢化项——前提是这种加速的效用可证。
论文自己列出的根本限制:由 Gödel 不完备性,任何包含算术的公理系统都存在真而不可证的命题,所以即使算力无限,机器也必须放弃那些无法在 A 内证明有效的自改进;可以构造病态的环境/效用函数使目标定理永远不可证;现实中资源受限的机器更是只能利用在时间/空间预算内证得完的改进。这些限制正是后来 DGM 等工作放弃"证明"、改用经验 benchmark 验证的动机。
关键结果
- Global Optimality Theorem(Thm 4.1):第一个被证明有用的自改写相对于初始证明搜索策略是全局最优的,无局部极大;所有 meta 层级坍缩为一层——一次目标定理的证明自动覆盖它对后续所有自改写的影响。
- 初始证明搜索器 BIOPS 是 Levin Universal Search 的在线扩展,具有最优复杂度阶;且不同于 AIXItl/HSEARCH 等前作,可证有用时能进一步压掉 O() 隐藏的常数级慢化。
- 论文明确承认三类不可绕过的限制:不可证的真命题(Gödel 1931)、可构造的病态环境使目标定理不可证(联系 Blum speed-up theorem)、资源受限下证不完的改进一律不能用。
- 全文没有实验、没有实现、没有伪代码级别以下的细节;结论一节留下的"实际问题"是该往公理系统 A 里加哪些定理作为初始 bias——这个问题论文没有回答。
实证核查
与我们方向的关系
对课题组读 DGM/HGM 这条线的直接价值是坐标系:原版 Gödel Machine 把"什么时候允许自我修改"定义为"证明了改写后效用更高",这是最强也最不可行的验证标准;DGM 把它降级为"在 SWE-bench/Polyglot 上分数变高",HGM 又加了对长期改进潜力的估计。比较三者时,关键差异就是验证信号的强度与可得性,而不是"自改写"本身——自改写在 2003 年就说清楚了。
另一个可借鉴的概念是 meta 层级坍缩:目标定理一次性覆盖对后续所有自改写的影响,避免无穷回归。现代经验性 RSI 没有这个性质(改坏评估器/选择器的风险始终存在),这正是 objective hacking / 评估腐蚀问题的理论根源,写综述或立论时可以引用本文 4.3 节和 FAQ 第 2、3 条作对照。