阿克曼函数

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

历史

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

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

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

定义

$A(m,n)={\begin{cases}n+1\\A(m-1,1)\\A(m-1,A(m,n-1))\\\end{cases}}$	若m=0
	若m>0且n=0
	若m>0且n>0

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

 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))

递归是有界的，因为在每次应用递归时，要么 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。

函数值表

A(m, n) 的值

m\n	0	1	2	3	4	n
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2$
2	3	5	7	9	11	$2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13	65533	265536 − 3	A(3, 265536 − 3)	A(3, A(4, 3))	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\end{matrix}}$（n+3个数字2）
5	65533	A(4, 65533)	A(4, A(5, 1))	A(4, A(5, 2))	A(4, A(5, 3))
6	A(5, 1)	A(5, A(5, 1))	A(5, A(6, 1))	A(5, A(6, 2))	A(5, A(6, 3))

反函数

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

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

以下是一个两个输入值的阿克曼反函数，其中$\lfloor x\rfloor$为下取整函数：

$\alpha (m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}.$

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

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

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

参见

• 迭代幂次
• 忙碌的海狸

引用

• 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.

外部链接

• Erich Friedman's page on Ackermann at Stetson University
• Scott Aaronson, Who can name the biggest number? （页面存档备份，存于互联网档案馆） (1999)
• Some values of the Ackermann function （页面存档备份，存于互联网档案馆）.
• Example use of the Ackermann function as a benchmark （页面存档备份，存于互联网档案馆）. Note the huge number of function calls used in computing low values.
• Decimal expansion of A(4,2)
• Hyper-operations （页面存档备份，存于互联网档案馆） Posting on A New Kind of Science Forum discussing the arithmetic operators of the Ackermann function and their inverse operators with link to an extended article on the subject.
• Robert Munafo's Versions of Ackermann's Function describes several variations on the definition of A.
• Zach, Richard,
  "Hilbert's Program" （页面存档备份，存于互联网档案馆）, The Stanford Encyclopedia of Philosophy (Fall 2003 Edition), Edward N. Zalta (ed.)