递归定理

1. 1. 导言

递归定理（recursion theorem）是递归函数论——即可计算性理论（computability theory，研究"什么问题原则上可以被机械地计算"的学科）——中的一组基本定理，由 Stephen Cole Kleene 提出，合称 Kleene 递归定理，包括两条：第一递归定理说，任何用递归方式定义的函数方程都有可计算的（最小）解——机械式的递归定义永远合法、永远有解；第二递归定理说，对任何可计算的全函数 f，总存在源程序 c，使得执行 c 与执行 f(c) 效果完全相同（[math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math]）——程序可以合法地引用自己的代码。

两条之中，第二递归定理尤为重要，它是数学中对"自指"（self-reference）现象最简洁、最有力的统一陈述：它只有一步对角线证明 `c = S(e, e)`（S 是"把程序的部分输入写死、生成新程序"的柯里化操作，详见 §2.3），却统一了从罗素悖论（1901）、Gödel 不完备定理（1931）、Turing 停机问题（1936）、von Neumann 自复制自动机（1948）到今天的 quine 程序（1960s）等全部自指现象——它们本质上是同一种对角线/自指结构的不同化身（详 §5.7）。


图1：六个经典自指现象——Cantor 对角线（1891）、Russell 悖论（1901）、Gödel 不完备定理（1931）、Turing 停机问题（1936）、von Neumann 自复制（1948）、Quine（自打印程序，1960s）——都源于同一种对角线/自指原理；Kleene 第二递归定理是这一原理最一般的陈述。

---

1. 1. 总览：两个定理各说了什么

Kleene 递归定理是关于自指（self-reference，即一个系统"谈论"自身）与不动点（fixed point，即变换后保持不变的点）的两个基本定理的合称。先用日常语言各说一遍，再给出精确表述。

第二递归定理（日常语言版）：对任何可计算的全函数 f（一个对任何输入都停机的"程序变换"），总存在一个源程序 c，使得执行 c 的效果，等同于执行 f(c)——即 f 拿着 c 自己的源代码算出来的那个程序。 用符号写就是：[math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math]。

第一递归定理（日常语言版）：任何递归定义——即把一个函数在某处的值，写成它自己在其他输入上的值（比如阶乘 fac(n) = n[math]\displaystyle{ \cdotfac(n−1) }[/math]）——都必然有解，而且其中"最小"的那个解一定能被机器算出。 换句话说，机械式的递归定义永远合法、永远有解。

两个定理的对照表（其中涉及的符号会在第二节逐一解释，此处可先跳过细节）：

| |第一递归定理（First Recursion Theorem, FRT）|第二递归定理（Second Recursion Theorem, SRT）| | -------- | -------------------------------------------------------- | ------------------------------------------------------------------------------------- | |作用对象|函数本身（"把函数变成函数"的规则）|程序的编号（代码）| |结论|任何可计算的函数变换规则 [math]\displaystyle{ \Psi }[/math] 都有最小不动点 [math]\displaystyle{ \phi }[/math]，且 [math]\displaystyle{ \phi }[/math] 是可计算的：[math]\displaystyle{ \Psi(\phi) = \phi }[/math]|任何可计算的程序变换规则 f 都有不动点 n：程序 n 与程序 f(n) 计算同一个函数，记作 [math]\displaystyle{ \phi_n = \phi_{f(n)} }[/math]| |数学血统|序理论中 Knaster–Tarski 不动点定理的"可计算版本"|对角线方法（diagonalization，Cantor、Gödel、Turing 用过的同一种论证技术）的集大成者| |别称|弱递归定理|强递归定理、Kleene 不动点定理| |首次出现|Kleene (1952)《元数学导论》中明确表述|Kleene (1938) §2 末尾，当时甚至没有名字，证明只有两行|


图2：两个定理的"不动点"含义截然不同——左：函数 [math]\displaystyle{ \phi }[/math] 经变换 [math]\displaystyle{ \Psi }[/math] 后变回 [math]\displaystyle{ \phi }[/math]（函数层面）；右：程序 n 经变换 f 后变成另一个程序 f(n)（通常 f(n) [math]\displaystyle{ \neq n }[/math]），但 [math]\displaystyle{ \phi_n = \phi_{f(n)} }[/math]（代码变了，行为不变）。§2.5 对此有详细辨析。

第二递归定理被 Moschovakis 称为 "令人惊叹的"（amazing）——他的综述标题就叫 Kleene's Amazing Second Recursion Theorem；计算机科学家 Neil Jones 称之为"可计算性的瑞士军刀"（A Swiss Pocket Knife for Computability）〔转引自 Kiselyov, §1〕。它的一行证明看似只是个小技巧，却支撑了从 Gödel 不完备定理到序数理论、从程序自复制到有效描述集合论的庞大理论大厦（详见第五、六节）。

---

1. 1. 预备知识：读懂本词条所需的全部概念

本节用程序员熟悉的语言解释文中会反复出现的五个概念。已经熟悉的读者可以跳过。

1. 1. 1. "可计算"与"部分函数"

可计算的（computable / effective / recursive）：一个函数是"可计算的"，意思是存在一套固定的、有穷的指令（程序），使得对任何输入，只要机械地按指令执行有穷多步，就能得到输出。"可计算的"（computable）、"有效的"（effective）、"递归的"（recursive）在本文中是同义词——这是历史造成的术语冗余，三个词来自 Church、Turing、Gödel–Kleene 三条等价的技术路线。

部分函数（partial function）：一台机器在某些输入上可能永远不停机（死循环），这时它在这些输入上没有输出。我们把"在部分输入上有定义、在其余输入上无定义"的函数称为部分函数；在所有输入上都有定义的称为全函数（total function）。程序天然对应部分函数，而不是数学课本里那种"处处有值"的函数——这是可计算性理论与普通数学的第一个思维差异。

记号 [math]\displaystyle{ \phi_e }[/math]：把全体程序（的所有可计算部分函数）排成一个序列，用自然数 0, 1, 2, [math]\displaystyle{ \ldots }[/math] 编号，[math]\displaystyle{ \phi_e }[/math] 表示"编号为 e 的程序所计算的那个部分函数"。这个编号也叫哥德尔数（Gödel number）：关键思想是"程序本身也是一个有限符号串，可以编码成一个自然数"，于是程序即数据——程序可以作为另一个程序的输入被处理。[math]\displaystyle{ \phi_e(x) }[/math] 表示"编号 e 的程序在输入 x 上的输出"（可能无定义）。本文中 p [math]\displaystyle{ \downarrow }[/math] 表示"程序 p 停机（有输出）"，p [math]\displaystyle{ \uparrow }[/math] 表示"不停机（无输出）"。

1. 1. 1. 通用程序（解释器）

存在一台"通用机器"：给它输入 (e, x)，它就模拟编号 e 的程序在输入 x 上的运行。这就是今天的解释器 / 虚拟机思想，Turing 1936 年的通用图灵机是它的首个化身。用记号写就是：存在程序 i 使得 [math]\displaystyle{ \phi_i(e, x) = \phi_e(x) }[/math]。

1. 1. 1. S-m-n 定理（柯里化 / 参数特化）

S-m-n 定理说：给定一个双输入程序和它的第一个输入，可以机械地生成一个"把第一个输入写死在程序里"的新单输入程序。用程序员的话说，就是柯里化（currying）或部分应用（partial application）总是可以机械完成的：存在可计算的全函数 S，使得

> [math]\displaystyle{ \phi_{S(e, y)}(x) = \phi_e(y, x) }[/math]

即"程序 S(e,y)"在输入 x 上的行为 = "程序 e"在输入 (y, x) 上的行为。Kleene 1938 年论文中的 S 函数就是这个工具。第二递归定理的证明只需要这一个工具，此外什么都不需要——这是它惊人简单的原因。

1. 1. 1. 递归可枚举集（r.e. set）

一个自然数集合称为递归可枚举的（recursively enumerable, r.e.），如果存在一台机器能把它的元素一个一个地全部列出来（允许重复、允许乱序；不在集合里的元素永远不会被列出）。等价地，r.e. 集就是某个程序有定义的输入的集合（即 [math]\displaystyle{ \phi_e }[/math] 的定义域），记作 [math]\displaystyle{ W_e }[/math]。典型例子："所有会停机的 (程序,输入) 对"构成的集合（停机问题集合 K）是 r.e. 的，但它的补集不是——这正是"停机问题不可判定"的现代表述。

1. 1. 1. "不动点"的两种含义（重要！）

"不动点"在本文中出现于两个截然不同的层面，混淆它们是最常见的理解障碍：

- 函数层面的不动点（第一递归定理）：变换规则 [math]\displaystyle{ \Psi }[/math] 把函数 [math]\displaystyle{ \phi }[/math] 变成新函数 [math]\displaystyle{ \Psi(\phi) }[/math]；若 [math]\displaystyle{ \Psi(\phi) = \phi }[/math]（作为函数处处相等），[math]\displaystyle{ \phi }[/math] 就是 [math]\displaystyle{ \Psi }[/math] 的不动点。这与分析学中"f(x) = x 的解"同类。 - 代码层面的不动点（第二递归定理）：变换规则 f 把程序编号 n 变成新编号 f(n)；注意 f(n) [math]\displaystyle{ \neq n }[/math] 通常成立——程序代码确实变了；但神奇的是，新程序 f(n) 和旧程序 n 计算的函数相同：[math]\displaystyle{ \phi_n = \phi_{f(n)} }[/math]。所以"不动"的不是代码，而是代码的行为。Rogers 为此特意造了"不动点值（fixed-point value）"一词，强调它不是数值不动点。

---

1. 1. 历史背景

1. 1. 1. 起源：一篇研究"序数记号"的 6 页短文

第二递归定理诞生于 Kleene 1938 年发表于《符号逻辑杂志》（The Journal of Symbolic Logic）的一篇仅 6 页的短文《论序数的记号》（On Notation for Ordinal Numbers）。这篇论文的主题表面上与"递归定理"毫不相干：

> 背景知识——序数（ordinal number）：序数是"无限队列的长度"的数学化。数完 0, 1, 2, 3, [math]\displaystyle{ \ldots }[/math]（全体自然数）之后，数学上允许继续数：第一个"超过所有自然数"的序数记作 [math]\displaystyle{ \omega }[/math]，然后还有 [math]\displaystyle{ \omega+1 }[/math], [math]\displaystyle{ \omega+2 }[/math], [math]\displaystyle{ \ldots }[/math], [math]\displaystyle{ \omega\cdot2 }[/math], [math]\displaystyle{ \ldots }[/math], [math]\displaystyle{ \omega^2 }[/math], [math]\displaystyle{ \ldots }[/math], [math]\displaystyle{ \omega^\omega }[/math], [math]\displaystyle{ \ldots }[/math]，可以无限延伸。所有"能用可数步骤达到"的序数称为可数序数，它们的总体（第二数类）是不可数的。 > > Church 与 Kleene 在 1930 年代问了一个构造性问题：能不能给每个可数序数起一个"机械可读的代号"（自然数编码），使得仅凭代号就能机械地判断：这个序数是 0、是某个序数的后继（+1）、还是某个递增序列的极限？并且在后两种情况下能机械地取出前驱代号或序列代号？ 满足这些条件的编码方案称为一个序数记号系统（Kleene 称之为 r-system）。

Kleene 在论文 §2 中建立了可计算函数的基本技术（编号、通用函数、§2.3 的 S 函数），然后在 §2 的最后顺手陈述并证明了一个当时没有名字的定理：

> 若 [math]\displaystyle{ \psi(z, x) }[/math] 是任意可计算的部分函数，则存在一个数 f，使得 [math]\displaystyle{ \phi_f(x) = \psi(f, x) }[/math] 对所有 x 成立（等号含义：两边同时无定义，或同时有定义且相等）。 > > 证明：设 e 是函数 [math]\displaystyle{ \psi(S(y,y), x) }[/math] 的编号，取 f = S(e, e) 即可。

——这就是第二递归定理的原始形态。Moschovakis 称之为 Kleene 没有意识到自己发掘出的"小宝石"（little gem）；Kiselyov 则以"函数式珍珠（A Functional Pearl）"为题向函数式编程社区重新发掘了它。

这个"小宝石"随即在论文 §3 被用于证明该文的主要结果：存在一个"通用"序数记号系统 [math]\displaystyle{ S_1 }[/math]——任何其他合法记号系统能命名的序数，[math]\displaystyle{ S_1 }[/math] 都能命名，且翻译过程本身是可计算的。这是"沿着序数逐层向上做递归定义"（后来称为有效超限递归，effective transfinite recursion）这一方法的首次应用。Kleene 由此构造出著名的记号系统 O（Kleene's O），并证明存在最小的一个"不可命名"的序数——Church–Kleene 序数 [math]\displaystyle{ \omega_1^CK }[/math]，即可数序数中第一个无法被任何机械记号系统触及的序数。

1. 1. 1. 命名史

- Kleene 本人始终只叫它 "the recursion theorem"（递归定理）——即使在他 1952 年的《元数学导论》（Introduction to Metamathematics）中两个定理同时出现时，也未加区分。 - Rogers (1967) 在其经典教材第 11 章首次建议：在两个定理同台的语境中，把关于"函数变换规则的不动点"的定理称为第一递归定理（Rogers 书中 Theorems XI、XII），把 Kleene 1938 的定理称为第二递归定理（Rogers 书中 Theorem IV）。Moschovakis 明确表示支持："在允许投票的场合，我投票采纳 Rogers 的命名"。 - 关于证明是怎么想到的：有学生曾问 Kleene，这个"短得可疑、巧得离谱"的两行证明从何而来，Kleene（也许是开玩笑地）回答说他只是"拿着 S-m-n 性质瞎鼓捣"（"fiddled around with (b)"）。Moschovakis 评论说，这种"鼓捣"很可能受到 [math]\displaystyle{ \lambda }[/math] 演算（Church 与 Kleene 此前共同发展的形式系统）中类似对角线构造的启发〔同上〕。

1. 1. 1. 一个值得铭记的教训

1944 年，Kleene 曾错误地宣称他构造的记号集 O 具有较低的逻辑复杂度（属于 [math]\displaystyle{ \Pi^0_2 }[/math] 类），因为他把第二递归定理给出的某一个不动点，误当作了归纳定义所要求的最小不动点。事实上 O 的复杂度要高得多（[math]\displaystyle{ \Pi^1_1 }[/math]-完备），Kleene 直到 1955 年才纠正。这个故事最生动地说明了：第二递归定理只保证"给你一个不动点"，不保证给你"最小/最特殊的那个"——这正是它区别于第一递归定理的关键（见 4.4 与 6.6）。

---

1. 1. 第一递归定理（FRT）

1. 1. 1. 从"递归定义的函数"说起

编程中最自然的定义方式是递归：定义阶乘时写 `fac(n) = n * fac(n-1)`，等号右边出现了正在定义的函数自己。抽象地看，这类定义都在解一个"函数方程"：

> [math]\displaystyle{ \phi = \Psi(\phi) }[/math]

其中 [math]\displaystyle{ \Psi }[/math] 是一个"函数变换规则"（输入一个函数 [math]\displaystyle{ \phi }[/math]，输出一个新函数 [math]\displaystyle{ \Psi(\phi) }[/math]；术语叫算子，operator）。例如阶乘定义对应的 [math]\displaystyle{ \Psi }[/math] 是：给定任意函数 [math]\displaystyle{ \phi }[/math]，输出新函数 [math]\displaystyle{ \phi }[/math]′，其中 [math]\displaystyle{ \phi }[/math]′(0) = 1，[math]\displaystyle{ \phi }[/math]′(n) = n[math]\displaystyle{ \cdot\phi(n−1) }[/math]。

第一递归定理问的是：什么样的 [math]\displaystyle{ \Psi }[/math] 能保证方程 [math]\displaystyle{ \phi = \Psi(\phi) }[/math] 有解，而且解是可计算的？

1. 1. 1. 定理表述

定义（可计算的变换规则）：如果变换 [math]\displaystyle{ \Psi }[/math] 满足下面两条，就称它是递归算子（recursive operator）：

1. 单调性：[math]\displaystyle{ \phi \subseteq \psi }[/math]（即 [math]\displaystyle{ \psi }[/math] 在 [math]\displaystyle{ \phi }[/math] 有定义的地方都有定义且取值相同）蕴含 [math]\displaystyle{ \Psi(\phi) \subseteq \Psi(\psi) }[/math]； 2. 有限性/连续性：[math]\displaystyle{ \Psi(\phi) }[/math] 的每个输出只依赖 [math]\displaystyle{ \phi }[/math] 在有限个输入上的值。

直觉地说，第二条就是"机器在任何时刻只能查看有限多的已有计算结果"——这是"机械可执行"的数学化。阶乘、斐波那契、以及绝大多数程序语言中的递归定义都满足这两条。

> 第一递归定理：设 [math]\displaystyle{ \Psi }[/math] 是递归算子，则存在函数 [math]\displaystyle{ \phi }[/math] 使得： > > 1. [math]\displaystyle{ \Psi(\phi) = \phi }[/math]（[math]\displaystyle{ \phi }[/math] 是方程的解，即 [math]\displaystyle{ \Psi }[/math] 的不动点）； > 2. 最小性：任何其他解 [math]\displaystyle{ \psi }[/math] 都满足 [math]\displaystyle{ \phi \subseteq \psi }[/math]（[math]\displaystyle{ \phi }[/math] 是"信息最少"的解）； > 3. 可计算性：[math]\displaystyle{ \phi }[/math] 是可计算的部分函数。 > >

证明思路（两分钟版）：从"处处无定义的空函数"出发，反复应用 [math]\displaystyle{ \Psi }[/math]：[math]\displaystyle{ \phi_0 }[/math] = 空，[math]\displaystyle{ \phi_1 = \Psi(\phi_0) }[/math]，[math]\displaystyle{ \phi_2 = \Psi(\phi_1) }[/math]，[math]\displaystyle{ \ldots }[/math][math]\displaystyle{ \ldots }[/math]。单调性保证这个序列不断"变长"（每次迭代只增不减）；有限性保证最终收敛到一个函数 [math]\displaystyle{ \phi }[/math]，且 [math]\displaystyle{ \Psi(\phi) = \phi }[/math]；"每一步都是机械操作"保证 [math]\displaystyle{ \phi }[/math] 整体可计算。取所有 [math]\displaystyle{ \phi }[/math]ₙ 的并就是答案。

例子：方程组 [math]\displaystyle{ \phi(1) = 2 }[/math]，[math]\displaystyle{ \phi(2x) = 2 }[/math][math]\displaystyle{ \phi(x) }[/math] 对应一个递归算子，其最小不动点是：[math]\displaystyle{ \phi(x) = x }[/math]（当 x 是 2 的幂），其余输入无定义。注意"最小性"自动处理了定义不完整的分支——机器在"非 2 的幂"上自然发散。

1. 1. 1. 意义：递归定义的"存在性定理"

第一递归定理的角色，类似于分析学中用不动点定理（如 Banach 压缩映像原理）证明微分方程解的存在性：它一劳永逸地保证"机械式递归定义必有可计算的解"，从此定义递归函数时无需逐个证明合法性。Rogers 指出，"递归定理"这个名字正来源于此——它是"解递归方程"的定理，类比集合论中沿序数递归定义函数的原理。Kleene 本人甚至把第一递归定理视为支持 Church–Turing 论题（"可计算 = 递归/图灵可计算"这一哲学论题）的最强证据之一：它表明"可计算函数"这个类恰好封闭于最一般的机械递归定义方式之下，不多也不少。

数学血统上，它是 Knaster–Tarski 不动点定理（序理论中"完备格上的单调映射必有不动点"）在"可计算"约束下的有效化版本。

1. 1. 1. 与第二递归定理的关系

Rogers 证明了：第二递归定理（强）蕴含第一递归定理（弱）——存在统一的机械方法，把"函数层面的不动点问题"翻译成"代码层面的不动点问题"，并且翻译后得到的不动点恰好是最小的。反过来不成立：第五、六节中第二递归定理的应用几乎都无法由第一递归定理得到。因此两者中第二递归定理更基本、更强大。

Moschovakis 还给出了一个统一形式：把"变换规则"同时允许依赖于"函数的编号"和"函数的值"，所得不动点定理在两种极端情形下分别退化为第二递归定理（不依赖函数值）和第一递归定理（不依赖编号）。

---

1. 1. 第二递归定理（SRT）——本文重点

1. 1. 1. 三种等价表述

表述 A（Kleene 原始形式，1938）：对任意可计算的部分函数 [math]\displaystyle{ \psi(z, x) }[/math]，存在编号 f 使得对所有 x：

> [math]\displaystyle{ \phi_f(x) = \psi(f, x) }[/math]

即：存在一个程序 f，它在输入 x 上的行为，恰好等于"把 f 自己的编号当作第一个参数喂给 [math]\displaystyle{ \psi }[/math]"的行为。 程序 f 在某种意义上"知道自己的代码"。

表述 B（Rogers 不动点形式，1967）：对任意可计算的全函数 f（程序变换规则），存在编号 n 使得：

> [math]\displaystyle{ \phi_n = \phi_{f(n)} }[/math]

这是 Rogers 的原话——"Let f be any recursive function; then there exists an n such that [math]\displaystyle{ \phi_n = \phi_{f(n)} }[/math]."。意思是：f 拿着程序 n 的源代码算出一个新程序 f(n)，而新程序与旧程序计算的是同一个函数。

表述 C（带参数的强化形式）：A、B 只断言不动点"存在"，表述 C 进一步保证：不动点能被程序机械地找出来，并且能随参数连续变化。设想变换规则额外带一个参数 y——用一个三元函数 [math]\displaystyle{ \psi(e, y, x) }[/math] 表示"编号为 e 的程序在参数 y 下的行为"。那么存在一个可计算的全函数 z：你输入 y，它就输出针对这个参数的不动点编号 z(y)，使得 [math]\displaystyle{ \phi_{z(y)}(x) = \psi(z(y), y, x) }[/math] 对所有 x 成立。此外还能要求：①不动点不止一个，而是无穷多个；②不同参数 y 给出不同的编号（z 是单射，即一对一）。

1. 1. 1. 推论：SRT 衍生出的若干重要结果

> SRT 不是孤岛，但也不能把整片大陆都记在它名下。本节收录三条真正以 SRT 为证明枢纽的结果——它们的证明都必经 SRT，称"推论"名副其实： > > - §5.2.1 Smullyan 双递归定理——SRT 的"联立化"推广：一次造出两个互相引用对方代码的程序（可推广到 k 个），是后续许多构造的通用工具； > - §5.2.2 Rogers 同构定理——SRT 的"编号独立性"推论：任意两个通用程序枚举之间必有保结构的可计算同构； > - §5.2.3 Arslanov 完全性判据——相对化 SRT 的"刻画性"等价定理：一个 r.e. 集何时是 r.e.-完备的。 > > 常被误归为 SRT 推论的 Rice 定理与 Rice-Shapiro 定理不在此列：Rice 的教科书证明是停机归约（对角线矛盾），Rice-Shapiro 是"有限可生成"的结构定理，两者都不依赖 SRT（SRT 至多为 Rice 提供一条事后捷径）。它们属于 r.e. 索引集理论，与 SRT 的关系是"同源，但独立"——因此移至 §6.5，与真正依赖 SRT 的 Myhill 定理并置，以对照这两种不同关系。

1. 1. 1. 1. Smullyan 双递归定理（1959, 1961）

SRT 的联立推广：对任意两个全可计算函数 g, h（不一定全），存在两个程序 m, n 使得

> [math]\displaystyle{ \phi_m(x) = g(\langle m, n\rangle, x) }[/math]，[math]\displaystyle{ \phi_n(x) = h(\langle m, n\rangle, x) }[/math]

——两个程序可以互相引用对方的代码。这是 SRT 的"二元推广"，可直接由 SRT 套用：

1. 先用 S-m-n（§2.3）构造两个可计算函数 [math]\displaystyle{ \psi_1(x) = g(S(x, x), x) }[/math]、[math]\displaystyle{ \psi_2(x) = h(S(x, x), x) }[/math]，二者均依赖自身编号； 2. 对 [math]\displaystyle{ \psi_1 }[/math] 套 SRT 拿到不动点 m； 3. m 唯一确定后，n 由 [math]\displaystyle{ \phi_n = \psi_2(m) }[/math] 的不动点结构给出。

推广到 k 元：对任意 k 个全可计算函数 [math]\displaystyle{ g_1 }[/math], [math]\displaystyle{ \ldots }[/math], [math]\displaystyle{ g_k }[/math]，存在 k 个程序 [math]\displaystyle{ m_1 }[/math], [math]\displaystyle{ \ldots }[/math], [math]\displaystyle{ m_k }[/math] 使得 [math]\displaystyle{ \phi_{m_i}(x) = g_i(\langle m_1, \ldots, m_k\rangle, x) }[/math]。

双递归定理是后续许多重要构造的核心：① §6.3 介绍的"两层超算术构造"里，Spector 定理需要同时构造两个互相缠绕的函数；②Myhill-Shepherdson 定理（§6.6 简述）描述"如何用 r.e. 集作为其它 r.e. 集的有效操作"时也需要联立不动点；③某些停机问题的"相对化"证明也走双递归路线。

1. 1. 1. 1. Rogers 同构定理（1958）

任意两个通用程序枚举（即枚举出所有可计算函数的程序编号系统，详见 §2.2；下称 [math]\displaystyle{ \phi }[/math] 系统与 [math]\displaystyle{ \psi }[/math] 系统）之间，必然存在一个可计算同构 [math]\displaystyle{ \rho }[/math]：[math]\displaystyle{ \mathbb{N} \to \mathbb{N} }[/math]——一部双向都可计算的"翻译词典"，把 [math]\displaystyle{ \phi }[/math] 系统里的每个程序号 e 送到 [math]\displaystyle{ \psi }[/math] 系统里的程序号 [math]\displaystyle{ \rho(e) }[/math]，并且 保 [math]\displaystyle{ \phi }[/math] 等价、保 W 等价。这两个"保…等价"头回见到有点吓人，其实只是说：这部词典不改变任何行为事实。逐个拆开看：

- [math]\displaystyle{ \phi }[/math] 等价：同一编号系统内，若两个程序 [math]\displaystyle{ e_1 }[/math]、[math]\displaystyle{ e_2 }[/math] 计算的是同一个（部分）函数（[math]\displaystyle{ \phi_{e_1} = \phi_{e_2} }[/math]，§2.1），就说它们 [math]\displaystyle{ \phi }[/math] 等价——编号只是程序的外衣，算出的函数才是实质。 - 保 [math]\displaystyle{ \phi }[/math] 等价：要求对每个程序号 e 成立 [math]\displaystyle{ \phi_e = \psi_{\rho(e)} }[/math]：e 在 [math]\displaystyle{ \phi }[/math] 系统里算什么函数，[math]\displaystyle{ \rho(e) }[/math] 在 [math]\displaystyle{ \psi }[/math] 系统里就算同一个函数。于是"算同一函数"的程序对，翻译后依然是"算同一函数"的对。 - W 等价 / 保 W 等价：[math]\displaystyle{ W_e }[/math] 是程序 e 的定义域——会让它停机的输入集合（§2.4）。两个程序 W 等价指 [math]\displaystyle{ W_{e_1} = W_{e_2} }[/math]（接受的输入一模一样）；保 W 等价指翻译也不破坏这层对应。由于词条约定 [math]\displaystyle{ W_e = dom(\phi_e) }[/math]，"保 [math]\displaystyle{ \phi }[/math]"已自动带出"保 W"；Rogers 原版把两层并列，是因为他的框架允许"函数枚举"与"r.e. 集枚举"彼此独立（§6.5 索引集的 [math]\displaystyle{ \mathcal{A} }[/math] 用的正是独立于 [math]\displaystyle{ \phi }[/math] 的 W 层）。

直觉上：两个不同的程序编号系统乍看像不同的语言（一个把 quine 编号成 42，另一个编号成 100），但实质上说的是同一类对象；Rogers 定理说它们之间必有可计算的"翻译词典"，且词典严格保结构。

证明思路：把"取 f(c) = 在另一编号系统下对应于 c 的程序编号"作为变换规则，对它套 SRT 得到不动点 c——c 就是翻译词典的种子；之后逐条验证它保 [math]\displaystyle{ \phi }[/math]、W 等价性。Rogers 同构定理常被引用作"程序编号系统的选择不影响可计算性理论"的根据——你可以挑任何合理的编号方式，得出的可计算性结论都一样。

1. 1. 1. 1. Arslanov 完全性判据（1981）

SRT 的相对化版本所给出的等价刻画：r.e. 集合 C 称为 r.e.-完全，当且仅当满足下面这一性质：

> 对每个 r.e. 集合 W，存在一个可计算函数 [math]\displaystyle{ f_W }[/math] 使得 W [math]\displaystyle{ \leq_T C }[/math] via [math]\displaystyle{ f_W }[/math]

这里一下子出现了三个新名字，先逐个解释：

- r.e. 集合：见 §2.4。本词条统一用缩写 r.e.（recursively enumerable，递归可枚举）。 - r.e.-完全：r.e. 集合这个"复杂度类别"里"最硬核"的一档——任何别的 r.e. 集合 W 都能机械地归约到 C，判定"W 含 x"等价于"问 C"。 - Turing 归约 / W [math]\displaystyle{ \leq_T C }[/math] via [math]\displaystyle{ f_W }[/math]：A 能 Turing 归约到 B（记 A [math]\displaystyle{ \leq_T B }[/math]），意思是"只要允许把 B 当神谕机（oracle，下一条解释）——可以向它提任意多个 yes/no 问题并瞬时得到回答——A 就能被判定"。等式 W [math]\displaystyle{ \leq_T C }[/math] via [math]\displaystyle{ f_W }[/math] 即"编排提问方式的过程由可计算函数 [math]\displaystyle{ f_W }[/math] 给出，它把 x 改写成若干个向 C 的查询并综合出答案"。

直觉上：Arslanov 判据说"装得下所有 r.e. 集合"等价于"对每个 r.e. 集合都有机械的相对化方式"——这和 SRT 中"对每个全可计算 f 都给出一个不动点"的相对化版本（relativized SRT）说的是同一件事：SRT 的相对化是说"对每个以 C 为神谕（oracle）可计算的 f，存在不动点 c"；Arslanov 判据说"对每个 W，存在以 C 为神谕可计算的归约"。

Arslanov 判据在递归论里是教科书级工具：①用于证明 Gödel 不完备定理的算术陈述（"PA 不一致"这种陈述）的相对可计算性与停机问题同构；② 用于证明某些 r.e. 集"不可能被简化"。

1. 1. 1. 证明：一行对角线

以表述 A 为例，全部证明如下。函数 [math]\displaystyle{ \psi(S(y, y), x) }[/math] 是可计算的（它只是把 §2.3 的柯里化操作 S 和 [math]\displaystyle{ \psi }[/math] 复合起来），所以它有编号，设为 e。令 f = S(e, e)，则对任何输入 x：

> [math]\displaystyle{ \phi_f(x) = \phi_{S(e,e)}(x) = \phi_e(e, x) = \psi(S(e,e), x) = \psi(f, x) }[/math] ∎

第一步是 f 的定义；第二步是柯里化的定义（S(e,e) 就是"把 e 的第一个输入写死为 e"）；第三步是 e 的定义；第四步再回到 f 的定义。唯一实质操作是第三步前那个自应用 S(e,e)：让程序 e 作用于自己的编号。 这就是对角线方法——与 Cantor 证明实数不可数、Gödel 构造"本句不可证"、Turing 证明停机问题不可解是同一种技术。


图3：第二递归定理证明的三步拆解与对角线自应用的视觉化——核心动作就是让程序 e 在 S(e,e) 里"看见自己"，从而闭合循环。

1. 1. 1. 1. 列表法（Cutland 1980）：把"对角线"画成一张表

上面的一行证明把对角线方法压缩到了极致——好处是直接，坏处是看不出"对角线"长什么样。Cutland 在《Computability》§2.3 (Theorem 2.3) 给出过一种更直观的列表法证明，用一张"行 = 枚举、列 = 位置"的二维表，把"对角线"和"沿对角线的循环"都画在纸面上。三步走。

1. 把"所有可计算函数的枚举"摆成一张表

按 §2.2，每个可计算部分函数都有一个编号；所有这种编号的全体记作 {[math]\displaystyle{ \phi_k }[/math]}。对任意"枚举函数" E（把一列编号映射成一列可计算函数），E 的第 n 项就是 [math]\displaystyle{ \phi_{E(n)} }[/math]，即"编号为 E(n) 的程序"。现在考虑所有"可计算函数的枚举"——它们每一个都是某个可计算函数 h。Cutland 把它们自身也排成一张表：用编号为 k 的程序 [math]\displaystyle{ \phi_k }[/math] 自己去枚举，得到

> [math]\displaystyle{ E_k }[/math] = "以 [math]\displaystyle{ \phi_k }[/math] 为枚举函数的那种枚举"，即 [math]\displaystyle{ E_k }[/math] 的第 n 项 = [math]\displaystyle{ \phi_{\phi_k(n)} }[/math]

——双重编号 [math]\displaystyle{ \phi_{\phi_k(n)} }[/math]。把 [math]\displaystyle{ E_0 }[/math]、[math]\displaystyle{ E_1 }[/math]、[math]\displaystyle{ E_2 }[/math]、[math]\displaystyle{ \ldots }[/math] 并排写下来就是一张二维表（图 6 的上半部）：每行 [math]\displaystyle{ E_k }[/math] 是一个枚举、每列 n 是"该行第 n 个值"、每格是某个具体的可计算函数。这张表把"枚举可计算函数的所有方式"完整地、不重不漏地列了出来。

2. 对角线枚举 D

把这张表沿主对角线的格子圈出来——它们正是

> D = ( [math]\displaystyle{ \phi_\phi_0(0) }[/math], [math]\displaystyle{ \phi_\phi_1(1) }[/math], [math]\displaystyle{ \phi_\phi_2(2) }[/math], [math]\displaystyle{ \ldots }[/math] )

D 仍然是一个可计算的枚举：由 h(x) = [math]\displaystyle{ \phi_x(x) }[/math] 给出（图 6 黄底一行的"沿主对角线"）。它满足一个关键性质：

> D 和每行 [math]\displaystyle{ E_k }[/math] 都共享一项：第 (k+1) 项都是 [math]\displaystyle{ \phi_\phi_k(k) }[/math]

——因为 [math]\displaystyle{ E_k }[/math] 的第 (k+1) 项 = [math]\displaystyle{ \phi_\phi_k(k) }[/math]，而 D 的第 (k+1) 项 = [math]\displaystyle{ \phi_\phi_k(k) }[/math]，两者恰好对得上（图 6 右侧红字注释）。

3. 沿 D 把 f 套进去，得到 f 的不动点

设 f 是任意全可计算函数。沿 D 的每一项先用 f 变一下号，再去取对应的可计算函数，得到另一个枚举：

> D* = ( [math]\displaystyle{ \phi_{f(\phi_0(0))} }[/math], [math]\displaystyle{ \phi_{f(\phi_1(1))} }[/math], [math]\displaystyle{ \phi_{f(\phi_2(2))} }[/math], [math]\displaystyle{ \ldots }[/math] )

D* 也可计算（由 f(h(x)) 给出）——既然 D* 本身也是"枚举可计算函数"的一种方式，它必然是表里某一行 [math]\displaystyle{ E_m }[/math]。这正是循环闭合的地方：套用 f 之后，必然撞回表内。

取 k = m：D* = [math]\displaystyle{ E_m }[/math]，所以 D* 的第 (m+1) 项 = [math]\displaystyle{ E_m }[/math] 的第 (m+1) 项 = [math]\displaystyle{ \phi_\phi_m(m) }[/math]。而 D* 的第 (m+1) 项由定义也是 [math]\displaystyle{ \phi_{f(\phi_m(m))} }[/math]：

> [math]\displaystyle{ \phi_\phi_m(m) = \phi_{f(\phi_m(m))} }[/math]

Cutland 用 Lemma 2.1 把"第 m 行"调整成全的（即 [math]\displaystyle{ \phi_m }[/math] 是全函数），所以 [math]\displaystyle{ \phi_m(m) }[/math] 是一个良定的自然数 n。设 n = [math]\displaystyle{ \phi_m(m) }[/math]：

> [math]\displaystyle{ \phi_n = \phi_{f(n)} }[/math]

n 就是 f 的不动点 ∎。

与"一行证明"的关系：§5.3 的证明把表上 D* = [math]\displaystyle{ E_m }[/math] 的循环直接写成 [math]\displaystyle{ \psi(S(e,e), x) }[/math] 的柯里化形式——h(x) = [math]\displaystyle{ \phi_x(x) }[/math] 对应"e = 编号([math]\displaystyle{ \psi(S(y,y), x) }[/math])"，S(e,e) 就是用自应用把表上的对角线点亮；列表法只是把这一行在表格里完整地展开。两者本质相同：列表法暴露了"为什么沿对角线循环必会撞回表里"——每行 [math]\displaystyle{ E_k }[/math] 都被对角线穿一格，循环天然闭合。


图6：Cutland (1980) 列表法证明的视觉化。上半：四行四列的"枚举之枚举"表 [math]\displaystyle{ E_0 }[/math], [math]\displaystyle{ E_1 }[/math], [math]\displaystyle{ E_2 }[/math], [math]\displaystyle{ E_k }[/math]，每格填 [math]\displaystyle{ \phi_\phi_i(j) }[/math]；主对角线（红圈）上的格子构成对角枚举 D。黄底 D 行：把对角线上的格子抽出，得到 D = ([math]\displaystyle{ \phi_\phi_0(0) }[/math], [math]\displaystyle{ \phi_\phi_1(1) }[/math], [math]\displaystyle{ \phi_\phi_2(2) }[/math], [math]\displaystyle{ \ldots }[/math])。*D 行*：把 f 套到 D 上得到 D = ([math]\displaystyle{ \phi_{f(\phi_0(0))} }[/math], [math]\displaystyle{ \phi_{f(\phi_1(1))} }[/math], [math]\displaystyle{ \ldots }[/math])——可计算 [math]\displaystyle{ \Rightarrow }[/math]必是某行 [math]\displaystyle{ E_m }[/math]。绿框：取 k = m 撞上 [math]\displaystyle{ E_m }[/math]，得 [math]\displaystyle{ \phi_\phi_m(m) = \phi_{f(\phi_m(m))} }[/math]，再设 n = [math]\displaystyle{ \phi_m(m) }[/math] 即得 [math]\displaystyle{ \phi_n = \phi_{f(n)} }[/math]——f 的不动点。

1. 1. 1. 直观图景：程序如何"谈论"自己的代码

例 1（Quine，Python 版）〔示例取自 Wikipedia "Quine (computing)"；与 SRT 的关系见 Kiselyov, §2〕：所谓 quine 就是"打印出自己源代码的程序"。第二递归定理断言：这样的程序必然存在。下面这个 Python 程序就是教科书级的 quine——运行它，会原样打印出它自己的源码：

```python c = 'c = %r; print(c %% c)'; print(c % c) ```

它的机制很简洁：字符串 `c` 本身是一个"打印模板"——`%r` 会带上引号打印出 c 自己的内容，`%%` 是格式化转义符（输出为单个 `%`）。于是 `print(c % c)` 打印出的结果，恰好就是这个程序的全部源码。程序把自己的源码当作数据、再把它打印出来——这正是第二递归定理"程序合法地引用自己的代码"在程序语言里的最小实现。

把 Print 换成任意可计算操作 f：quine 是 SRT 在 f = Print 上的特例。上面那个 quine 里的 `print(c % c)` 可以立刻换成任意可计算操作。看下面这个程序——它不再"打印自己"，而是"先把自己的源码施加一个变换 f、再打印结果"（这里 f = "给每一行加上行号"）：

```python def f(s):

   return '\n'.join(f'{i:2d}: {line}'
                    for i, line in enumerate(s.split('\n'), 1))

c = def f(s):

   return '\\n'.join(f'{i:2d}: {line}'
                    for i, line in enumerate(s.split('\\n'), 1))

src = %r print(f(src % src)) print(f(c % c)) ```

`c % c` 仍然是"自己的源码"，但最后一行不再是 `print(c % c)`，而是 `print(f(src % src))`——也就是先调用 f 处理自己的源码、再打印结果。这个程序满足

> c 的行为 = "对 c 的源码施加 f、再打印"的行为

——用公式写就是 [math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math]（[math]\displaystyle{ \phi_c }[/math] 是程序 c 当作可计算函数看时的整体行为）。把上面那个 f 换成别的——比如"统计字符数"、"对源码求 SHA-256"、"把字符串大写"、"把源码上传到某服务器"、"什么都不做只返回自己"——只要 f 是可计算的全函数，满足 [math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math] 的不动点程序 c 就必然存在。这正是 SRT 所承诺的内容：quine 是 SRT 在 f = "Print" 这一个特例上的推论，SRT 则是 quine 在 f = "任意全可计算函数"上的推广。Kiselyov 在分阶段 [math]\displaystyle{ \lambda }[/math] 演算里把这一观察形式化为"quine = f = id 的不动点、twine（两程序互相打印对方）= f = 另一程序编号映射的不动点、trade 谜题 = f = 投影函数对的不动点"。

SRT 的证明，本身就是一个 Quine 构造——而且方向和 quine 完全相同。再回看 §5.3 那一行证明——给定 f，构造 [math]\displaystyle{ \psi(x) = \phi_{S(x,x)} }[/math]（其中 S 把 f 与"自应用"组合起来），取 e 满足 [math]\displaystyle{ \phi_e = \psi }[/math]，再对 [math]\displaystyle{ \psi }[/math] 套 SRT 取不动点——会发现它和 quine 是同一种构造，差别只在目的（执行层面 vs 输出层面）。两边共用同一种"自指核心动作"——让程序合法地把"自己的表示"当作输入：

| |quine 的自指|SRT 证明的自指| |---|---|---| |自指的载体|字符串 `c`（程序的源码）|编号 e（程序在 [math]\displaystyle{ \phi }[/math] 枚举里的下标）| |载体在哪里被引用|`print(c % c)` 把 c 嵌入 print 的实参|[math]\displaystyle{ \psi(x) = \phi_{S(x,x)} }[/math] 把 e 作为通用函数的下标| |构造方向|先有具体 f（= Print），再造 c（c 的代码里嵌入 f 的引用）|先有具体 f（§5.3 假设中任意一个），再造 c（c 由对 f 套 SRT 得到）| |目的|让 c 的输出 = c 的源码|让 [math]\displaystyle{ \phi_c }[/math] 等价于 [math]\displaystyle{ \phi_{f(c)} }[/math]| |得到什么|一个具体程序（f = Print 时的不动点）|一个具体程序（这个 f 的不动点 c），且这个 c 依赖 f（不同 f 给出不同 c）|

也就是说，SRT 证明与 quine 不是"互逆"，而是同构——两者都是"先有一个具体的全可计算函数 f、再造一个不动点程序 c 满足 [math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math]"。"quine 是 f = Print 时的特例"是对的，但"quine 是先有 f 反求 c、SRT 是先有 c 对任意 f 都成立"是错的——SRT 证明里 c 也是 f 的函数（换一个 f 就换一个 c）。SRT 真正比 quine 强的地方只有一点：它证明了"先有 f、再造 c"这种构造对所有全可计算 f 都成立，而 quine 只演示了 f = Print 一个特例；SRT 给的不是"一个程序"，而是"对每个 f 都有一个程序（f 的不动点 c）"这样的普遍性陈述。这也解释了为何 SRT 在可计算性文献中被称为"second recursion theorem"——它把"quine 这种特例的构造手法"摆到了"自指可计算函数的普遍刻画"这一位置，把 quine 从"程序员的奇技"升格为"任何合理程序系统都封不住自指"的元定理。

例 2（自我命名的集合）：是否存在程序 n，它所列出的集合恰好是单点集 {n}——一个枚举出自己编号的程序？直觉上这像是编号系统的"巧合"，但取变换规则 f 使得"程序 f(x) 恰好输出单点集 {x}"（这样的 f 显然可构造），应用表述 B 即得 [math]\displaystyle{ \phi_n = \phi_{f(n)} }[/math]，即 [math]\displaystyle{ W_n }[/math] = {n}。而且这个结论对任何合理的程序编号系统都成立——它不是编号的巧合，而是编号的必然。

自指的机制（Rogers 的精辟分析）：不动点程序 n 作为一段指令，并不包含它自身的全文（这不可能，句子不能比自身还长），而是包含一份"如何重建自身"的配方——"先算出我的代码，再执行它"。这与 Gödel 在证明不完备定理时发明的"替换函数"（substitution function，把一个公式的编号代入公式自身）是同一种机制。自然语言中的对应物是这个短语：

> "the result of substituting 'the result of substituting "x" in "x"' in 'the result of substituting "x" in "x"'" > （把 "把 x 代入 x 的结果" 代入 "把 x 代入 x 的结果" 所得到的结果）

——按规则展开后，这个短语恰好指称它自己。

1. 1. 1. \lambda 演算视角：与 Y 组合子的关系

[math]\displaystyle{ \lambda }[/math] 演算（Church 1930 年代发明的、Lisp 等函数式语言的祖先）中有一个著名对象 Y 组合子：对任何函数 F，YF = F(YF)，即 Y 直接生产出 F 的不动点，纯函数式地实现递归——它让匿名函数也能"引用自己"。

Kiselyov 在分阶段 [math]\displaystyle{ \lambda }[/math] 演算（staged lambda-calculus，区分"代码"与"值"两个阶段的现代元编程框架）中重构了第二递归定理，得出一个漂亮的结论：第二递归定理就是 Y 组合子的"带代码"推广——Y 组合子给出函数层面的不动点，SRT 给出"程序 + 自身代码"层面的不动点；当把"代码"取为平凡编码（程序即自身）时，SRT 的构造精确退化为 Y 组合子。

这一视角澄清了 SRT 对计算机科学的意义：它陈述的是"任何合理的程序系统对自指构造封闭"，是把高阶操作（程序变换）降阶到数据层面（编号）的不动点原理——部分求值（partial evaluation）、编译器自举（bootstrapping）、宏系统的理论基础。

1. 1. 1. 与其它不动点定理的关系

SRT 衍生出许多重要推论（见 §5.2），但还有些定理与 SRT 的关系更微妙——它们与 SRT 同源（都基于对角线 / 自指），却走的是独立证明路线，或者处于更高层的范畴论概括下。这里集中讨论两个最重要的"不动点定理"：Gödel 的不动点引理与 Lawvere 的范畴论不动点定理，重点说明 SRT 与它们的精确定位关系。

1. 1. 1. 1. Gödel 不动点引理（对角引理）

对任何包含足够算术的递归可公理化理论 T，对 T 中任何公式 [math]\displaystyle{ \phi(x) }[/math]，都存在一个"不动点句子"[math]\displaystyle{ \psi }[/math]，使得 T 证 [math]\displaystyle{ \psi }[/math] ↔ [math]\displaystyle{ \phi }[/math](⌜[math]\displaystyle{ \psi }[/math]⌝)。它的证明手法（对角线替换）与 SRT 同源，但 Gödel 早在 1931 年就独立给出了完整论证，SRT 推不出 Gödel 自身的不完备定理——Gödel 不完备的全部内容（一致性、[math]\displaystyle{ \omega }[/math]-一致性、不可判定性三层）见 §5.7.4 的详述。

注：Gödel 不动点引理本身是 SRT 最干净、最纯粹的推论（既可以把 SRT 当证明工具来证它，也可以两边都用"自指 + 对角线"的同源手法独立证明）。它和 SRT 的关系是"同源、互为推论"；但 Gödel 不完备定理与 SRT 的关系另当别论，见 §5.7.4 的"双重身份"分析。

1. 1. 1. 1. Lawvere 不动点定理（1969）

这一定理是 SRT 所在的整个"对角线 / 自指"现象的范畴论统一视角。它告诉我们：SRT 不是孤立的递归论怪事，而是任何"足够自指的计算系统"都会涌现出的通用结构。下面先用范畴论语言表述，再讲清它和 SRT 的接口。

Lawvere 定理（标准陈述）：设 C 是一个 Cartesian 闭范畴（Cartesian closed category，"对象 = 数据类型、态射 = 数据类型间可计算变换、函数空间本身也是对象、可以反复变换"的信息世界）。设 F: C [math]\displaystyle{ \to C }[/math] 是一个函子（"世界内部的一种自我变换"）。如果存在一个满射态射（surjective morphism，形象地说"覆盖了 F(A) 的全部出口"）

> f: A [math]\displaystyle{ \to F(A) }[/math] （每个 F(A) 元素都被 f 的像源元素覆写）

那么对任意态射 g: F(A) [math]\displaystyle{ \to A }[/math]，都存在一个不动物 x: A [math]\displaystyle{ \to A }[/math]，使得

> F(x) ∘ f = g ∘ f

即顺着"A [math]\displaystyle{ \to F(A) \to A }[/math]"这条回路绕一圈，既可以按 g 走、也可以按 F(x) 走，两条路径等价。

直观解读：所谓"自指世界"，就是那种函数空间可以作为自身参数来研究的地方（Cartesian 闭）。在这种世界里，只要有一个"程序能撞出比自己更复杂的结果"的接口（满射态射），任何"全局选择函数"（g）都必有不动物——你的 g 想要把世界再次变换回自己，总会撞到某个无法再造新东西的点（x），而那个点正好让变换等于"再变换一次"（F(x) = g）。"自我引用 [math]\displaystyle{ \to }[/math]不动点"在这种世界里是不可避免的结构——不论那世界是自然数 + 可计算函数（Turing、Kleene），还是形式系统 + 可证性（Gödel），还是集合论宇宙（Russell、Cantor）。

SRT 是 Lawvere 的特例：把上述抽象框架特殊化到可计算函数的世界，就回到 SRT。具体的接口是：

|Lawvere 抽象成分|SRT 实例化| |---|---| |Cartesian 闭范畴 C|取 Enf——其对象是"一切部分可计算函数 [math]\displaystyle{ \phi }[/math]: [math]\displaystyle{ \mathbb{N}^k }[/math] ⇀ [math]\displaystyle{ \mathbb{N} }[/math] 的等价类"，态射是可计算变换；或者更技术地说，[math]\displaystyle{ P_\omega }[/math] 或 K1 范畴（Gödel 编码的可计算函数论范畴）| |函子 F|适当选取（C 上的函子"程序 [math]\displaystyle{ \to }[/math]它自己的不动点集"），在 SRT 证明里通常把 F 取作"按编号 e 取 [math]\displaystyle{ \phi_e }[/math]" 的函子| |满射态射 f: A [math]\displaystyle{ \to F(A) }[/math]|取定 §2.1 中 [math]\displaystyle{ \phi_e }[/math] 的"自枚举"——把 [math]\displaystyle{ \phi_e }[/math] 编号 e 看作可枚举的元素、保证 F(A) 的每个元素都能表示为"以 f(e) 为参数的程序"，这一步在 SRT 证明中就是 §5.3 一行对角线 e [math]\displaystyle{ \mapsto \Phi_h(f(e), e) }[/math]（也称"自评价插值器"）| |任意态射 g: F(A) [math]\displaystyle{ \to A }[/math]|取 g = SRT 推论里那个给定的全可计算函数 f（"按它编程序"）。注意：SRT 表述要求 f: [math]\displaystyle{ \mathbb{N} \to \mathbb{N} }[/math] 是全可计算的——Lawvere 框架对应"f 处处有定义"这一约束，保证 g 在 F(A) 的全部范围内都有意义。| |不动物 x: A [math]\displaystyle{ \to A }[/math]|正是 SRT 给出的那个不动点编号 c——它满足 F(c) ∘ f = g ∘ f，即 [math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math]|

关系定性：

- Lawvere 不动点定理不是 SRT 的"推论"（该定理没有反推 SRT，而是反过来把 SRT 概括出来）； - Lawvere 也不仅是 SRT 的"更高层次表述"（它是数学基础层面的定理，把 SRT、Gödel 不动点引理、Turing 停机问题的不可判定性、Russell 悖论、Cantor 对角线全部统一为这一个抽象结构的不同时面）； - 因此在写作时应避免两种过度描述：①"Lawvere 推翻了 SRT 的独立性"（错，它们不在一个抽象层）；②"SRT 是 Lawvere 的特例，所以 SRT 的定理就是 Lawvere 给出来的"（错，Lawvere 是更高层的解释，不是 SRT 证明的工具；SRT 证明仍然是 §5.3 的对角线论证）。

对读者的现实意义：如果你做的是程序语义、形式化验证、自指系统、AI 反思架构等领域，理解 Lawvere 框架能让你看清为什么"自指"在这些领域无处不在——而不是递归论特有的怪癖。但若你只想用 SRT 构造自指程序做现实计算，§5.3 的对角线证明就是你所需要的——Lawvere 对那条一行的构造不增加任何可计算内容。

1. 1. 1. 自指现象：SRT 的"自指"一面

第二递归定理最直接、也最让人着迷的威力，是它一劳永逸地解释了"自指"现象为什么合法。但要先澄清一个容易混淆的关键点：这些里程碑可以从两个正交的维度来理解——

- 结论的性质：是"否定性"（证否某物不存在：Cantor、Russell、Turing、Gödel），还是"肯定性"（证实自指对象存在：自复制、quine、SRT 本身）； - 结论活在哪个世界：纯集合论（SRT 够不着），还是程序 / 可计算世界（SRT 够得着）。

两个维度交叉，得到下表：

| |否定性结论（证否某物）|肯定性结论（证实某物存在）| | --------------------- | ----------------------- | --------------------------------- | |纯集合论（SRT 够不着）|Cantor 不可数、Russell 悖论|（无）| |程序 / 可计算（SRT 够得着）|Turing 停机、Gödel 不完备|von Neumann 自复制、quine、自省程序、SRT 本身|

由此看清每个现象的双重身份：Turing 停机、Gödel 不完备在"风格"上是否定性自指（与 Cantor、Russell 同类），但它们活在程序世界，所以又能被 SRT 事后统一推出；Cantor、Russell 活在纯集合论世界，SRT 造不出"实数"或"集合"，只能算同源但独立。下面逐个讲清楚。

1. 1. 1. 1. Cantor 对角线论证（1891）

现象：实数集不可数。假设每个实数都被编号 0, 1, 2, [math]\displaystyle{ \ldots }[/math]；定义一个新实数，令它的第 n 位小数与"编号 n 的实数"的第 n 位小数都不同。这个新实数不在原表里——矛盾。

与 SRT 的关系：同源，但独立。两者做了同一件事——取"第 i 个对象在第 i 个位置上的值"（对角线）：Cantor 取"第 i 个实数的第 i 位小数"，SRT 取"第 e 个程序在输入 e 上的值"[math]\displaystyle{ \phi_e(e) }[/math]（即证明里的 S(e, e)）。但方向相反：Cantor 取对角线后改动它，制造一个"不在表里"的对象，从而证明实数不可数；SRT 取对角线后固定它，得到一个"引用自己编号"的程序，从而证明自指程序存在。注意，SRT 推不出 Cantor 定理——SRT 的结论都活在"程序 / 可计算"的世界里，给不出"实数不可数"这种纯集合论命题；两者只是共享了同一个技巧。

1. 1. 1. 1. Russell 悖论（1901）

现象：考虑 R = {x : x [math]\displaystyle{ \notin x }[/math]}（所有"不属于自己"的集合组成的集合）。问 R [math]\displaystyle{ \in R }[/math] 是否成立？若 R [math]\displaystyle{ \in R }[/math]，则按定义 R [math]\displaystyle{ \notin R }[/math]；若 R [math]\displaystyle{ \notin R }[/math]，则按定义 R [math]\displaystyle{ \in R }[/math]。两边都矛盾，这个悖论动摇了朴素集合论。

与 SRT 的关系：同源，但独立。Russell 悖论也是"把谓词'不属于自身'同时用于所有集合"的对角线操作，和 SRT 共享同一个技巧，但 SRT 同样推不出它——它是朴素集合论内部的问题，不涉及程序。真正值得注意的，是 Rogers 指出的一个类比：把"集合"换成"可枚举的集合 [math]\displaystyle{ W_e }[/math]"、把"[math]\displaystyle{ \in }[/math]"换成"e [math]\displaystyle{ \in W_e }[/math]"，就得到 K = {e : e [math]\displaystyle{ \notin W_e }[/math]}——K 可枚举、其补集不可枚举。而"K 的补集不可枚举"恰好等价于停机问题不可判定（见 5.7.3），后者才是 SRT 真正推得出来的。换言之，"停机问题不可判定"可以看作"递归论版的 Russell 悖论"，但 Russell 悖论本身与 SRT 只是同源关系。

1. 1. 1. 1. Turing 停机问题（1936）

现象：不存在算法 H 能判定"任意程序 e 在任意输入 x 上是否会停机"。这是可计算性理论第一个、也是最著名的"不可判定"结果。

双重身份：停机不可判定在结论性质上是否定性的（证明"判定器不存在"），与 Cantor、Russell 同类；但因为它活在"程序"世界，又能被 SRT 推出。下面展示完整的"套用"过程——这是所有例子里最干净的一个，最能看清 SRT 到底在哪里发力。

套用 SRT 造否定性自指程序的完整演示：

1. 假设存在判定器 H（H(e,x)=1 表示"程序 e 在输入 x 停机"，=0 表示不停机）。 2. 写出"想要的行为"，把"自己"写成参数 z：我们要一个与 H 唱反调的捣乱程序——"如果 H 说程序 z（在输入 z 上）会停机，我就死循环；如果 H 说不停机，我就立即停机"。写成可计算规则：

  > [math]\displaystyle{ \psi(z, x) }[/math] = 若 H(z, z) = 1，则发散（死循环）；若 H(z, z) = 0，则输出 0（立即停机）。

3. 套 SRT：存在编号 f，使 [math]\displaystyle{ \phi_f(x) = \psi(f, x) }[/math]。SRT 在这一步把参数 z 换成了 f 自己，循环闭合：

  > [math]\displaystyle{ \phi_f(x) }[/math] = 若 H(f, f) = 1，则发散；若 H(f, f) = 0，则输出 0。

4. 代入 x = f 制造矛盾：若 H(f,f)=1（H 说"f 在输入 f 停机"），但此时 [math]\displaystyle{ \phi_f(f) }[/math] 发散——H 判错；若 H(f,f)=0（H 说不停机），但此时 [math]\displaystyle{ \phi_f(f)=0 }[/math] 停机——H 又判错。于是 H 无论如何都错 [math]\displaystyle{ \to }[/math]H 不存在。∎

关键就在第 3 步：[math]\displaystyle{ \psi }[/math] 里用的是参数 z（可以正常定义），SRT 把它换成 f 自己——没有 SRT，"[math]\displaystyle{ \phi_f }[/math] 的行为取决于 H 对 f 的判决"就是非法循环定义，写不出来。SRT 的全部威力，就是把这种循环合法化：你只管把"自己"写成参数，存在性交给定理。

1. 1. 1. 1. Gödel 第一不完备定理（1931）

现象：任何"足够强"的一致可公理化理论 T（例如 Peano 算术 PA）都不完备：存在一个句子 [math]\displaystyle{ \sigma }[/math]，使 T 既证不出 [math]\displaystyle{ \sigma }[/math]、也证不出 [math]\displaystyle{ \neg }[/math][math]\displaystyle{ \sigma }[/math]。

术语——PA 与 Q：PA 是 Peano 算术（Peano Arithmetic）的缩写，是一阶算术的标准公理系统，用于形式化刻画自然数（0, 1, 2, [math]\displaystyle{ \ldots }[/math]）及其加法、乘法。它由意大利数学家 G. Peano（1889）的公理发展而来，包含：①常元 0；②后继运算 S（每个数有唯一后继，0 不是任何数的后继，后继相同则原数相同）；③加法、乘法的递归定义；④归纳公理模式（induction schema：对任何一阶公式 [math]\displaystyle{ \phi }[/math]，若 [math]\displaystyle{ \phi(0) }[/math] 成立、且 [math]\displaystyle{ \phi(n) \Rightarrow \phi(n+1) }[/math]，则 [math]\displaystyle{ \phi }[/math] 对一切自然数成立）。PA 是 Gödel 不完备定理的典型对象——它足够强（能在内部编码所有初等数论），又是可公理化的一致理论。而 Q（Robinson 算术）是 PA 的一个弱化：保留①—③、去掉归纳公理模式，只留极有限的几条公理，是"足以推出不完备定理的最弱理论"之一（后文 Myhill 定理即用它）。

双重身份：与停机问题一样，Gödel 不完备在结论上是否定性的（证明"完备一致的理论不存在"）；Gödel 1931 的原证走的是 Cantor/Russell 的否定性对角线老路、并不依赖 SRT。但因为它活在"形式系统可证性"这一可计算世界，事后也能被 SRT 干净地推出。核心是不动点引理（Fixed Point Lemma），它是 SRT 最纯粹形式的直接推论：

> 不动点引理：设 T 是任何足够强的可公理化理论，则对任何含一个自由变量的公式 [math]\displaystyle{ \theta(v) }[/math]，都存在句子 [math]\displaystyle{ \sigma }[/math]，使 T 可证 "[math]\displaystyle{ \sigma }[/math] ↔ [math]\displaystyle{ \theta }[/math](⌜[math]\displaystyle{ \sigma }[/math]⌝)"（⌜[math]\displaystyle{ \sigma }[/math]⌝ 是 [math]\displaystyle{ \sigma }[/math] 的哥德尔数）。即：任何性质 [math]\displaystyle{ \theta }[/math]，都存在一个句子 [math]\displaystyle{ \sigma }[/math]，在 T 可证的意义下恰好谈论"自己是否具有 [math]\displaystyle{ \theta }[/math]"。

证明：取 [math]\displaystyle{ \theta(v) }[/math] = "v 不可证"，由不动点引理得 [math]\displaystyle{ \sigma }[/math] ↔ "[math]\displaystyle{ \sigma }[/math] 不可证"。若 [math]\displaystyle{ \sigma }[/math] 可证，则它说的是真话（我不可证），矛盾；若 [math]\displaystyle{ \neg }[/math][math]\displaystyle{ \sigma }[/math] 可证，则"[math]\displaystyle{ \sigma }[/math] 可证"，又矛盾。于是 [math]\displaystyle{ \sigma }[/math] 与 [math]\displaystyle{ \neg }[/math][math]\displaystyle{ \sigma }[/math] 都不可证——第一不完备定理成立。把 [math]\displaystyle{ \theta }[/math] 换成 Rosser 的精巧变体，还能去掉"[math]\displaystyle{ \omega }[/math]-一致性"这个额外假设，得到 Rosser 强化。

> Myhill 定理（1955）：Robinson 算术 Q 的任何一致、可公理化扩张 T，其定理集都是创造集（见 §6.5.3），从而是 r.e.-完备的。

合起来得到一个惊人结论：所有足够强的一致公理化理论（PA、ZFC[math]\displaystyle{ \ldots }[/math][math]\displaystyle{ \ldots }[/math]）都自动满足不动点引理的条件，因而都不完备、不可判定；而且任意两个这样的理论，其定理集在递归同构意义下完全相同。

Rogers 还讨论过一个反向的自指：可以构造一个公理系统，其中包含断言自身一致性的句子（对任何公理集 [math]\displaystyle{ W_p }[/math]，存在 n 使 [math]\displaystyle{ W_n = W_p }[/math] [math]\displaystyle{ \cup }[/math]{⌜[math]\displaystyle{ W_n }[/math] 一致⌝}）。但 Gödel 第二不完备定理说明：若 [math]\displaystyle{ W_p }[/math] 已含 PA，这个"自信"的系统反而不可能一致。

1. 1. 1. 1. von Neumann 自复制自动机（1948）

现象：存在能在物理上自我复制的自动机。von Neumann 在 Los Alamos 设计的方案含四部分：通用构造器 A（读入一段指令，构造出该指令描述的任何机器）、通用拷贝器 B（复制指令）、控制器 C（指挥 A 与 B 协同运作、并把指令传给新机器）、以及一段描述 A、B、C 三者如何组合的蓝图（即指令带）；机器 M = [math]\displaystyle{ \langle }[/math] A, B, C, 蓝图[math]\displaystyle{ \rangle }[/math] 启动后能造出 M 自己的副本。

SRT 如何推出它：

> 定理（自复制图灵机）：存在一台图灵机，从空白纸带出发，停机时纸带上恰好写着它自己的完整描述（转移表）。

证明是 SRT 的典型用法：定义 [math]\displaystyle{ \psi(z) }[/math] = "把编号 z 的机器的描述打印出来"——一个完全机械、与"谁被打印"无关的变换。SRT 给出不动点 f：程序 f 的行为 = 打印 f 自己的描述。循环凭空闭合。

Rogers 给出更一般的框架：只要存在一台"通用建造机"（即 von Neumann 的 A 的抽象——给蓝图就造机器），就必存在一台机器，无论输入什么都造出自己的副本。这直接驳倒了"自复制不可能"的谬误论证（"复制需要蓝图，蓝图又需要蓝图的蓝图，无穷倒退"）：SRT 表明系统能用有限指令闭合这个回环。


图4：自复制机的闭合回路——机器 M 的蓝图描述了 M 的全部部件（构造器 A、拷贝器 B、控制器 C）；启动后 A 读蓝图 [math]\displaystyle{ \to }[/math]造出 M 的新副本、B 复制蓝图、C 把它们组装起来。SRT 保证存在这样的蓝图，让有限指令即可闭合循环（驳斥了"蓝图之蓝图无穷倒退"的谬误）。

1. 1. 1. 1. Quine（自打印程序）

现象：一个不接受任何输入、只打印出自己源代码副本的程序。。它的约束很苛刻——不能读自己的源码（靠读文件输出自己、如 `cat $0`，被视为"作弊"，不算 quine），只能靠"代码部分 + 代表代码文本的数据部分"来构造性地打印自己；§5.4 例 1 的 Python 程序就是一个标准 quine。"quine" 一词由 Hofstadter 在《哥德尔、艾舍尔、巴赫》中普及（借自哲学家 W. V. O. Quine 的名字，他构造过自指的句子）。

SRT 如何推出它：把 SRT 里的变换规则 f 直接定义为"打印"程序——f(c) = "打印出 c 的源码的那个程序"。套用 SRT（[math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math]）得到不动点 c：

> [math]\displaystyle{ \phi_c = \phi_{f(c)} = \phi_{"打印 c"} }[/math]

也就是说，程序 c 的行为 = 打印出 c 自己——这正是 quine。所以 quine 就是"取 f = Print 程序、再套 SRT"的一行产物。Kiselyov 在分阶段 [math]\displaystyle{ \lambda }[/math] 演算里形式化地证明，quine、twine（两个程序互相打印对方）、trade 谜题都是 SRT 的不动点。

1. 1. 1. 1. 自省程序与自省式自改进程序

自省程序（introspective program）：比 quine 强得多的自指——它能在运行时"看到"自身（或自身的有界近似），并据此修改、调整自己的行为。Lisp 的 `eval`、Python 的 `inspect`/反射、调试器、动态语言的元对象协议都是它的化身。

这一思想最早是 Cutland 在 Computability: An Introduction to Recursive Function Theory（1980）§1.9 中以 [math]\displaystyle{ \psi }[/math]-introspective / totally [math]\displaystyle{ \psi }[/math]-introspective 之名给出严格定义并证明存在性（定理 1.9）。他关于 [math]\displaystyle{ \psi }[/math]-分析与 totally [math]\displaystyle{ \psi }[/math]-introspective 的原话是：

> 假设给定一个全可计算函数 [math]\displaystyle{ \psi }[/math] 和一个程序 P。所谓 P(x) 计算的 [math]\displaystyle{ \psi }[/math]-分析（[math]\displaystyle{ \psi }[/math]-analysis），是指 P(x) 计算到 [math]\displaystyle{ \psi(x) }[/math] 步的那段计算的代码。称程序 P 在 x 上是 [math]\displaystyle{ \psi }[/math]-自省的（[math]\displaystyle{ \psi }[/math]-introspective at x），若 P(x) 收敛并把它自己的 [math]\displaystyle{ \psi }[/math]-分析作为输出；若 P 在所有 x 上都是 [math]\displaystyle{ \psi }[/math]-自省的，则称为 完全 [math]\displaystyle{ \psi }[/math]-自省的（totally [math]\displaystyle{ \psi }[/math]-introspective）。 > > 定理 1.9：存在一个程序 P 是完全 [math]\displaystyle{ \psi }[/math]-自省的。 > > 证明：直接对可计算函数 f(e, x) = [math]\displaystyle{ \sigma }[/math]*(e, x, [math]\displaystyle{ \psi(x) }[/math]) 应用推论 1.4（SRT 在 Cutland 体系里的等价形式，[math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math] 的不点形式），得到一个不动点 n 使得 > > [math]\displaystyle{ \phi_n(x) = f(n, x) = P_n(x) }[/math] 的 [math]\displaystyle{ \psi }[/math]-分析。□

其中 [math]\displaystyle{ \sigma }[/math](e, x, y) 是 Cutland 引入的 有界通用函数——输出"程序 e 在输入 x 上运行至多 y 步后停下"的那段计算的代码（y 步内不停则发散）。所以 f(n, x) = [math]\displaystyle{ \sigma }[/math](n, x, [math]\displaystyle{ \psi(x) }[/math]) 直译过来就是"把 [math]\displaystyle{ P_n(x) }[/math] 跑 [math]\displaystyle{ \psi(x) }[/math] 步后的整段计算的代码吐出来"。这里的 [math]\displaystyle{ \psi }[/math] 是任意的全可计算步数函数——既可取常数（"只看自身一固定切片"）也可随 x 变化。完全 [math]\displaystyle{ \psi }[/math]-自省 在 [math]\displaystyle{ \psi }[/math] 取常数情形即"输出自身代码的一个有界近似"，恰是现代"自省（introspection）"这一概念的形式化原型。

SRT 的现代等价说法：与 quine 同构，只把 f 换成有界自模拟器 [math]\displaystyle{ f_T }[/math]——[math]\displaystyle{ f_T(c) }[/math] = "模拟程序 c 运行 T 步的那个程序"（T 是固定步数上界，因此 [math]\displaystyle{ f_T }[/math] 是可计算的全函数）。套 SRT（[math]\displaystyle{ \phi_c = \phi_{f(c)} }[/math]）得到不动点 c：

> [math]\displaystyle{ \phi_c = \phi_{f_T(c)} = \phi_{"模拟 c 运行 T 步"} }[/math]

即程序 c 的行为 = 在 T 步内模拟自己——它"看到"了自己的有界近似。自省程序的存在性因此是 SRT 的直接推论；这一节的脉络是：Cutland 1980 的定理 1.9 是原始定义/证明，[math]\displaystyle{ f_T }[/math] 这套叙事是更易上手的现代等价说法，而 Zhang、Yuan & Zhang (2026) 把它延伸到"自省式自改进程序"。

自省式自改进程序（introspective self-improving program）：在自省基础上再进一步——程序不仅模拟自己，还基于自模拟结果来修改、改进自己。Zhang、Yuan & Zhang (2026) 用这一构造论证：存在能自我模拟、自我改进的程序，并把 von Neumann 的"复杂度阈值"重新诠释为大型语言模型递归自我改进所需的自省阈值（introspection threshold）——系统必须在自身描述中编码足够多的关于自身的信息，才能维持非退化的递归自我改进，否则会陷入熵退化或模型坍缩。

---

统一性总结：上述现象共享同一个"对角线 / 自指"技巧，从结论性质（否定/肯定）和所在世界（集合论/可计算）两个维度看，完整谱系是：

``` 对角线 / 自指（一个共同技巧，不是某个定理） ├─ 否定性用法（证否"某物存在"） │ ├─ 纯集合论：Cantor(不可数)、Russell(悖论) \leftarrow SRT 够不着，同源但独立 │ └─ 可计算世界：Turing(停机)、Gödel(不完备) \leftarrow SRT 能事后统一推出 └─ 肯定性用法（证实"自指存在"）

    └─ SRT 本身 + von Neumann 自复制 + quine + 自省程序      \leftarrow SRT 直接给出

```

其中 Turing 停机、Gödel 不完备拥有双重身份：结论是否定性的（与 Cantor、Russell 同类），历史原证也走否定性对角线老路、不依赖 SRT；但因活在程序世界，又能被 SRT 事后更简洁地推出（§5.7.3 展示了停机问题的完整套用过程）。它们共同构成 SRT 的"自指"一面；SRT 还有另一面——"沿序数逐层构造"——见第六节。

---

1. 1. 其它应用：非自指构造

上一节（§5.7）的那些现象都是"自指"本身的例子——程序或句子直接谈论自己。但 SRT 的威力远不止此：它同样是构造不涉及自指的复杂数学对象的基本工具。Moschovakis (2010) 以"回顾展"方式列举了 18 个 SRT 发挥关键作用的结果，其中最重要的一类是 Kleene 本人最钟爱的沿序数逐层构造（有效超限递归）——把递归定义从自然数推广到序数，从而定义出越来越复杂的对象。本节即以它开篇（6.1–6.4）；此后转入其余主题（6.5–6.7）——注意 6.5 板块中的 Rice 家族与 SRT 是“同源，但独立”的关系（并非 SRT 应用），详见该节导言。逻辑学家 Leo Harrington 对 SRT 威力的概括最为传神：

> "You need a number z? You got it!"（你需要一个这样的数 z？给你！）

1. 1. 1. 沿序数逐层构造之一：通用序数记号系统与 \omega_1^CK

这是 SRT 最初的应用（见 3.1）。回顾§3.1 的背景：序数记号系统给可数序数指派自然数代号，使得 0 / 后继 / 极限三分可机械判定、前驱与基本序列可机械取出。在进入定理之前，先把本节反复用到的几个概念交代清楚（"序数"本身的背景见 §3.1 的背景框）：

- 代号与所指：记号系统里的每个自然数 a 都是一个代号，它所指的序数记作 |a|。一个序数 [math]\displaystyle{ \alpha }[/math] 的后继（successor）就是 [math]\displaystyle{ \alpha+1 }[/math]（0 的后继是 1，[math]\displaystyle{ \omega }[/math] 的后继是 [math]\displaystyle{ \omega+1 }[/math]）。极限序数（limit ordinal，下文统记作 [math]\displaystyle{ \lambda }[/math]）则是既非 0 也非任何序数之后继的序数——它不能靠"+1"走到，只能被一列递增的序数"逼近"，最典型的例子是 [math]\displaystyle{ \omega }[/math]（0, 1, 2, 3, [math]\displaystyle{ \ldots }[/math] 无限数完之后的那一步：任何自然数都不是它的"前一个"）。 - 前驱与基本序列：后继代号 x 的前驱（predecessor）记 P(x)——所指序数被"+1"之前那个序数的代号。极限代号 x 的基本序列（fundamental sequence）是一条可机械取出的递增代号列 [math]\displaystyle{ x_0 }[/math], [math]\displaystyle{ x_1 }[/math], [math]\displaystyle{ x_2 }[/math], [math]\displaystyle{ \ldots }[/math]，所指序数 |[math]\displaystyle{ x_0 }[/math]| < |[math]\displaystyle{ x_1 }[/math]| < [math]\displaystyle{ \ldots }[/math] 逐渐逼近 |x|。 - [math]\displaystyle{ S_1 }[/math] 的语法（[math]\displaystyle{ S_1 }[/math] 是下文定理要构造的那个"通用"序数记号系统，Kleene 1938 为它设计的编码方案；后文的记号系统 O 沿用同一语法）：0 的代号固定为 1；代号 a 的后继的代号写成 2^a；极限序数的代号写成 3[math]\displaystyle{ \cdot5^e }[/math]，并约定 |3[math]\displaystyle{ \cdot5^e }[/math]| = lim |[math]\displaystyle{ \phi }[/math]ₑ(n)|（程序 e 逐个吐出逼近该极限的记号列，[math]\displaystyle{ \phi }[/math]ₑ 是编号为 e 的程序，见 §2.2）。取这三种质因数形态（1、2 的幂、3[math]\displaystyle{ \times5 }[/math] 的幂）纯属编码技巧：对代号做质因数分解，就能机械判定它是 0 的代号、后继代号还是极限代号。

> 定理（Kleene 1938）：存在一个通用序数记号系统 [math]\displaystyle{ S_1 }[/math]：对任何其他合法的序数记号系统 S（"合法"即满足 §3.1 说的条件——0 / 后继 / 极限三分可机械判定、前驱与基本序列可机械取出），存在可计算函数把 S 的代号保序地翻译为 [math]\displaystyle{ S_1 }[/math] 的代号（"保序"：若 |x| < |y|，则翻译后所指的序数仍保持这一大小关系——翻译不打乱任何两个序数的先后）。

证明的思路（这是"有效超限递归"的范式，值得细看）：想要的翻译函数 [math]\displaystyle{ \psi }[/math] 应该满足

> [math]\displaystyle{ \psi(x) = 1 }[/math]　　　　　　（x 是 0 的代号时） > [math]\displaystyle{ \psi(x) = 2^\psi(P(x)) }[/math]　　（x 是后继序数的代号时，P(x) 是前驱代号） > [math]\displaystyle{ \psi(x) = 3\cdot5^e }[/math]　　　　 （x 是极限序数的代号时，e 是"逐点翻译基本序列"那个程序的编号）

第三行的 e 值得拆开细看——[math]\displaystyle{ \psi }[/math] 的定义需要用到 [math]\displaystyle{ \psi }[/math]，循环正藏在 e 的代码里。设 [math]\displaystyle{ \lambda }[/math] 是 S 能命名的某个极限序数（就是上文说的那种"既非 0 也非后继、只能被逼近"的序数，例如 [math]\displaystyle{ \omega }[/math]），x 是它在 S 中的代号；S 是合法记号系统，故 x 自带一条可计算的基本序列 [math]\displaystyle{ x_0 }[/math], [math]\displaystyle{ x_1 }[/math], [math]\displaystyle{ x_2 }[/math], [math]\displaystyle{ \ldots }[/math]——一列递增的代号，所指序数逐渐逼近 [math]\displaystyle{ \lambda }[/math]。按上面交代的语法，极限序数的代号必须写成 3[math]\displaystyle{ \cdot5^e }[/math] 的形态，所以 [math]\displaystyle{ \psi(x) }[/math] 必须形如 3[math]\displaystyle{ \cdot5^e }[/math]，其中 e 是这样一个程序的编号：

> 输入 n [math]\displaystyle{ \to }[/math]从 x 取出 xₙ [math]\displaystyle{ \to }[/math]对 xₙ 运行 [math]\displaystyle{ \psi }[/math] [math]\displaystyle{ \to }[/math]输出 [math]\displaystyle{ \psi(xₙ) }[/math]

（"逐点翻译基本序列"说的就是它。）这里有两个层面的循环，性质完全不同：

- 值的层面（无害）：[math]\displaystyle{ \psi(x) = 3\cdot5^e }[/math] 是一个完整的数，e 只是其中 5 的指数；程序 e 的输出是 [math]\displaystyle{ \psi(x_0) }[/math], [math]\displaystyle{ \psi(x_1) }[/math], [math]\displaystyle{ \ldots }[/math]——x 下面各项的翻译——它从不计算 [math]\displaystyle{ \psi(x) }[/math] 自己（极限值由记号的形态约定，不是程序算出来的）。所以不存在"[math]\displaystyle{ \psi(x) }[/math] 的值里嵌着 [math]\displaystyle{ \psi(x) }[/math] 的值"这种直接自指。 - 代码的层面（真正的循环）：程序 e 要对 xₙ 运行 [math]\displaystyle{ \psi }[/math]，就必须在自己的代码里写死 [math]\displaystyle{ \psi }[/math] 的程序编号——而 [math]\displaystyle{ \psi }[/math] 此刻还在定义中。也就是说，想定义 [math]\displaystyle{ \psi }[/math]，得先造出一个"代码里引用了 [math]\displaystyle{ \psi }[/math] 的编号"的程序。这正是"右边出现了正在定义的 [math]\displaystyle{ \psi }[/math] 自己（及其编号）"的所指；这类循环在普通数学里非法。

SRT 恰好合法化它：先用 S-m-n 定理（§2.3）造一个可计算函数 q(x, d)——给定 [math]\displaystyle{ \psi }[/math] 的编号 d，机械地吐出"读 n、取 xₙ、运行程序 d"那个程序的编号。于是想求的 [math]\displaystyle{ \psi }[/math] 满足：[math]\displaystyle{ \psi(x) = 3\cdot5^e }[/math]，其中 e = q(x, d)，而 d 正是 [math]\displaystyle{ \psi }[/math] 自己的编号。把右边整体看作 d 的函数、套 SRT 取不动点 c，令 [math]\displaystyle{ \psi = \phi_c }[/math]，循环即闭合；再沿序数归纳验证 [math]\displaystyle{ \psi }[/math] 确实是全函数（"全"：对每个输入代号都有输出，见 §2.1）且保序。

顺带分辨两行的差异：第二行 [math]\displaystyle{ \psi(x) = 2^\psi(P(x)) }[/math] 是值依赖值的循环，且 P(x) 指向更小的序数，本质上是良基的（"良基"：不存在无穷下降链，所以"沿序数从小到大做归纳"是合法的）；第三行则是编号依赖编号的循环（e 的代码里嵌着 [math]\displaystyle{ \psi }[/math] 的编号），良基性救不了它——必须 SRT。

在 [math]\displaystyle{ S_1 }[/math] 的基础上，Kleene 进一步构造了带树状偏序的序数记号系统 O（Kleene's O）——"偏序"（partial order）指只在部分代号对之间定义的"小于"关系（O 中记作 <O，反映所指序数的大小）。O 是通用且极大的：每个可被任何合法记号系统命名的序数（称为构造序数，constructive ordinal）在 O 中都有代号。全体构造序数的上确界（supremum：不小于它们中任何一个的最小序数）

> [math]\displaystyle{ \omega_1^CK }[/math] = 最小的非构造序数（Church–Kleene 序数）

是逻辑学中最基本的"普适常数"之一：它是"机械命名能力"在序数世界中的绝对边界。Rogers 用同样的 SRT 技术证明：O 上的"序数加法"可由一个可计算函数实现。

问题来了：同一序数 [math]\displaystyle{ \alpha }[/math] 在系统中有无穷多个代号，用不同代号构造出的 [math]\displaystyle{ H_\alpha }[/math] 会不会不同？

图5：Kleene 记号系统 O 的树状结构示意。每个自然数都是某个序数的代号——规则：|1| = 0（最底层）；|2^x| = |x| + 1（后继，沿着"2 的幂"链向上）；|3[math]\displaystyle{ \cdot5^e }[/math]| = li[math]\displaystyle{ m_n }[/math] |[math]\displaystyle{ \phi_e(n) }[/math]|（极限——记号里携带基本序列程序的编号 e，这正是 SRT 大显身手的地方）。所有构造序数都在这棵树上生长；树顶是 [math]\displaystyle{ \omega_1^CK }[/math]（无法被任何机械记号触及的边界）。

Kiselyov 以现代眼光补充了这段历史的思想动机：Kleene 放弃用 [math]\displaystyle{ \lambda }[/math] 项（他与 Church 两年前的方案）做序数代号，正是因为 [math]\displaystyle{ \lambda }[/math] 项作为函数无法被机械地比较大小；极限序数的代号必须携带程序的编号而非函数本身——"只有编号（有穷对象）才能被直接给出，这是有穷主义立场的要求"。

1. 1. 1. 沿序数逐层构造之二：构造序数 = 递归序数

可数序数有两种自然刻画："构造序数"（能被某个机械记号系统命名，见 6.1）与"递归序数"（某个可计算良序的长度——即存在一个可计算的大小关系，把一堆自然数排成该长度的"无限队列"）。

> Markwald–Spector 定理（1954/1955）：两种刻画恰好等价——构造序数 ⟺ 递归序数。

这是经典集合论事实"第二数类的两种刻画等价"的可计算版本；两个方向的证明都以 SRT 为归纳枢纽。

1. 1. 1. 沿序数逐层构造之三：超算术层级与 Spector 唯一性定理

背景：这一段需要先铺垫三个概念。

神谕（oracle）：给程序外接一块只读"数据库"——集合 A。程序运行中可随时查询"数 n 是否属于 A"并立即得到正确答案。这样的 A 称为神谕；"以 A 为神谕可计算"衡量的是：若把 A 白送给你，你还能多算出什么。

Turing 跳跃（Turing jump）：对任何集合 A，把"哪些以 A 为神谕的程序会停机"这一问题本身收集成一个集合，记作 A′（读作"A 撇"）。可以证明：A′ 以 A 为神谕仍不可计算——每跳一次，都得到一个严格更难的"相对版停机问题"。特别地，从空集 [math]\displaystyle{ \emptyset }[/math] 出发跳一次得到的 0′，正是通常意义下的停机问题（5.7.3）。

沿构造序数"盖楼"：现在从 [math]\displaystyle{ H_0 = \emptyset }[/math] 出发，沿构造序数（见 6.1）逐层往上盖：

> [math]\displaystyle{ H_{\alpha+1} }[/math] = ([math]\displaystyle{ H_\alpha }[/math])′　（后继层：再跳一次，复杂度升一级） > [math]\displaystyle{ H_\lambda = \cup }[/math]ₙ [math]\displaystyle{ H_{\lambdaₙ} }[/math]　（极限层：把下面各层沿一条可计算上升的序列 [math]\displaystyle{ \lambda_0 \lt \lambda_1 \lt \lambda_2 \lt \ldots }[/math] 并起来——沿哪条序列取并由 [math]\displaystyle{ \lambda }[/math] 的代号给出，6.1 里"记号携带程序编号"的约定在此派上用场）

在某一层 [math]\displaystyle{ H_\alpha }[/math] 中可计算的集合，称为超算术的（hyperarithmetical, HYP）。这栋楼的前几层串起熟悉的图景：只盖有穷多层，得到的恰好是通常的算术层级——穷尽一阶算术（量词只作用于自然数）可定义的全部集合；盖到第 [math]\displaystyle{ \omega }[/math] 层（[math]\displaystyle{ \omega }[/math] 即 6.1 中最小的无穷序数），得到的集合已足以一举判定 PA （皮亚诺公理体系）的全部真语句——包括所有 PA 证明不了的真命题（对照 5.7.4 的不完备性）；而楼并不停在这里，它沿构造序数一直盖到 [math]\displaystyle{ \omega_1^CK }[/math] 为止。HYP 因此是真正高于算术层级的层级——至于它究竟高到哪一步（恰好等价于一个"二阶量词"的定义能力），正是 6.4 的主题。

问题来了：同一序数 [math]\displaystyle{ \alpha }[/math] 在系统中有无穷多个代号，用不同代号构造出的 [math]\displaystyle{ H_\alpha }[/math] 会不会不同？

> Spector 唯一性定理（1955）：不会。[math]\displaystyle{ H_\alpha }[/math] 的可计算度只依赖序数 [math]\displaystyle{ \alpha }[/math] 本身，与代号选择无关；而且不同代号之间的翻译是一致可计算的。

证明需要同时构造两个互相缠绕的函数（互相引用对方编号），由双递归定理（见 §5.2 的 Smullyan 版本）合法化——这是有效超限递归技术的高峰之一。Kleene 对这个学生的工作推崇备至，他常讲自己如何"行为不端"地接受它作为博士论文、又作为期刊编辑指定自己为审稿人并立即录用——"非常不合规矩，但我认为最终有利于逻辑！"

1. 1. 1. 沿序数逐层构造之四：HYP = \Delta^1_1 与有效描述集合论

背景：在自然数的集合（数学分析的对象）上，可以用"二阶量化"分层：[math]\displaystyle{ \Sigma^1_1 }[/math] 集是"存在一个实数使得某个可计算性质成立"的集合（存在投影），[math]\displaystyle{ \Pi^1_1 }[/math] 是其对偶（全称），[math]\displaystyle{ \Delta^1_1 = \Sigma^1_1 \cap \Pi^1_1 }[/math] 是"两面都可定义"的集合——可类比为分析学中"既可开逼近又可闭逼近"的集合。

> Kleene 定理（1955）：自然数的集合 A 是 [math]\displaystyle{ \Delta^1_1 }[/math] 的，当且仅当 A 是超算术的（HYP）。

这把可计算性理论（HYP，由机器和序数定义）与描述集合论（[math]\displaystyle{ \Delta^1_1 }[/math]，由投影/量化定义）两大传统焊接在一起，是 Kleene 获 1983 年 AMS Steele 奖的核心成果之一。证明的两个引理（Kleene's O 是 [math]\displaystyle{ \Pi^1_1 }[/math] 集、且是 [math]\displaystyle{ \Pi^1_1 }[/math] 中"最复杂"的完备集）都靠 SRT 沿良基树作有效超限递归建立。

在此基础上，SRT 向实数空间（Baire 空间，即自然数无穷序列的空间）推广后，成为有效描述集合论的引擎，三个代表性结果：

1. Suslin–Kleene 定理：Borel 集（从开集出发经可数次并、交、补生成的集合）与 [math]\displaystyle{ \Delta^1_1 }[/math] 集之间可以可计算地互译。它同时蕴含经典 Suslin 定理（[math]\displaystyle{ \Delta^1_1 = Borel }[/math]）和上述 Kleene 定理，是两大传统的汇合点； 2. 赋范归纳定理（Moschovakis 1974）：对带有良好"秩函数"结构的归纳定义，其最小/最大不动点保持在相应的可定义层级内。它的证明使用"关系版 SRT"（不动点代码 [math]\displaystyle{ \varepsilon }[/math]* 使自己的每个后继元组都由自己的前段定义）。这可视为对 Kleene 1944 年错误（见 3.3）的"正确打开方式"：SRT 只给某个不动点，要拿到最小不动点需要额外的秩结构； 3. 编码引理（Moschovakis 1970）：在 ZF+DC+AD（确定性公理，一个与大基数理论相关的集合论假设）下，若连续统可满射到基数 [math]\displaystyle{ \kappa }[/math]，则可满射到 [math]\displaystyle{ \kappa }[/math] 的幂集。证明通过带参数的 SRT作有效超限递归——SRT 由此进入基数算术这一纯集合论领域；它还是 Jackson 定理（1989：在 AD 下，三型存在量词的 Kleene 序数恰好等于最小的弱不可达基数）的基本工具——这是连接高类型递归论与大基数理论的最惊人结果之一。

此外，Kleene 1940 年代为直觉主义数学（拒绝排中律的构造性数学）构造的可实现性（realizability）解释中，bar 递归定义、bar 归纳与连续性原理的验证也本质地使用 SRT 的各种形式。

1. 1. 1. r.e. 索引集理论：Rice、Rice-Shapiro 与 Myhill

本板块把"程序行为性质"当作一个独立的研究对象。核心概念是索引集（index set）：给定某类程序行为，把"行为落在这类里"的全部程序编号收集起来，就得到 [math]\displaystyle{ \mathbb{N} }[/math] 的一个子集。若用程序 e 的定义域 [math]\displaystyle{ W_e }[/math]（§2.4）来编码行为、用 [math]\displaystyle{ \mathcal{A} }[/math] 表示某类 r.e. 集，则写法是

> A = { e : [math]\displaystyle{ W_e \in \mathcal{A} }[/math] }

（换成函数视角就是 A = { e : [math]\displaystyle{ \phi_e }[/math] 具有性质 [math]\displaystyle{ \mathcal{A} }[/math] }。）可判定、可枚举这类词只能作用于自然数集合，索引集正是那道翻译层——它把"程序行为问题"转写成 [math]\displaystyle{ \mathbb{N} }[/math] 的子集，之后才能问"这个性质能判定吗、能枚举吗"。两个要点：其一，此类性质必须只看行为、不看代码（同一函数的两个不同编号在 A 中必须同真同假），否则退化为平凡的代码分析；其二，记号上 r.e.（computably enumerable，可计算可枚举）就是 §2.4 的 r.e. 的现代同义词，二者完全等价。

与 SRT 的关系必须先分清：下面三个结果中，只有 Myhill 定理是 SRT 的应用（其证明核心是"程序 z 引用 z 自己的编号"，见 6.5.3）；Rice 与 Rice-Shapiro 不是 SRT 的推论——它们的标准证明分别是停机归约（对角线矛盾）与有限集/紧致性论证，全程不需要 SRT，SRT 至多给 Rice 提供一条事后捷径。也就是说，Rice 家族与 SRT"同源，但独立"：共享对角线血统，却不靠 SRT 的代码不动点力量成立。Rice 家族因此不宜与双递归定理等并列在 §5.2 的"推论"名义之下；本文把它们放在本板块，与 Myhill 定理并置，正是为了并排呈现"独立成立"与"依赖 SRT"这两种截然不同的关系。

1. 1. 1. 1. Rice 定理（1951）

陈述：程序行为的任何非平凡性质都不可判定。精确地说：设 [math]\displaystyle{ \mathcal{A} }[/math] 是某类部分可计算函数，既非空也非全体，则它的索引集 A = { e : [math]\displaystyle{ \phi_e \in \mathcal{A} }[/math] } 不是可计算集（更不是递归集）。

证明思路（停机归约——教科书标准路线，不依赖 SRT）： 1. 取一个"见证"函数 [math]\displaystyle{ \phi_a \in \mathcal{A} }[/math]。若处处无定义的函数恰好也在 [math]\displaystyle{ \mathcal{A} }[/math] 中，就对"补性质"（行为不在 [math]\displaystyle{ \mathcal{A} }[/math] 中）重做一遍论证——两类情况完全对称，故以下不妨设"恒发散"[math]\displaystyle{ \notin \mathcal{A} }[/math]； 2. 对每个 x，用 S-m-n 定理（§2.3）机械地造一个程序 h(x)：它先模拟"程序 x 在输入 x 上"的运行——这一步是对角线（让 x 面对自己的行为）；一旦该模拟停机，h(x) 就转而执行程序 a；若模拟永不停机，h(x) 也永不停机； 3. 于是 x 停在自己的输入上 ⟺ h(x) 计算的是 [math]\displaystyle{ \phi_a }[/math]（[math]\displaystyle{ \in \mathcal{A} }[/math]）⟺ h(x) [math]\displaystyle{ \in A }[/math]。若 A 可计算，就能机械判定"x 是否停在 x 上"，停机问题被解决——矛盾（§5.7.3）。

直觉：任何非平凡的"行为分类"都把停机问题吸收为自己内部的一个子问题——你若想机械地给每个程序的行为贴标签，就不得不先回答"程序 x 停在自己身上吗"，而那正是不可判定的对角线问题。

> 注（SRT 捷径，非本质）：Rice 定理也可用 SRT 三行证完：设 A 可计算，取变换规则 f(x) = "x [math]\displaystyle{ \in A }[/math] 时给一个 [math]\displaystyle{ \notin A }[/math] 的编号，否则给一个 [math]\displaystyle{ \in A }[/math] 的编号"（A 非空非全，顺序搜索即可机械实现），SRT 给出不动点 m 使 [math]\displaystyle{ \phi_m = \phi_{f(m)} }[/math]。若 m [math]\displaystyle{ \in A }[/math]，则 f(m) [math]\displaystyle{ \notin A }[/math]，同一函数 [math]\displaystyle{ \phi_m = \phi_{f(m)} }[/math] 却一个在 A 内、一个在 A 外（索引集只看行为），矛盾；m [math]\displaystyle{ \notin A }[/math] 同理。这条证明虽短，却是事后捷径——它没有揭示 Rice 定理与停机问题的血缘，而后者（上面的归约）才是定理的标准证明与本质机制。

1. 1. 1. 1. Rice-Shapiro 定理（1956）

Rice 定理回答"能否判定"；Rice-Shapiro 定理进一步刻画"何时能半判定"——把注意力从"A 是否可计算"收窄到"A 自身何时是 r.e. 的"：

> 设 A = { e : [math]\displaystyle{ W_e \in \mathcal{A} }[/math] } 是索引集。A 是 r.e. 的，当且仅当 [math]\displaystyle{ \mathcal{A} }[/math] 是"有限可生成"的：存在一个可计算列举的有限集列 𝒮 = {[math]\displaystyle{ S_0 }[/math], [math]\displaystyle{ S_1 }[/math], [math]\displaystyle{ S_2 }[/math], [math]\displaystyle{ \ldots }[/math]}，使得 W [math]\displaystyle{ \in \mathcal{A} }[/math] ⟺ 𝒮 中存在某个 [math]\displaystyle{ S_i \subseteq W }[/math]。

含义：一个行为性质若能被枚举地识别（索引集 r.e.），它就必须由有限证据决定——W 一旦包含某个预列的有限集 [math]\displaystyle{ S_i }[/math]，性质即成立；反之，性质成立也只需某个有限子集作证。"能识别 ⟹ 只依赖有限信息"这一半是紧致性式的论证（若性质的成立只靠无限多证据，枚举过程就永远等不到决定性的一刻）；"有限可生成 ⟹ 可枚举"那一半是直接列举。两个方向都与 SRT 无关。

Rice-Shapiro 不是 SRT 的推论，而是索引集理论中独立的结构定理，并且它比 Rice 定理更强——由它可以推出 Rice 定理：若非平凡索引集 A 可计算，则 A 与补集都是 r.e. 索引集，Rice-Shapiro 给 [math]\displaystyle{ \mathcal{A} }[/math] 与其补类都套上"有限可生成"；而有限可生成自动蕴含"超集仍在类中"，把两个类里各自的成员并起来，就得到同时属于两类的一个 r.e. 集，矛盾。可见在"识别程序性质"的问题上，真正的母定理是 Rice-Shapiro 而非 SRT。

1. 1. 1. 1. Myhill 定理：创造集 = 完备集

背景：停机问题集合 K = {e : 程序 e 在输入 e 上停机} 是 r.e. 集中"最不可判定"的——任何 r.e. 集都能通过可计算的翻译归约到它（称为 r.e.-完备，complete）。另有一个看似完全不同的概念：一个 r.e. 集 A 称为创造集（creative set），如果它的补集是"能系统地生产反例"的——存在一个可计算程序，你给它任何与 A 不交的 r.e. 集，它都能吐出一个既不在 A 里也不在那个集合里的元素。创造性是 Post 1944 年为刻画"不可判定的源泉"而引入的概念。

> 定理（Myhill 1955）：每个创造集都是 r.e.-完备的；两个概念重合。

证明中 SRT 的关键一步：想把任意 r.e. 集 B 归约到创造集 A，需要构造一个程序 z，使得"若 x [math]\displaystyle{ \in B }[/math]，则 z 枚举出 {u(z)}；否则 z 枚举空集"——z 的定义里用到了 z 自己的编号（u(z) 是生产反例的程序作用于 z）。这正是 SRT 合法化的自指；没有这个自指，证明无法闭合。由此 Rogers 还得到推论：所有创造集在"可计算的重新命名"意义下完全相同（两两递归同构）——从可计算性角度看它们"长得一模一样"。

1. 1. 1. 有效运算的连续性：Myhill–Shepherdson 与 KLS–Čeĭnin 定理

背景：一个"程序变换"[math]\displaystyle{ \Phi }[/math] 把函数 [math]\displaystyle{ \phi }[/math] 变成新函数 [math]\displaystyle{ \Phi(\phi) }[/math]。有两种实现方式：按代码操作（给 [math]\displaystyle{ \Phi }[/math] 输入 [math]\displaystyle{ \phi }[/math] 的程序编号，让它随便分析代码——类似"按名调用"）与按值操作（[math]\displaystyle{ \Phi }[/math] 只能查询 [math]\displaystyle{ \phi }[/math] 在具体输入上的输出，像黑盒——类似"按值调用"）。直觉上按代码操作更强大（能读源代码），但：

> Myhill–Shepherdson 定理（1955）：对可计算变换而言，两种方式恰好等价——任何"按代码"的可计算变换都能改写成"按值"的图灵机计算，反之亦然。

证明的两个关键引理（变换必然是单调的、必然是连续的）都依赖 SRT：构造一个"监视 [math]\displaystyle{ \Phi }[/math] 是否已输出、在此之前模仿函数 [math]\displaystyle{ \phi_1 }[/math]、之后叛变为函数 [math]\displaystyle{ \phi_2 }[/math]"的程序 z——z 的行为取决于 z 自己（经 [math]\displaystyle{ \Phi }[/math] 处理后）的表现，由 SRT 提供，再用"同一函数的不同编号必须得到同一结果"逼出矛盾。

> Kreisel–Lacombe–Shoenfield–Čeĭnin 定理（1957/1962）：作用在全函数上的可计算变换必然是连续的——输出在任何点的值只依赖输入函数的有限个值；而且可用确定性图灵机实现。

Čeĭnin 的版本——"构造度量空间之间的每个可计算算子都是有效连续的"——是俄罗斯构造性分析学派（用可计算性重新奠基数学分析）的中心结果之一。证明中 SRT 出现两次，用法与上述如出一辙。

此外，Rogers 用 SRT 证明了 Blum 定理：任意两个"通用部分函数"（即解释器）都只差一个可计算的重新编号（递归同构）——编号系统在"重新命名"意义下本质唯一。

1. 1. 1. Solovay 可证性逻辑

背景：可证性逻辑（provability logic）研究"可证"这个概念的抽象规律，把 "⌜[math]\displaystyle{ \phi }[/math]⌝ 在 PA 中可证" 抽象为模态算子 □[math]\displaystyle{ \phi }[/math]。模态逻辑系统 GL（Gödel–Löb 逻辑）是候选公理系统。

> Solovay 定理（1976）：一个模态公式在 PA 的所有解释下都可证，当且仅当它是 GL 的定理。即 GL 恰好完全刻画了 PA 的可证性逻辑。

Solovay 的证明漫长精巧，其关键引理需要构造一个自指的函数 h——h 的定义中引用 h 自己的编号。Solovay 本人用一句话带过："表面上的循环用递归定理以通常方式处理"。Moschovakis 评论：无法想象不借助 SRT 如何凭空想出这个构造——在此意义上 SRT 是可证性逻辑这块基石中不可或缺的成分。

1. 1. 1. 应用地图一览

|领域|代表性结果|SRT 的角色| | -------- | -------------------------------------- | ------------------- | |r.e. 索引集理论|Rice 定理；Rice-Shapiro；Myhill：创造集 = 完备集|前两者：同源但独立（非 SRT）；Myhill：构造"监控自己"的程序〔§2〕| |有效运算|Myhill–Shepherdson；KLS–Čeĭnin 连续性|证明单调性与连续性〔§§3–4〕| |可证性逻辑|Solovay：GL 完备性|构造自指函数〔§6〕| |序数记号|通用系统、Kleene's O、[math]\displaystyle{ \omega_1^CK }[/math]|最初的用武之地〔§7〕| |超算术理论|Markwald–Spector；Spector 唯一性；HYP = [math]\displaystyle{ \Delta^1_1 }[/math]|每个证明的归纳枢纽〔§§8–9〕| |有效描述集合论|Suslin–Kleene；赋范归纳；编码引理|关系版/参数版 SRT〔§10〕| |高类型递归|Kleene 1959 体系；Jackson 定理|理论的第一块基石〔§11〕| |直觉主义数学|可实现性、bar 递归合法性|验证自指定义〔§12〕| |函数式编程|Y 组合子的推广、部分求值|元编程的不动点原理|

（表中"§"编号均指 Moschovakis 2010 的章节。）

---

1. 1. 评注与影响

1. 简单性与普适性的反差。SRT 的全部证明只有一行对角线，应用却横跨逻辑学几乎所有分支。Moschovakis 指出：其广泛适用性恰恰源于这种简单——它极易被翻译到自然数以外的语境（实数空间、任意 Polish 空间、高类型对象、模态逻辑），在每个语境中重新化身。 2. 两个递归定理的分工。第一递归定理保证递归定义有最小解（函数层面、序理论的不动点）；第二递归定理保证自指定义合法（代码层面的不动点）。前者回答"这个函数方程有解吗"，后者回答"我能在定义中引用被定义者自己的代码吗"。强定理蕴含弱定理，反之不然（见 4.4）。 3. 自指的数学化。从 Gödel 的替换函数、Turing 的通用机、von Neumann 的自复制自动机，到 quine、计算机病毒、编译器自举，乃至人工智能中"系统改进自身"的设想，"系统谈论自身"的可行性边界都由同一种对角线结构划定。Kleene 递归定理是这一结构最干净、最一般的陈述。 4. 历史反讽。Kleene 1938 年发明 SRT 是为了构造序数记号，而 1944 年他恰恰因为"拿到一个不动点却误以为拿到最小不动点"而犯下著名错误，直到 1955 年才纠正（见 3.3）——这个故事最恰当地说明了理解两个递归定理区别的重要性。 5. Rogers 的总评：递归定理是"一个基本的研究工具、一个深刻的结果"（a basic research tool [math]\displaystyle{ \ldots }[/math] a deep result），它的深刻在于"以优雅和智识上的经济性，处理那些否则需要繁复构造的问题"；虽然它的直接效果常是产生各种"病态"结构（自我枚举的集合、自我打印的程序），但它在 Myhill 定理等结果中起到了"在此前独立定义的概念之间建立正则联系"的作用。

---

一手文献

综述与教材（本文主要依据）