阿克曼函数——完全可计算，但不是原始递归
primitive recursion ⊊ 完全可计算的经典见证：一个你显然能计算、却没有任何 for 循环程序能计算的函数。
阿克曼函数
A(0, n) = n + 1A(m+1, 0) = A(m, 1)A(m+1, n+1) = A(m, A(m+1, n))最后一行在自己的参数内部递归——是嵌套，不是单纯的计数器。
A 是完全的（每次调用都会终止——数对 (m,n) 按字典序严格递减），也显然是可计算的（照规则执行即可）。
Theorem
A不是原始递归的 阿克曼函数比任何原始递归函数都增长得快。
Proof支撑证明的是一条支配引理：每一个原始递归函数都被某个单一的阿克曼层级封顶。我们要用到
A的几条标准单调性（均可用归纳法证明）：A(m,n) > n；A在每个参数上都严格递增；以及层级吸收：A(a, A(b,n)) ≤ A(max(a,b)+2, n)——嵌套两层的代价只是一个常数。引理。 对任意原始递归函数
f(x₁,…,xₖ)，都存在一个固定层级t，使得对所有输入都有f(x⃗) < A(t, max(x⃗))。对
f的构造做结构归纳来证明。
- 基础情形。 零函数
= 0、后继函数= A(0,x)、投影函数≤ max(x⃗)——全部都< A(1, max(x⃗))。- 复合。
f = g(h₁,…,hⱼ)。由归纳假设，每个hᵢ < A(u, max(x⃗))（取最大的u），且g < A(s, 其参数的最大值)。于是f < A(s, A(u, max(x⃗))) ≤ A(max(s,u)+2, max(x⃗))，由层级吸收得到——仍是一个固定层级。- 原始递归。
f(0,x⃗)=g(x⃗)，f(n+1,x⃗)=h(n,f(n,x⃗),x⃗)，由归纳假设g < A(p,·)，h < A(q,·)。展开递归：每一步都套用一次（被A(q,·)界定的）操作，共n层深。而A(q,·)迭代n次仍不超过A(q+1, n+·)——这恰好就是递推式A(q+1, n+1) = A(q, A(q+1, n))。所以f < A(q+2, n + max(x⃗))——同样是一个固定层级。每一种构造方式都只把所需层级抬高一个常数，所以任何固定的原始递归函数
f都落在某个固定层级t之下。∎（引理证毕）现在对角化。 假设
A确实是原始递归的。那么g(n) = A(n,n) + 1也是原始递归的（把A与对角线复合而成），于是引理给出一个固定的t，使得对所有n都有g(n) < A(t, n)。令n = t：A(t,t) + 1 = g(t) < A(t, t)——矛盾。所以A不是原始递归的。∎
寓意：一个原始递归函数被困在层级体系 A(0,·), A(1,·), A(2,·), … 中某个固定的梯级 t 上；而 A(n,n) 会随 n 一路往上爬梯级，所以它逃出了每一个固定梯级。
增长速度极其剧烈：A(4,2) 就已经有 19,729 位十进制数字。这份额外的威力来自嵌套递归——恰恰是有界计数器无法表达的东西，也预示了 general-recursion 中那种无界搜索。（A 本身依然是完全的；你还不需要不终止性——但你已经离开了 for 循环的世界。）