阿克曼函数

阿克曼函数(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}$

函数值表

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))