阿克曼函數

维基百科，自由的百科全书

阿克曼函數是非原始递归函数的例子；它需要兩個自然數作為輸入值，輸出一個自然數。它的輸出值增長速度非常高，僅是(4,3)的輸出已大得不能準確計算。

[编辑] 歷史

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定義了一個類似的函數，但只用兩個變數。

[编辑] 定義

$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) 的值
m\n	0	1	2	3	4	n
0	1	2	3	4	5	$n + 1$
1	2	3	4	5	6	$2 + (n + 3) - 3$
2	3	5	7	9	11	$2\cdot(n + 3)-3$
3	5	13	29	61	125	$2 (n + 3) - 3$
4	13	65533	2⁶⁵⁵³⁶ − 3	A(3, 2⁶⁵⁵³⁶ − 3)	A(3, A(4, 3))	$\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\mbox{ + 3 twos}\end{matrix}$
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))

[编辑] 参见

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

[编辑] 外部链接

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