Purely for my own amusement I've been playing around with the Ackermann function. The Ackermann function is a non primitive recursive function defined on non-negative integers by:
$A(m,n) = n+1$, if $m=0$
$A(m,n) = A(m-1,1)$, if $m>0$ and $n=0$
$A(m,n) = A(m-1,A(m,n-1))$, if $m>0$ and $n>0$
I'm not interested in values of the function itself, rather I'm interested in the number of recursions the function takes to arrive at a value. For example:
$A(1,2) = A(0,A(1,1)) = A(0,A(0,A(1,0))) = A(0,A(0,A(0,1))) = A(0,A(0,2)) = A(0,3) = 4$
That's 6 steps, so if we define $RA(m,n)$ as the number of recursions to calculate $A(m,n)$, then $RA(1,2) = 6$.
I made a short Excel macro to calculate $RA(m,n)$ for any given $m$ and $n$. The problem I have is that $RA(m,n)$ grows even faster than $A(m,n)$ and I quickly run out of stackspace. The table below shows $RA(m,n)$ for very small values of $m$ and $n$. The numbers shown for $RA(3,10)$ and $RA(4,1)$ are the number of steps before crashing!
A formula for $RA(1,n)$ is trivial, and it is relatively easy to see that $RA(2,n) = 5(n+1) + 4n(n+1)/2$.
So my questions: can anyone see an explicit formula for $RA(3,n)$? More generally, does a formula exist for $RA(m,n)$, in the same way that $A(m,n)$ can be expressed using Knuth arrows?
For the low values shown of $m$ and $n$, $RA(m,n)$ looks about order of magnitude larger than $A(m,n)$. Can we prove that $RA(m,n) > A(m,n)$ for all $m,n$. Intuitively, it should be.
For bonus points, can $RA(m,n)$ be expressed in terms of $A(m,n)$?
Best Answer
The function $RA(m,n)$ (as defined by the computation process described in the question description) satisfies the following conditions (where $A(m,n)$ is the standard Ackermann function): $$ RA(m,n)= \begin{cases} 1 & \text{for } m=0\\ 1 + RA(m-1, 1) & \text{for } m>0 \text{ and } n=0\\ 1 + RA(m, n-1) + RA(m-1, A(m, n-1)) & \text{for } m>0 \text{ and }n>0 \\ \end{cases} $$
First two cases are trivial: $A(0, n)$ is given directly, without recurring any further, and $A(m,0)$ is defined as $A(m-1,1)$, so we just need to perform a single additional recursive call.
The third case is the slightly tricky one: in order to evaluate $A(m-1,A(m,n-1))$, we first need to compute the value of $A(m,n-1)$, which takes $RA(m,n-1)$ steps. After that, we are computing $A(m-1,\cdot)$, where $\cdot$ is the just-computed value of $A(m,n-1)$ (i.e. it doesn't bring in any further recursive calls), which is represented by the last term.
It is now not too difficult to see that $RA(m,n)\geq A(m,n)$ for $m\geq 1$ ($m=0$ is a special case, since it involves no additional recursion).
We can also use the third line repeatedly until we reach $n=0$ and finish by applying the second one to obtain the following equality which expresses $RA(m,n)$ using just $RA(m-1,\cdot)$:
$$RA(m,n)=(n+1) + RA(m-1,1) + \sum_{k=0}^{n-1} RA(m-1,A(m,k))$$
Since $A(3,n)=2^{n+3}-3$ and we already know $RA(2,n)=2n^2+7n+5$, we can evaluate $RA(3,n)$ exactly as: $$RA(3,n) = 128\frac{4^n-1}{3} - 40\left(2^n-1\right) + 3n + 15$$
(the strange-looking terms are results of summing geometric progressions)
This subsequently allows us to reach a little bit further in the computations and find that $RA(4,1)=2862984010$ but beyond this point the numbers grow very fast. Furthermore, unlike the nice polynomials (for $m\leq 2$) and exponentials (for $m=3$), exponential towers and further hyperoperations which are lurking in $A(m,n)$ for $m>3$ do not play well with simple summation, so I doubt there would be any simple exact expression for $RA(m,n)$ with $m>3$.
Of course, this doesn't stop this function from having some explicit (and possibly even tight) bounds in terms of $A(m,n)$ or some similar function; I even have an idea of how such bounds might looks like; I will try to play with and update the answer if it yields anything interesting.