Background

Description

函数-阿克曼函数（Ackermann）

在递归函数论和涉及集合的并的某些算法的复杂性研究中，有一个起重要作用的递归函数——阿克曼（Ackermann）函数,该函数是由希尔伯特的学生，德国著名数学家威尔海姆·阿克曼于1928年发现的。这是一个图灵机可计算的，但不是原始递归的函数。下面，我们介绍这个经典的递归函数，并给出其相应的计算过程。

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

在 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} ，也是阿克曼函数的一个版本。

Format

Input

Output

Samples

1
2

4

3
3

61

Limitation

1s, 1024KiB for each test case.