0
$\begingroup$

I have trouble with a question i need to use the function of Ackermann, I need to show that Ack(2,3) = 9.

A(2,3) A(1,A(2,2)) A(1,A(1,A(2,1))) A(1,A(1,A(1,A(2,0)))) A(1,A(1,A(1,A(1,1))))) A(1,A(1,A(1,A(0,A(1,0)))))) A(1,A(1,A(1,A(0,A(0,1)))))) A(1,A(1,A(1,A(0,2)))) A(1,A(1,A(1,3))) A(1,A(1,A(0,A(1,2))) A(1,A(1,A(0,A(0,A(1,1))))) A(1,A(1,A(0,A(0,A(0,A(1,0)))))) A(1,A(1,A(0,A(0,A(0,A(0,1)))))) A(1,A(1,A(0,A(0,A(0,2))))) A(1,A(1,A(0,A(0,3)))) A(1,A(1,A(0,4))) A(1,A(1,4)) A(1,A(0,A(1,3))) A(1,A(0,A(0,A(1,2)))) A(1,A(0,A(0,A(0,A(1,1))))) A(1,A(0,A(0,A(0,A(0,A(1,0)))))) A(1,A(0,A(0,A(0,A(0,A(0,1)))))) A(1,A(0,A(0,A(0,A(0,2))))) A(1,A(0,A(0,A(0,3)))) A(1,A(0,A(0,4))) A(1,A(0,5)) A(1,6) A(0,A(1,5)) A(0,A(0,A(1,4))) A(0,A(0,A(0,A(1,3)))) A(0,A(0,A(0,A(0,A(1,2))))) A(0,A(0,A(0,A(0,A(0,A(1,1)))))) A(0,A(0,A(0,A(0,A(0,A(0,A(1,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,2)))))) A(0,A(0,A(0,A(0,A(0,3))))) A(0,A(0,A(0,A(0,4)))) A(0,A(0,A(0,5))) A(0,A(0,6)) A(0,7) A=8 

Where did I go wrong? If anyone could find my mistake i'd be thankful for your help!

Thanks!

3 Answers 3

5

Where you simplify $A(1,A(1,A(0,4)))$ to $A(1,A(1,4))$. $A(0,4)$ is $5$. By the way, Wolfram Alpha can show you all the steps.

  • 0
    Thanks alot for your help! Also thanks for the Wolfram Alpha tip.2012-01-12
2

The 17th line appears wrong $A(1,A(1,4))$ should be $A(1,A(1,5))$ since $A(0,4)$ is $5$.

2

Its not too hard to prove by induction that

$A(0,n)=n+1\implies A(1,n)=n+2\\\implies A(2,n)=2n+3$

Directly, one can see that:

$A(1,0)=A(0,1)=2=0+2~\color{green}\checkmark$

$A(2,0)=A(1,1)=A(0,A(1,0))=A(0,A(0,1))=3=2(0)+3~\color{green}\checkmark$

Now the induction steps:

$A(1,n+1)=A(0,A(1,n))=A(0,n+2)=(n+1)+2~\color{green}\checkmark$

$A(2,n+1)=A(1,A(2,n))=A(1,2n+3)=(2n+3)+2=2(n+1)+3~\color{green}\checkmark$

And so it follows swiftly that

$A(2,3)=2(3)+3=6+3=9$