Explaining the Ackermann function as A: $\mathbb N \times \mathbb N \rightarrow \mathbb N$

348 Views Asked by At

We have the following variation of the Ackermann function: $$A(0,m) = m+1$$ $$A(n,0) = \begin{cases}1, & \text{if } n=0 \\ 2, & \text{if } n=1 \\ 0, & \text{if }n=2 \\ 1, & \text{if }n\gt 2\end{cases}$$ $$A(n+1,m+1) = A(n, A(n+1,m))$$

The question asks, "Explain why the previous equations do indeed define a function $A: \mathbb N \times \mathbb N \rightarrow \mathbb N$."

I understand how the function works - that is, I can describe what happens to an arbitrary input. But I don't fully understand what this question is asking. Am I meant to explain why a single input will never produce more than one output, and that the function is closed under the natural numbers? If so, how do I argue this without simply describing what the function is doing?