How to prove that calculating Ackermman function stops?

Question

Let $$\begin{eqnarray*} A(0,y) &=& y+1 \\ A(x+1,0) &=& A(x,1) \\ A(x+1,y+1) &=& A(x,A(x+1,y)) \end{eqnarray*}$$ be Ackermann function. How to prove by structural induction that calculating $A(n,m)$ for any natural $n,m$ stops?

Answer 1

HINT: It’s clear that it stops for all $A(0,n)$. Suppose that $m\in\Bbb N$, and it stops for all $A(k,n)$ such that $k\le m$. Show by induction on $n$ that it stops for all $A(m+1,n)$. In other words, you’re doing an induction on the second argument within an induction on the first argument.