先上維基百科： 維基百科：阿克曼函數

http://zh.wikipedia.org/wiki/%E9%98%BF%E5%85%8B%E6%9B%BC%E5%87%BD%E6%95%B8

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

1920年代后期，數學家大衛·希爾伯特的學生Gabriel Sudan和威廉·阿克曼，當時正研究計算的基礎。Sudan發明了一個遞歸卻非原始遞歸的Sudan函數。1928年，阿克曼又獨立想出了另一個遞歸卻非原始遞歸的函數。他最初的念頭是一個三個變量的函數A(m,n,p)，使用康威鏈式箭號表示法是m→n→p。阿克曼證明了它是遞歸函數。希爾伯特在On the Infinite猜想這個函數不是原始遞歸。阿克曼在On Hilbert’s Construction of the Real Numbers證明了這點。后來Rozsa Peter和Raphael Robinson定義了一個類似的函數，但只用兩個變量。

已知Ackerman函數akm(m,n)定義如下： 當m=0時: akm(m,n) = n + 1; 當m!=0, n=0時: akm(m,n) = akm(m-1, 1); 當m!=0, n!=0時: akm(m,n) = akm(m-1, akm(m, n-1));

Scheme 實現如下：

運行結果如下： 計算(A 4 3)的時候 程序就已經死了。只有中斷。

當計算(A 1 10)時過程如下： (A 1 10) (A 0 (A 1 9)) (A 0 (A 0 (A 1 8) ………… (A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0 1)))))))))) (A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0 2))))))))) (A 0(A 0(A 0(A 0(A 0(A 0(A 0(A 0 4)))))))) …………. (A 0 2^9) 2^10 = 1024 此過程中調用了 A 十次。 當計算(A 2 4)時計算過程如下： (A 2 4) (A 1 (A 2 3)) (A 1 (A 1 (A 2 2))) (A 1 (A 1 (A 1 (A 2 1)))) (A 1 (A 1 (A 1 2))) (A 1 (A 1 (A 0 (A 1 1)))) (A 1 (A 1 (A 0 2))) (A 1 (A 1 4)) ……4次調用 (A 1 16) ……16次調用 2 ^16 = 65536 經過了20次調用

(A 3 3) (A 2 (A 3 2)) (A 2 (A 2 (A 3 1))) (A 2 (A 2 2)) (A 2(A 1 (A 2 1))) …… (A 2 4) …… 2 ^16 up主已經無法計算調用了多少次這個函數類了 - -

所以最后結論可以做出來了：

(define ( f n) (A 0 n)) 計算的是 2n (define (g n) (A 1 n)) 計算的是2^n (define (h n) (A 2 n)) 計算的是((….(((2^2)^2)^2)….)^2) n層嵌套。