阿克曼函数

阿克曼函数(Ackermann function)是由德国数学家威廉·阿克曼(Wilhelm Ackermann)创造的非原始递归函数。

定义

$A(m,n)=\{\begin{array}{ll}n+1& ,m=0\\ A(m-1,1)& ,m>0\text{and}n=0\\ A(m-1,A(m,n-1))& ,m>0\text{and}n>0\end{array}$

示例

$\begin{array}{ccl}A(2,2)& =& A(1,A(2,1))\\ & =& A(1,A(1,A(2,0)))& & \\ & =& A(1,A(1,A(1,1)))\\ & =& A(1,A(1,A(0,A(1,0))))\\ & =& A(1,A(1,A(0,A(0,1))))\\ & =& A(1,A(1,A(0,2)))\\ & =& A(1,A(1,3))\\ & =& A(1,A(0,A(1,2)))\\ & =& A(1,A(0,A(0,A(1,1))))\\ & =& A(1,A(0,A(0,A(0,A(1,0)))))\\ & =& A(1,A(0,A(0,A(0,A(0,1)))))\\ & =& A(1,A(0,A(0,A(0,2))))\\ & =& A(1,A(0,A(0,3)))\\ & =& A(1,A(0,4))\\ & =& A(1,5)\\ & =& A(0,A(1,4))\\ & =& A(0,A(0,A(1,3)))\\ & =& A(0,A(0,A(0,A(1,2))))\\ & =& A(0,A(0,A(0,A(0,A(1,1)))))\\ & =& A(0,A(0,A(0,A(0,A(0,A(1,0))))))\\ & =& A(0,A(0,A(0,A(0,A(0,A(0,1))))))\\ & =& A(0,A(0,A(0,A(0,A(0,2)))))\\ & =& A(0,A(0,A(0,A(0,3))))\\ & =& A(0,A(0,A(0,4)))\\ & =& A(0,A(0,5))\\ & =& A(0,6)\\ & =& 7\end{array}$

函数值表

A(m, n) 的值

m\n	0	1	2	3	4	n
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2$
2	3	5	7	9	11	$2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13	65533	265536 − 3	A(3, 265536 − 3)	A(3, A(4, 3))	$\begin{array}{c}\underbrace{{2^2}^{{\cdot }^{{\cdot }^{{\cdot }^2}}}}-3\end{array}$（n+3个2）
5	65533	A(4, 65533)	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))
6	A(5, 1)	A(5, A(5, 1))	A(5, A(6, 1))	A(5, A(6, 2))	A(5, A(6, 3))

小贴士

阿克曼函数的FGH增长率约为$\omega$。