# 阿克曼函式

## 歷史

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

## 定義

 ${\displaystyle 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))


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 ${\displaystyle n+1}$
1 2 3 4 5 6 ${\displaystyle n+2}$
2 3 5 7 9 11 ${\displaystyle 2\cdot (n+3)-3}$
3 5 13 29 61 125 ${\displaystyle 2^{(n+3)}-3}$
4 13 65533 265536 − 3 A(3, 265536 − 3) A(3, A(4, 3)) ${\displaystyle {\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))

## 反函式

${\displaystyle \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’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.