阿克曼函数

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

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

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

	若m=0
	若m>0且n=0
	若m>0且n>0

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

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

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

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

对于m>2，A(m, n) = (2 → (n+3) → (m - 2)) - 3。

即是

对于n>2，2 → n → m = A(m+2,n-3) + 3。

使用hyper运算符就是

A(m, n) = hyper(2, m, n + 3) - 3。

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

A(m, n) = 2↑^m-2(n+3) - 3。