阿克曼函数

在可计算性理论中，以 Wilhelm Ackermann 命名的阿克曼函数是非原始递归的总可计算函数的最简单和最早发现的示例之一。 所有原始递归函数都是全函数和可计算的，但阿克曼函数说明并非所有可计算全函数都是原始递归函数。 在阿克曼发表他的函数（具有三个非负整数参数）之后，许多作者对其进行了修改以适应各种目的，因此今天的阿克曼函数可能指的是原始函数的众多变体中的任何一个。

它的价值增长迅速，即使是小投入。 例如，A(4, 2) 是 19,729 位十进制数字的整数（相当于 265536−3，或 22222−3）。

在 20 年代后期，大卫希尔伯特的学生数学家加布里埃尔苏丹和威廉阿克曼正在研究计算的基础。 Sudan 和 Ackermann 都因发现了非原始递归的总可计算函数（在某些参考文献中简称为递归）而受到赞誉。 苏丹发表了鲜为人知的苏丹函数，不久之后，阿克曼在 1928 年独立发表了他的函数 φ {displaystyle varphi }（希腊字母 phi）。

（除了其作为完全可计算但非原始递归函数的历史角色外，阿克曼的原始函数被视为将基本算术运算扩展到求幂之外，尽管不如阿克曼的变体那样无缝 专门为此目的设计的函数——例如 Goodstein 的超操作序列。）

在 On the Infinite 中，David Hilbert 假设阿克曼函数不是原始递归，但实际上是 Hilbert 的私人秘书兼前学生 Ackermann 在他的论文 On Hilbert's Construction of the 实数。

Rózsa Péter 和 Raphael Robinson 后来开发了一个双变量版本的阿克曼函数，几乎成为所有作者的首选。

广义超操作序列，例如 G ( m , a , b ) = a [ m ] b {displaystyle G(m,a,b)=a[m]b} ，也是阿克曼函数的一个版本。

许多其他版本的阿克曼函数已被调查。

阿克曼的原始三参数函数 φ ( m , n , p ) {displaystyle varphi (m,n,p)} 对于非负整数