阿克曼函数

阿克曼函数(Ackermann function)是由德国数学家 Wilhelm Ackermann 创造的非原始递归函数，后来由 Rozsa Peter 和 Raphael M. Robinson 简化。阿克曼函数有多种不同的版本。

定义

Robinson 的版本是最常被使用的 Ackermann 函数：

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

在这个定义下，$A(x,y)=2{\uparrow }^{x-2}(y+3)-3$，它的 FGH 增长率约为 $\omega$。

示例

$\begin{array}{lll}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+(n+3)-3$
2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13	65533	265536 – 3	$2^{2^{65536}}-3$	$2^{2^{2^{65536}}}-3$	$=2\uparrow \uparrow (n+3)-3$
5	65533	$2\uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow (n+3)-3$
6	$2\uparrow \uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow \uparrow (n+3)-3$
m	$(2{\uparrow }^{m-2}3)-3$	$(2{\uparrow }^{m-2}4)-3$	$(2{\uparrow }^{m-2}5)-3$	$(2{\uparrow }^{m-2}6)-3$	$(2{\uparrow }^{m-2}7)-3$	$(2{\uparrow }^{m-2}(n+3))-3$

其他定义

原始定义

$A(n,x,y)=\{\begin{array}{ll}x+y& ,n=0\\ \underset{y\text{ times}}{\underbrace{A(n-1,A(\cdots (A(n-1,x))\cdots ))}}& ,n\ne 0\end{array}$

它可以用上箭头表示法表示为 $A(n,x,y)=x{\uparrow }^{n-2}y$，但是在它被定义前上箭头表示法还未被发明。它是根据高阶原始递归（即函数上的原始递归）定义的。

Friedman 的定义

$A(x,y)=\{\begin{array}{ll}2& ,y=1\\ 2y& ,x=1\wedge y>1\\ A(x-1,A(x,y-1))& ,x>1\wedge y>1\end{array}$

在这个定义下，$A(x,y)=2{\uparrow }^{x-1}y$。

其他内容

定义在 R^* 上的 Ackermann 函数

CompactStar 的定义：

$A(x,y)=\{\begin{array}{ll}x+y+1& ,x<1\\ A(x-1,y\cdot A(x-1,1)-y+1)& ,x⩾1\wedge y<1\\ A(x-1,A(x,y-1))& ,x⩾1\wedge y⩾1\end{array}$

Ackermann 函数和 Ackermann 数

数列 $A_n=A(n+2,n,n)$（使用原始定义）被称为 Ackermann 数，这里 $A_n=n{\uparrow }^{n}n$。