Ackermann's function is:

$A(0,y) = y + 1 $

$ A(x+1,0)= A(x,1)$

$ A(x+1,y+1)= A(x,A(x+1,y)$

which is a total computable function but not a primitive recursive one. Why is the following property valid?

$A(n,2)= 2n+3 ,\forall n>0$

Proving that $A(n,1)= n+2 ,\forall n>0\ $ is trivial, but with $n=2$ it gets a bit tricky.

My idea so far:

$A(2,n) = A(1,A(2,n-1))=A(1,A(1,A(2,n-2)))= \dots A(1,A(1,A(1,A(1\dots A(2,n-n)))))$ ,

which will give $A(2,0)= A(1,1)= A(0,A(1,0))= A(0,A(0,1)=A(0,2)=3$

and then start computing back all the way to $A(2,n)$. Alas, I cannot extract that $2n$ from this recursion.

Extra: is there any way to create a more general formula for $x = 1,2, \dots k $ for $A(k,n)$?


You do it by induction. $A(2,0)=A(1,1)=1+2=3=2\cdot 0 +3$ is the base case. Now assume $A(2,k)=2k+3$. Then $A(2,k+1)=A(1,A(2,k))=A(2,k)+2=2k+3+2=2(k+1)+3$ and we have proven for all $n, A(2,n)=2n+3.$ It is better to write this as $A(2,n)=2(n+3)-3$ to fit the pattern with higher first indices.

A similar induction works for any given value of the first index. We have $A(3,0)=A(2,1)=5=2^3-3$. We claim $A(3,n)=2^{n+3}-3.$ The base case fits. Then again assume $A(3,k)=2^{k+3}-3$. We have $A(3,k+1)=A(2,A(3,k))=2\cdot ((A(3,k)+3)-3=2\cdot(2^{k+3}-3)+6-3=2^{(k+1)+3}-3$

As the index gets higher we need another notation to express what is going on. The nicest version I know is Knuth's up-arrow notation. If I recall correctly,in terms of that, for $x \ge 3$ we have $A(x,y)=2\uparrow^{x-2}(y+3)-3.$ You can prove that by induction on $x$. The base case is $A(3,y)$ which we have shown works.

  • $\begingroup$ thank you!!! now i get it $\endgroup$ – Mario Zelic May 23 '18 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.