Dtyjlui

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.

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,}_3underbrace{A(4,A(4,}_21))))))))\&=underbrace{A(5,A(5,A(5,A(5,}_3underbrace{A(4,}_1underbrace{A(3,A(3,}_21))))))))\&=dotsend{align}$$

If I recall correctly, the "closed form" of the Ackermann function I knew was
$$A(x,y)=2uparrow^{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.