Ack(4,4)等于多少?

Question

Ack(4,4)等于多少?

Answer 1

从Ackermann函数的定义中可以看出,Ackermann函数可以看成关于n的一个函数序列,其中第0个函数返回n+1,而第m个函数则是将第m-1个函数对1迭代n+1遍.对较小的m,该函数为： 


　　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.
 
       当m≥4,Ackermann函数的增长快得惊人.Ackermann(4,0)=13,Ackermann(4,1)=65533,Ackermann(4,2)=2^65536-3有19729位,而Ackermann(4,3)则即使是位数也不易估计.
因此 Ack(4,4)= 2^2^2^2^2^2^2-3=18446744073709551613