Kleene 不动点——递归的序路线

上级：logic

"Kleene"这个名字对应三个不同的定理；讲等价性的那个是 kleene-theorem。不动点版本,才是递归的含义所在。

一、Kleene 不动点定理(域论——递归的语义)

从

⊥ 向上攀爬得到最小不动点 在一个 CPO(一个带有最小元 ⊥、且任意升链都有上确界的偏序集)上,给定一个 Scott 连续的 f,最小不动点为 lfp(f) = ⊔ₙ fⁿ(⊥) = ⊥ ⊑ f(⊥) ⊑ f²(⊥) ⊑ … ——即从底元开始迭代 f 所得升链的上确界。

这正是递归定义的含义。一个递归函数,就是 X = F(X)(其定义泛函为 F)的最小解;Kleene 定理说这个解存在,并且可以通过从未定义函数 ⊥ 开始展开来达到——第 n 次近似,就是"展开 n 层之后所计算出的函数"。Y 组合子(lambda-calculus)正是把这个不动点用语法的形式表达出来。

二、Kleene 递归(不动点)定理(可计算性——自指)

程序可以看到自己的代码

对每一个全可计算函数 f,都存在一个程序 e 使得 $\varphi_e = \varphi_{f(e)}$——也就是说,e 所计算的函数与 f(e) 所计算的相同。

于是一个程序可以获得并使用它自己的源码——这正是quine 程序、能自举的编译器、以及对角化论证背后的原理。这是另一种"不动点":不是数据上某个函数的不动点,而是程序上某个变换的不动点。

它出现在哪里(无处不在)

• 正则语言: Arden 法则 X = A X | B ⟹ X = A*B 就是一个最小不动点;Kleene 星号运算符本身就是一个不动点算子(kleene-theorem、regular-expressions)。
• Bellman / 强化学习: 值迭代通过从下方逐步攀爬,把价值函数收敛到 Bellman 算子的最小不动点(sequential-and-control)。
• 类型: 归纳类型 = 函子的最小不动点(初始代数);余归纳类型 = 最大不动点(终余代数)(type-theory)。

结论——通向同一个不动点的两条路线

递归的含义始终是"求解 X = F(X)",而保证有解的方法有两种:

• Kleene / order: F 在 CPO 上单调/连续 → 得到最小不动点,通过从 ⊥ 向上攀爬达到;
• Banach / metric: F 在完备度量空间上是一个压缩映射 → 得到唯一不动点,通过收缩(几何收敛)达到。

序 vs 度量;最小 vs 唯一;攀爬 vs 收缩。我们所讲的 convergence 故事是度量的那一半——而这里补上了它缺失的序论对偶。