定义
本文为了方便，本文有时将一系列参数 $x_1, x_2, \dots, x_n$ 记作 $x_{1\dots n}$，并将 $g_1(x_{1\dots m}), g_2(x_{1\dots m}), \dots,g_k(x_{1\dots m})$ 记作 $g_{1\dots k}(x_{1\dots m})$。
原始递归函数
原始递归函数是指仅用基本原始递归函数经过复合和原始递归两种操作可以得到的函数。其中基本原始递归函数指以下三类函数：
- 常数函数。0 元函数 $0$。
- 后继函数。1 元后继函数 $S$。
- 投影函数。$P^n_i$ 接受 $n$ 个参数返回第 $i$ 个参数，即 $P^n_i(x_{1\dots n}) = x_i$。
复合操作是指，$k$ 元函数 $f$ 和 $k$ 个 $m$ 元函数 $g_{1\dots k}$ 可以复合成函数
$$ h(x_{1\dots m} ) = f(g_1(x_{1\dots m}), g_2(x_{1\dots m}), \dots,g_k(x_{1\dots m})) $$
原始递归操作是指，给定 $k$ 元函数 $f$ ，和 $k + 2$ 元函数 $g$，可以得到 $k + 1$ 元函数 $h$：
$$ \begin{split} h(0,x_{1\dots k}) &= f(x_{1\dots k}) \\ h(S(n),x_{1\dots k}) &= g(h(n,x_{1\dots k}),n,x_{1\dots k}) \end{split} $$
Ackermann 函数
$$ \begin{split} A(0, n) &= S(n) \\ A(S(m), 0) &= A(m, 1) \\ A(S(m), S(n)) &= A(m, A(S(m), n)) \end{split} $$
接下来我们会证明，Ackermann 函数不是原始递归函数。
证明
易知 Ackermann 函数在两个参数的方向上都单调递增，且 $A ( m , n ) > m$ 和 $A ( m , n ) > n$。
引理1
引理 1：$∀ m , n . A ( m , A ( n , l ) ) < A ( \max { m , n } + 3 , l )$
证明：记 $k=\max { m , n }$ ，则 $A(m,A(n,l)) < A(k,A(S(k),l)) = A(S(k), S(l))$。
使用数学归纳法证明 $A(k+3, l)>A(S(k),S(l))$ ：
当 $l = 0$ 时 $A(S(k), S(l))=A(S(k), 1)$，而 $A ( k + 3 , l ) = A ( k + 2 , 1 ) > A ( S ( k ) , 1 )$。
当 $l > 0$ 时由归纳条件 $A(k+3, l-1)>A(S(k), l)$ ，因此
$$ \begin{split} A(k+3, l)&=A(k+2,A(k+3, l-1))\\ &>A(k+2,A(S(k), l))\\ &>A(k, A(S(k), l) = A(S(k), S(l)) \end{split} $$
引理 1 证毕。
引理2
引理 2：$\forall m\ge 1,n\ge 0.A(S(m),n)> A(m, 2n)$
证明： 对 $n$ 归纳：
$A(S(m),0)=A(m, 1)>A(m,2\times 0)$
$A(S(m),S(n))=A(m,A(S(m),n))>A(m,A(m,2n))$
因此需要证明 $A(m,k)\ge k+2$。对 $k$ 归纳：
$A(m,0)\ge A(1,0)=2=0+2$
$A(m,S(k))=A(m-1,A(m,k))\ge A(m-1,k+2)\ge k+3=S(k)+2$
引理 2 证毕。
证明
定义概念支配：如果对于 $n$ 元函数 $f$，$\exists t\ .\forall x_{1 \dots n}\ .f(x_{1\dots n})<A(t, \max{x_{1\dots n}})$，那么称 $f$ 被 $A$ 支配，记作 $f\prec A(t,\cdot)$ 。接下来的证明思路是证明所有原始递归函数都被 $A$ 支配，从而得到 $A$ 不是原始递归函数。
首先证明三个基本原始递归函数都被 $A$ 支配，这很容易：
$0<A(0,0)$
$S(n) = A(0, n) < A(1, \max{n})$
$P^n_i(x_{1\dots n})=x_i \le \max{x_{1\dots n}}<A(0,\max{x_{1\dots n}})$
然后证明复合和原始递归两种操作产生的结果都被 $A$ 支配。
对于 $k$ 元原始递归函数 $f$ 和 $k$ 个 $m$ 元原始递归函数 $g_{1\dots k}$，如果 $f\prec A(t_f,\cdot)$，$g\prec A(t_g,\cdot)$，那么它们的复合：
$$ \begin{split} h(x_{1\dots m} ) & = f(g_1(x_{1\dots m}), g_2(x_{1\dots m}), \dots,g_k(x_{1\dots m})) \\ &<A(t_f,\max\{g_{1\dots k}(x_{1\dots m})\}) \\ &<A(t_f,\max\{A(t_1,\max\{x_{1\dots m}\}),A(t_2,\max\{x_{1\dots m}\}),\dots, A(t_k,\max\{x_{1\dots m}\})\})\\ &\le A(t_f,A(\max\{t_{1\dots k}\},\max\{x_{1\dots m}\}) \\ &<A(\max\{t_f, t_{1\dots k}\}+3, \max\{x_{1\dots m}\}) \end{split} $$
倒数第一步用了引理 1。因此 $h\prec A(\max{t_f, t_{1\dots k}}+3,\cdot)$。
而对于原始递归操作，给定 $k$ 元原始递归函数 $f$，和 $k+2$ 元原始递归函数 $g$，如果有 $f\prec A(t_f,\cdot)$，$g\prec A(t_g,\cdot)$，那么它们经过原始递归操作得到的 $k+1$ 元原始递归函数 $h$ ，记 $t_h=\max{t_f,t_g}+1$，我们先归纳证明 $\forall n.h(n,x_{1\dots k})< A(t_h,\max{n,x_{1\dots k}}+n)$：
$h(0,x_{1\dots k}) = f(x_{1\dots k}) <A(t_f,\max{x_{1\dots k}})<A(t_h,\max{0,x_{1\dots k}})$
$$ \begin{split} h(S(n),x_{1\dots k}) &= g(h(n,x_{1\dots k}),n,x_{1\dots k})\\ &<A(t_g,\max\{h(n,x_{1\dots k}),n,x_{1\dots k}\})\\ &\le A(t_g,\max\{A(t_h,\max\{n,x_{1\dots k}\}+n),n,x_{1\dots k}\})\\ &=A(t_g,A(t_h,\max\{n,x_{1\dots k}\}+n))\\ &\le A(t_h-1,A(t_h,\max\{n,x_{1\dots k}\}+n))\\ &=A(t_h,\max\{n, x_{1\dots k}\}+n+1)\\ &\le A(t_h,\max\{S(n), x_{1\dots k}\}+S(n)) \end{split} $$
因此根据引理 2
$$ \begin{split} h(n,x_{1\dots k})&\le A(t_h, \max\{n,x_{1\dots k}\}+n)\\ &\le A(t_h,2\max\{n,x_{1\dots k}\})\\ &<A(S(t_h),\max\{n,x_{1\dots k}\}) \end{split} $$
因此 $h\prec A(\max{t_f,t_h}+2,\cdot)$。
由此证明 $A$ 不是原始递归函数，否则存在 $t_a$ 使得 $\forall m, n . A(m,n)<A(t_a, \max{m,n})$，将 $t_a$ 代入 $m$ 和 $n$ 的位置就有 $A(t_a,t_a)<A(t_a,t_a)$，产生矛盾。
后记
本来想的证明思路是证明原始递归函数有某种性质，而 Ackermann 函数没有，但是想不出来，翻英文 wiki 加咨询 DeepSeek 才得到现在这个证明思路，中间证明原始递归操作卡了我一天一夜……。其实这个思路也属于我一开始的思路，因为相当于证明原始递归函数有“被 Ackermann 函数支配”这个性质。而且最终的反证还是一种对角线证法。但总觉得这种“比所有原始递归函数都快”的证法有点奇怪？缺少通用性？