阿克曼函数

阿克曼函数是非原始递归函数的例子；它需要两个自然数作为输入值，输出一个自然数。它的输出值增长速度非常高。

1920年代后期，数学家大卫·希尔伯特的学生Gabriel Sudan和威廉·阿克曼，当时正研究计算的基础。Sudan发明了一个递归却非原始递归的苏丹函数。1928年，阿克曼又独立想出了另一个递归却非原始递归的函数。

他最初的念头是一个三个变量的函数A(,,)，使用康威链式箭号表示法是→→。阿克曼证明了它是递归函数。希尔伯特在猜想这个函数不是原始递归函数。阿克曼在证明了这点。

后来Rózsa Péter（英语：Rózsa Péter）和拉斐尔·米切尔·罗宾逊定义了一个类似的函数，但只用两个变量。

以下是阿克曼函数的伪代码：

 function ack(m, n)     while m ≠ 0         if n = 0             n := 1         else             n := ack(m, n-1)         m := m - 1     return n+1

Haskell 语言能生成更精确的定义:

 ack 0 n = n + 1 ack m 0 = ack (m - 1) 1 ack m n = ack (m - 1) (ack m (n - 1))

递归是有界的，因为在每次应用递归时，要么 递减，要么 保持不变而 递减。每次 达到零， 递减，所以 最终可以达到零。（较技术性的表达：在每种情况下，有序对(, )按字典次序递减，它保持了非负整数的良序关系）。但是，在 递减的时候， 的增加没有上界，而且增加的幅度比较大。

这个函数亦可用康威链式箭号表示法来作一个非递归性的定义：

即是

使用hyper运算符就是

使用高德纳箭号表示法则为

由于函数 () = (, )的增加速率非常快，因此其反函数−1则会以非常慢的速度增加。阿克曼反函数常用α表示。因为A(4, 4)的数量级约等于${\displaystyle 2^{2^{{10}^{19729}}}}$，α(n)均小于5。

阿克曼反函数会出现在一些算法的时间复杂度分析中，例如并查集或是Chazelle针对最小生成树的算法中。有时会使用一些阿克曼函数的变体，例如省略表达式中的-3等，但其增加的速率都相当快。

以下是一个两个输入值的阿克曼反函数，其中${\displaystyle \lfloor <!--\; \lfloor \; -->x\rfloor <!--\; \rfloor \; -->}$表示其运算的次数，而表示元素的个数。在最小生成树算法中，表示其边的个数，而表示其顶点的个数。

有些定义方式会用上述的定义略作修改，例如log₂ 改为，或是下取整函数改为上取整函数。

有些研究则是用上述的定义，但是令m为常数，因此只需要一个输入值。