阿克曼函数

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

一般定义

定义

Robinson 的版本是最常被使用的阿克曼函数：

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

其他定义

（本节内容大部分来自 Googology Wiki。）

原始定义

$A(n,x,y)=\{\begin{array}{ll}x+1& ,n=0\\ \underset{y\text{ times}}{\underbrace{A(n-1,A(n-1,\cdots A(n-1,0,x)\cdots ,x),x)}}& ,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\text{and}y>1\\ A(x-1,A(x,y-1))& ,x>1\text{and}y>1\end{array}$

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

Buck 的定义

Buck 使用相同的基本递归定义一个相关函数：$F(x,y)=F(x-1,F(x,y-1))$

但边界值略有不同：

$\begin{array}{rlrl}F(0,y)& =& y+1& \\ F(1,0)& =& 2& \\ F(2,0)& =& 0& \\ F(x,0)& =& 1& \text{for }x=3,4,\cdots \end{array}$

这个函数递归得到：

$\begin{array}{rlr}F(1,y)& =& 2+y\\ F(2,y)& =& 2y\\ F(3,y)& =& 2^y\\ F(4,y)& =& 2\uparrow \uparrow y\end{array}$

F(4,n) 给出了序列 1, 2, 4, 16, 65536, 2⁶⁵⁵³⁶,... (OEIS A014221)；

F(n,n) 给出了序列 1, 3, 4, 8, 65536, $2\uparrow \uparrow 65536$,...(OEIS A001695)。

Goucher 的定义

A.P.Goucher 在其博客文章中提出了阿克曼函数的以下定义：

• $f_1(n)=n+2$
• $f_{m+1}(n)=f_m^n(2)$
• $A(n)=f_n(n)$

该文章描述了该函数的另一个变体，该变体与以下问题相关：

给定一排盒子，每个盒子中有若干硬币，我们可以选择一个盒子并按照以下规则之一进行操作：

1. 从该盒子中移除一枚硬币，并在第 n+1 个盒子中添加两枚硬币。
2. 从该盒子中移除一枚硬币，并反转第 n+1 和 n+2 个盒子中的硬币数量。

我们可以选择一种策略，即挑选盒子并应用相应的规则。考虑以下情况：除最右侧的盒子外，所有盒子均为空。此时，给定一排 n 个盒子，每个盒子中各有一枚硬币，$f(n)$ 表示最右侧盒子中可能出现的最大硬币数量。计算该函数的精确值可能颇具挑战，但显而易见的是 $f(1)=1$、$f(2)=3$ 和 $f(3)=7$。而证明 $f(4)=28$ 则稍显困难。

其他内容

定义在 R^* 上的阿克曼函数

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}$

阿克曼函数和阿克曼数

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

非原始递归的函数

阿克曼函数是一个良定义全函数的最简单例子，它是可计算的但不是原始递归的，这为 20 世纪初人们认为每个可计算函数也是原始递归的这一信念提供了反例。

阿克曼函数的逆函数

由 ${\lambda }_i(n)=\min \{j\in \mathbb{\mathbb{N}}|A(i,j)⩾n\}$ 定义的函数 $\lambda :{\mathbb{\mathbb{N}}}^2\to \mathbb{\mathbb{N}}(i,n)\mapsto {\lambda }_i(n)$（亦记为 $\alpha (i,n)$）被称为阿克曼函数的逆函数(inverse-Ackermann function)，尽管它并非非双射映射 $A:{\mathbb{\mathbb{N}}}^2\to \mathbb{\mathbb{N}}$ 本身的逆映射。由于 $A(m,n)$ 的增长速度相对较快，逆阿克曼函数因此呈现出极为缓慢的增长特性。有趣的是，该函数已在时间复杂度理论领域得到实际应用。

阿克曼函数的对角化

阿克曼函数让我有些困扰，因为它是一个二元函数，而我们更关注一元函数。显然，对于任意的 n，Ackermann(n,n) 应该有个特定的名称吧？比如 Knackered_Man(n) 或者 Ackermann(n,n)？或者简称 Gag(n)？另外，像+、*、^这样的进阶运算……它们在递进过程中会生成新的函数吗？这就是所谓的 tetration 和 quintation 的意思吗？感谢解答这些疑问 ——Alistair Cockburn

函数

$A(x)=A(x,x)$

（基于 Robinson 定义）是阿克曼函数的对角化，这个函数也被叫做 Gag 或 Knackeredman。这个名字来自 Alistair Cockburn，由于阿克曼函数与上箭头表示法的关系，

$A(x)=2{\uparrow }^{x-2}(x+3)-3$

。