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

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.

• By recurrence on the first parameter, you can show there is only one such function (You already did for x=0). To make a program without recursion, you'll need a stack and a while loop.
– Xoff
Dec 17, 2018 at 10:11

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}

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.