历史

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

他最初的念头是一个三个变数的函数A( m , n , p )，使用康威链式箭号表示法是 m → n → p 。阿克曼证明了它是递归函数。希尔伯特在 On the Infinite 猜想这个函数不是原始递归函数。阿克曼在 On Hilbert"s Construction of the Real Numbers 证明了这点。

后来Rozsa Peter和Raphael Robinson定义了一个类似的函数，但只用两个变数。

定义

以下是阿克曼函数的虚拟码：

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

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

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

即是

使用hyper运算符就是

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

函数值表

反函数

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

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

以下是一个二个输入值的阿克曼反函数，其中 ⌊ ⌊ --> x ⌋ ⌋ --> {\displaystyle \lfloor x\rfloor } 为地板函数：

许多算法的复杂度分析会用到此函数，可以以此得到一个较好的时间上限。在并查集的数据结构中， m 表示其运算的次数，而 n 表示元素的个数。在最小生成树算法中， m 表示其边的个数，而 n 表示其顶点的个数。

有些定义方式会用上述的定义略作修改，例如log 2 n 改为 n ，或是地板函数改为天花板函数。

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

参见

迭代幂次

Busy beaver （ 英语 ： Busy beaver ）

引用

Wilhelm Ackermann, Zum Hilbertschen Aufbau der reelen Zahlen , Math. Annalen 99 (1928), pp. 118-133.

von Heijenoort.From Frege To Gödel, 1967. This is an invaluable reference in understanding the context of Ackermann"s paper On Hilbert’s Construction of the Real Numbers , containing his paper as well as Hilbert’s On The Infinite and Gödel’s two papers on the completeness and consistency of mathematics.

Raphael M. Robinson, Recursion and double recursion , Bull. Amer. Math. Soc., Vol. 54, pp. 987-993.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。