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)$?

up vote 1 down vote accepted

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.

  • thank you!!! now i get it – Mario Zelic May 23 at 15:23

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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