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