[科普中國]-阿克曼函數(shù)

阿克曼函數(shù)（Ackermann）是非原始遞歸函數(shù)的例子。它需要兩個自然數(shù)作為輸入值，輸出一個自然數(shù)。它的輸出值增長速度非?？?，僅是對于(4,3)的輸出已大得不能準(zhǔn)確計算。

歷史1920年代后期，數(shù)學(xué)家大衛(wèi)·希爾伯特的學(xué)生Gabriel Sudan和威廉·阿克曼，當(dāng)時正研究計算的基礎(chǔ)。Sudan發(fā)明了一個遞歸卻非原始遞歸的Sudan函數(shù)。1928年，阿克曼又獨立想出了另一個遞歸卻非原始遞歸的函數(shù)。[1]

他最初的念頭是一個三個變量的函數(shù)A(m,n,p)，使用康威鏈?zhǔn)郊柋硎痉ㄊ莔→n→p。阿克曼證明了它是遞歸函數(shù)。希爾伯特在On the Infinite猜想這個函數(shù)不是原始遞歸函數(shù)。阿克曼在On Hilbert's Construction of the Real Numbers證明了這點。

后來Rózsa Péter和拉斐爾·米切爾·羅賓遜定義了一個類似的函數(shù)，但只用兩個變量。1

定義Ackermann函數(shù)定義如下： 若m=0，返回n+1。

若m>0且n=0，返回Ackermann(m-1,1)。

若m>0且n>0，返回Ackermann(m-1,Ackermann(m,n-1))。2

意義從Ackermann函數(shù)的定義中可以看出，Ackermann函數(shù)可以看成關(guān)于n的一個函數(shù)序列，其中第0個函數(shù)返回n+1，而第m個函數(shù)則是將第m-1個函數(shù)對1迭代n+1遍。對較小的m，該函數(shù)為：

Ackermann(0,n)=n+1

Ackermann(1,n)=n+2

Ackermann(2,n)=2*n+3

Ackermann(3,n)=2^(n+3)-3

Ackermann(4,n)=2^2^2^……^2-3，乘冪中共有n+3個2。

當(dāng)m≥4，Ackermann函數(shù)的增長快得驚人。Ackermann(4,0)=13，Ackermann(4,1)=65533，Ackermann(4,2)=2^65536-3有19729位，而Ackermann(4,3)則即使是位數(shù)也不易估計。Ackermann(5,0)=65533，Ackermann(5,1)=Ackermann(4,65533)……2

反函數(shù)單變量反Ackermann函數(shù)（簡稱反Ackermann函數(shù)）α(x)定義為最大的整數(shù)m使得Ackermann(m,m)≤x。從上面的討論中可以看到，因為Ackermann函數(shù)的增長很快，所以其反函數(shù)α(x)的增長是非常慢的，對所有在實際問題中有意義的x，α(x)≤4，所以在算法時間復(fù)雜度分析等問題中，可以把α(x)看成常數(shù)。

α(x)出現(xiàn)在使用了按秩合并和路徑壓縮的并查集算法的時間復(fù)雜度中。1

計算代碼遞歸算法int ack(int m,int n){

while(m!=0){

if( n==0) n=1;

}else{

n=ack(m, n-1);

m--;

}

return n+1;

}

非遞歸算法一int Ackermann(int m,int n)

{

int akm[m][n];

int i,j;

memset(akm,o,sizeof(akm));

for(j=0;j