原创 集智百科团队 2026-10-28 14:30 日本

Stephen Cole Kleene提出的递归函数论，即可计算性理论中的一组基本定理

递归定理（recursion theorem）是递归函数论，即可计算性理论（computability theory）中的一组基本定理，由Stephen Cole Kleene提出，合称 Kleene 递归定理，包括两条：第一递归定理: 任何用递归方式定义的函数方程都有可计算的（最小）解——机械式的递归定义永远合法、永远有解；第二递归定理: 对任何可计算的全函数 f，总存在一个程序编号（即源代码）c，使得执行c与执行编号（源代码）为f(c)的计算效果完全相同，因此程序可以合法地引用自己的代码。两条之中，第二递归定理尤为重要，它是数学中对自指（self-reference）现象最简洁、最有力的统一陈述：它只有一步对角线证明 `c=S(e,e)`（S 是"把程序的部分输入写死、生成新程序"的柯里化操作（Currying），详见2.3小节），却统一了从罗素悖论（1901）、哥德尔不完备定理（1931）、图灵停机问题（1936）、冯诺伊曼自复制自动机（1948）到今天的Quine程序（1960s）等全部自指现象——它们本质上是同一种对角线/自指结构的不同化身（详见5.7小节）。

图1：六个经典自指现象——康托尔对角线（1891）、罗素悖论（1901）、哥德尔不完备定理（1931）、图灵停机问题（1936）、冯诺伊曼自复制（1948）、Quine（自打印程序，1960s）和自省程序(以及自省式自修改程序，2026）——都源于同一种对角线/自指原理；Kleene 第二递归定理是这一原理最一般的陈述。

第二递归定理可以用公式表达为：

这里的ϕ代表通用函数，ϕ_c代表通用函数在模拟代码为c的程序计算，≃代表左右两个函数功能等价，即它们在所有的输入数据上要么计算结果相等，要么无定义。

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

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

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

第二递归定理（日常语言版）：对任何可计算的全函数 f（一个对任何输入都停机的"程序变换"），总存在一个源程序 c，使得执行 c 的效果，等同于执行 f(c)——即 f 拿着 c 自己的源代码算出来结果（通常结果都是一个自然数或字符串，对应为一个程序的编号或源代码）的那个程序。用符号写就是：ϕ_c≃ϕ_f(c)^[1].

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

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

图2：两个定理的"不动点"含义截然不同——左：函数 φ经变换Ψ 后变回 φ（函数层面）；右：程序 n 经变换 f 后变成另一个程序 f(n)（通常f(n)≠n），但ϕ_n=ϕ_f(n)（代码变了，行为不变）。§2.5 对此有详细辨析。

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

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

2.1 “可计算”与“部分函数”

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

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

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

2.2 通用程序（解释器）

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

2.3 s-m-n 定理（柯里化 / 参数特化）

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

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

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

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

2.5 “不动点”的两种含义

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

• 函数层面的不动点（第一递归定理）：变换规则 Ψ 把函数 ϕ 变成新函数 Ψ(ϕ)；若 Ψ(ϕ)=ϕ（作为函数处处相等），ϕ 就是 Ψ 的不动点。这与分析学中"f(x)=x 的解"同类。

• 代码层面的不动点（第二递归定理）：变换规则 f 把程序编号 n 变成新编号 f(n)；注意 f(n)≠n 通常成立——程序代码确实变了；但神奇的是，新程序 f(n) 和旧程序 n计算的函数相同：ϕ_n=ϕ_f(n)。所以"不动"的不是代码，而是代码的行为。Rogers 为此特意造了"不动点值（fixed-point value）"一词，强调它不是数值不动点^[1]。

3. 历史背景

3.1 起源：一篇研究“序数记号”的 6 页短文

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

背景知识——序数（ordinal number）：序数是"无限队列的长度"的数学化。数完 0, 1, 2, 3, …（全体自然数）之后，数学上允许继续数：第一个"超过所有自然数"的序数记作 ω，然后还有 ω+1, ω+2, …, ω⋅2, …, ω², …, ω^ω, …，可以无限延伸。所有"能用可数步骤达到"的序数称为可数序数，它们的总体（第二数类）是不可数的。

Church 与 Kleene 在 1930 年代问了一个构造性问题：能不能给每个可数序数起一个"机械可读的代号"（自然数编码），使得仅凭代号就能机械地判断：这个序数是 0、是某个序数的后继（+1）、还是某个递增序列的极限？并且在后两种情况下能机械地取出前驱代号或序列代号？ 满足这些条件的编码方案称为一个序数记号系统（Kleene 称之为 r-system）^[4]。

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

• 若 ψ(z,x) 是任意可计算的部分函数，则存在一个数 f，使得 ϕ_f(x)=ψ(f,x) 对所有 x 成立（等号含义：两边同时无定义，或同时有定义且相等）。

• 证明：设 e 是函数 ψ(S(y,y),x) 的编号，取 f=S(e,e) 即可。

——这就是第二递归定理的原始形态。Moschovakis说连Kleene自己都没有意识到，他发掘出的，是一颗珍贵的"小宝石"（little gem）^[3]；Kiselyov 则以"函数式珍珠（A Functional Pearl）"为题向函数式编程社区重新发掘了它^[5]。

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

3.2 命名史

Kleene 本人始终只叫它 "the recursion theorem"（递归定理）——即使在他 1952 年的《元数学导论》（Introduction to Metamathematics）中两个定理同时出现时，也未加区分^[3]。

Rogers (1967)在其经典教材第 11 章首次建议：在两个定理同台的语境中，把关于"函数变换规则的不动点"的定理称为第一递归定理（Rogers 书中 Theorems XI、XII），把 Kleene 1938 的定理称为第二递归定理（Rogers 书中 Theorem IV，Second Recursion Theorem，后文简称SRT，）^[1]。Moschovakis 明确表示支持："在允许投票的场合，我投票采纳 Rogers 的命名"^[3]。

有学生曾问 Kleene，这个"短得可疑、巧得离谱"的两行证明从何而来（指Kleene 第二递归定理的证明，见SRT的证明）？Kleene（也许是开玩笑地）回答说他只是"拿着 s-m-n 的性质瞎鼓捣"（"fiddled around with (b)"）就给出了这个证明^[3]。Moschovakis 评论说，这种"鼓捣"很可能受到 lambda演算（Church 与 Kleene 此前共同发展的形式系统）中类似对角线构造的启发。

3.3 一个值得铭记的教训

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

4. 第一递归定理（FRT）

4.1 从“递归定义的函数”说起

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

α=Ψ(α)

其中 Ψ 是一个"函数变换规则"（输入一个函数 α，输出一个新函数 Ψ(α)；术语叫算子，operator）。例如阶乘定义对应的 Ψ 是：给定任意函数 α，输出新函数 α′，其中 α′(0)=1，

α′(n)=n⋅α(n−1)。

第一递归定理问的是：什么样的 Ψ 能保证方程 α=Ψ(α) 有解，而且解是可计算的？

4.2 定理表述

定义（可计算的变换规则）：如果变换 Ψ 满足下面两条，就称它是递归算子（recursive operator）：

1. 单调性：α⊆β（即 β 在 α 有定义的地方都有定义且取值相同）蕴含 Ψ(α)⊆Ψ(β)；

2. 有限性/连续性：Ψ(α) 的每个输出只依赖 α 在有限个输入上的值。

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

第一递归定理：设 Ψ 是递归算子，则存在函数 α 使得：

1. Ψ(α)=α（α 是方程的解，即 Ψ 的不动点）；

2. 最小性：任何其他解 β 都满足 α⊆β（α 是"信息最少"的解）；

3. 可计算性：α 是可计算的部分函数。

证明思路：从"处处无定义的空函数"出发，反复应用 Ψ：α₀=∅，α₁=Ψ(α₀)，α₂=Ψ(α₁),……。单调性保证这个序列不断"变长"（每次迭代只增不减）；有限性保证最终收敛到一个函数 α，且 Ψ(α)=α；"每一步都是机械操作"保证 α 整体可计算。取所有 α_n的并就是答案^[1]。

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

4.3 意义：递归定义的“存在性定理”

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

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

4.4 与第二递归定理的关系

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

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

5. 第二递归定理（SRT）

5.1 三种等价表述

表述 A（Kleene 原始形式，1938）：对任意可计算的部分函数 ψ(z,x)，存在编号 f 使得对所有 x：

ϕ_f(x)=ψ(f,x)  （表述A）

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

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

ϕ_n≃ϕ_f(n)  （表述B）

这里，符号≃表示的是函数的等价，即当左右两侧的函数在输入x上有定义时，则左右两边的函数值相等；当没有定义时，则左右两侧都没有定义函数值。Rogers 是这样解释该表述的："Let f be any recursive function; then there exists an n such that ϕ_n=ϕ_f(n)."^[1]，意思是：f 拿着程序 n 的源代码算出一个新程序 f(n)，而新程序与旧程序计算的是同一个函数^[1]。

表述 C（带参数的强化形式）：A、B 只断言不动点"存在"，表述C 进一步保证：不动点能被程序机械地找出来，并且能随参数连续变化。设想变换规则额外带一个参数 y——用一个三元函数 ψ(e,y,x) 表示"编号为 e 的程序在参数 y 下的行为"。那么存在一个可计算的全函数 z：你输入 y，它就输出针对这个参数的不动点编号 z(y)，使得:

ϕ_z(y)(x)=ψ(z(y),y,x)（表述C）

对所有 x 成立。此外还能要求：①不动点不止一个，而是无穷多个；②不同参数 y 给出不同的编号（z 是单射，即不同的输入对应不同的输出）^[1][3]。

5.2 证明

这里列举两种本质上相同的证明方法。

5.2.1 一行对角线

以表述A 为例，全部证明如下：

首先，根据s-m-n定理，对于任意的编号为a的二元输入可计算函数，以及任意的自然数y，这个二元函数都等价于一个一元可计算函数：

ϕ_S(a,y)≃ϕ_a(y,⋅)

其中，S(a,y)为这个对应的一元函数的编码，它在任意输入x上的计算效果等价于编号为a的二元函数在输入y,x上的计算效果（当无定义的时候，两边同时无定义）。

其次，不难知道函数 ψ(S(y,y),x) 是可计算的（它只是把 §2.3 的柯里化操作 S 和 ψ 复合起来），所以它有编号，设为 e。令 f=S(e,e)，则对任何输入 x：

ϕ_f(x)=ϕ_S(e,e)(x)=ϕ_e(e,x)=ψ(S(e,e),x)=ψ(f,x)∎

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

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

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

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

这一方法分三步走。

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

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

——双重编号。把 E₀、E₁、E₂、… 并排写下来就是一张二维表（图 6 的上半部）：每行 E_k 是一个枚举、每列 n 是"该行第 n 个值"、每格是某个具体的可计算函数。这张表把"枚举可计算函数的所有方式"完整地、不重不漏地列了出来。

• 2. 对角线枚举D

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

D 仍然是一个可计算的枚举：由 h(x)=ϕ_x(x) 给出（图 6 黄底一行的"沿主对角线"）。它满足一个关键性质：

——因为 E_k 的第 (k+1) 项 = ，而 D 的第 (k+1) 项 = ，两者恰好对得上（图 6 右侧红字注释）。

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

设 f 是任意全可计算函数。沿 D 的每一项先用 f 得到新的程序编号（源代码），再去取对应的可计算函数，得到另一个枚举：

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

取 ：k=m：D^∗=E_m，所以D^∗的第(m+1)项 =E_m的第(m+1)项 =。而D^∗的第(m+1)项由定义也是

Cutland 用 Lemma 2.1 把"第 m 行"调整成全的（即 ϕ_m 是全函数），所以 ϕ_m(m) 是一个良定的自然数 n。设 n=ϕ_m(m)，则：

n 就是 f 的不动点 ∎^[6].

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

图6：Cutland (1980) 列表法证明的视觉化。上半：四行四列的"枚举之枚举"表 E₀,E₁,E₂,⋯,E_k，每格填 ；主对角线（红圈）上的格子构成对角枚举 D。黄底 D 行：把对角线上的格子抽出，得到 。D^∗ 行：把 f 套到 D 上得到——可计算 ⇒ 必是某行 E_m。绿框：取 k=m 撞上 E_m，得 ，再设 n=ϕ_m(m) 即得 ϕ_n≃ϕ_f(n)——f 的不动点。

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

递归函数即可计算函数。然而，我们接触到的大部分程序都是使用字符串来编码，而并非使用自然数。这就使得初学者会对函数或程序的编码非常困惑，而第二递归定理（SRT）本身就是建立在两套编码对应的函数功能等价的基础之上的，因此造成很多的理解困惑。

实际上，一个递归函数，或可计算的图灵机程序，既可以被编码为自然数，又可以被编码为字符串，也就是源程序代码，二者本质上等价。要建立这种等价关系，我们只需要按照字典序为所有可能的字符串做自然数编码就可以了，于是任何一个字符串都对应了一个自然数，反之自然数也可以对应回字符串。这样，所有关于SRT的结论都自然能够平移到我们熟悉的以字符串对应函数编码的程序世界里。

程序世界里SRT的一个最简单的对应物就是Quine程序，即“打印自己源代码”的程序。

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

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

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

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

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

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