阿克曼函數

歷史

1920年代後期，數學家大衛·希爾伯特的學生Gabriel Sudan和威廉·阿克曼，當時正研究計算的基礎。Sudan發明了一個遞歸卻非原始遞歸的Sudan函數。1928年，阿克曼又獨立想出了另一個遞歸卻非原始遞歸的函數。[1]

定義

 $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


 ack 0 n = n + 1
ack m 0 = ack (m - 1) 1
ack m n = ack (m - 1) (ack m (n - 1))


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

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

函數值表

A(mn) 的值
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 \\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))

反函數

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

引用

• 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’sConstruction of the Real Numbers, containing his paper as well as Hilbert’sOn The Infinite and Gödel’stwo papers on the completeness and consistency of mathematics.
• Raphael M. Robinson, Recursion and double recursion, Bull. Amer. Math. Soc., Vol. 54, pp. 987-993.