proof that Ackermannfunction is uniquely defined and finding algorithm without recursions to calculate its values

Question

my question is involving the Ackermannfunction. Let's call a function $a: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ "Ackermannfunktion", if for all $x,y \in \mathbb{N}$ the following conditions are fulfilled:
1) a(0,y) = y+1 2) a(x+1,0) = a(x,1) 3) a(x+1, y+1) = a(x, a(x+1, y))

Now I have to proof that there exists a) at least one and b) at most one such function. c) write a programme (or describe an algorithm) without recursive calls that for every input (x,y) calculates a(x,y). d) Then calculate or describe a(4,2018).

I am not sure, what in a) is to do. Do you know what is meant? For b) I tried with functions A and B, that fulfill all three requirements, to prove that it's (A-B)(x,y) = 0 for every input (x,y), but I didn't manage to do so (I only managed for the input (0,y)). In c) I have no clue how to approach it. d) I found on the internet how a(4,y) looks like, so I could write down the solution, but I don't know how you get to the expression of a(4,y).

I'd appreciate your help on this and am looking forward to your replies.

Answer 1

Proving uniqueness is pretty straightforward via two layers of induction. To give you some pointers:

$a(0,y)$ is uniquely defined.

If $a(X,y)$ is uniquely defined for some fixed $X$ and all $y$, then:

• $a(X+1,0)$ is uniquely defined.

• If $a(X+1,Y)$ is uniquely defined, then $a(X+1,Y+1)$ is uniquely defined

$\implies a(X+1,y)$ is uniquely defined for that $X$ and all $y$.

To avoid recursive calls, notice how this function expands according to your rules. Take $A(6,3)$ for example:

$$\begin{align}A(6,3)&=A(5,A(6,2))\\&=A(5,A(5,A(6,1)))\\&=A(5,A(5,A(5,A(6,0))))\\&=\underbrace{A(5,A(5,A(5,A(5,}_{3+1}1))))\end{align}$$

In general,

$$A(x+1,y)=\underbrace{A(x,\dots A(x,}_{y+1}1)\dots)$$

which allows you to avoid a lot of recursion via loops. You can keep track of which $x$'s you have separately as well, to avoid ever calling the function again, and basically repeatedly expand based on the "most recent" $x$ value.

For example, if you wanted to calculate $A(6,3)$, you'd start by making $4$ copies of $5$ evaluated at $1$. Then you'd have $3$ copies of $5$ followed by $2$ copies of $4$ evaluated at $1$. Then you'd have $3$ copies of $5$ followed by $1$ copy of $4$ followed by $2$ copies of $3$ evaluated at $1$. etc. Visually:

$$\begin{align}A(6,3)&=\underbrace{A(5,A(5,A(5,A(5,}_41))))\\&=\underbrace{A(5,A(5,A(5,A(5,}_3\underbrace{A(4,A(4,}_21))))))))\\&=\underbrace{A(5,A(5,A(5,A(5,}_3\underbrace{A(4,}_1\underbrace{A(3,A(3,}_21))))))))\\&=\dots\end{align}$$

Answer 2

If I recall correctly, the "closed form" of the Ackermann function I knew was $$A(x,y)=2\uparrow^{y-3}x+3$$ where the uparrow is Knuth's and the power is the number of uparrows. I am not sure calculating this is without recursive calls. It doesn't call the routine to compute any other value, but unpacking the uparrows is a big job. There are several different Ackermann functions out there, so your closed form may differ in detail. I was able to prove mine by induction.