递归函数——通向"可计算"的定义之路

上级：logic

（偏）递归函数

最小的偏函数类 ℕᵏ → ℕ（对所有 k），包含以下基本函数：

• 零函数 Z(x) = 0、后继函数 S(x) = x+1、投影函数 Pᵢ(x₁,…,xₖ) = xᵢ，

并且对三种构造方式封闭：

• 复合（Composition）——由元数为 m 的 g 与元数为 k 的 h₁,…,hₘ，构造 f(x₁,…,xₖ) = g(h₁(x₁,…,xₖ),…,hₘ(x₁,…,xₖ))。
• 原始递归（Primitive recursion）——由元数为 k 的 g 与元数为 k+2 的 h，构造元数为 k+1 的 f：f(0, x) = g(x)，f(n+1, x) = h(n, f(n, x), x)。
• 极小化算子 μ（Minimization）——由元数为 k+1 的 g，构造 f(x) = μn.[ g(n, x) = 0 ] = 使 g(n,x)=0 成立的最小 n（且对所有 i<n，g(i,x) 均有定义且非零）；若不存在这样的 n，则无定义。

按保留了哪些构造方式，可以分出三个具名子类：

• 仅保留基本函数 + 复合 + 原始递归 → primitive recursive——全部完全（total，总是停机）；
• 加入 μ → 一般递归 / μ-递归 = 偏递归函数；
• 该类中完全的成员 → 完全递归函数。

为什么"完全递归"是个微妙的概念

完全递归函数 = 那些完全（对每个输入都停机）的可计算函数。有两个不太显然的事实：（1）你无法有效地列出它们——没有算法能恰好枚举出所有完全函数（对角化：总能在任何给定的列表之外构造出一个完全可计算函数）；（2）"这个程序是否完全？"是不可判定的——事实上属于 Π₂，比停机问题更难。所以"完全递归"是一个干净的数学类，却没有可判定成员资格的算法把手——不像r.e.的偏递归函数，那是可以枚举的。

这个阶梯意味着什么

• 原始递归 ⊊ 完全递归 ⊊ 偏递归。 第一步严格包含关系有一个明确的见证者：Ackermann 是完全且可计算的，但不是原始递归的（for 循环太弱了）。
• 最高一级等于Turing machines与λ-calculus——即Church–Turing thesis。
• 这一跃升正是从有界递归到无界递归：原始递归 = for 循环（完全）；加入 μ = while 循环（图灵完备，可能不停机）。这正是phase transition——不可判定性开始出现的地方。

（现在定义已经固定，举个例子：factorial(0)=1，factorial(n+1)=(n+1)·factorial(n) 就是原始递归，其中 g=1，h(n,y,·)=(n+1)·y。）