7
$\begingroup$

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!

enter image description here

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)$?

$\endgroup$
2
  • $\begingroup$ I find your call expression misleading in terms of this kind of counting. It should be $A(1,2)=A(0,A(1,1))=1+A(1,1)=1+A(0,A(1,0))=1+1+A(1,0)=2+(1+1)=4$. This shows when an A can be removed due to the first argument being zero more explicitly which is key to computing RA. (In particular, the first time an A is removed will always be after m steps.) $\endgroup$ – Ian Nov 11 '17 at 6:59
  • $\begingroup$ Hi Ian, I've used the calculations for $A(1,2)$ exactly as it appears on Wikipedia. Yours makes sense too. $\endgroup$ – Moriarty Nov 16 '17 at 4:36
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Wow. Thank you, that's very thorough. If you travel any further in your 'playing' I'd love to hear your results. $\endgroup$ – Moriarty Dec 5 '17 at 0:27
2
$\begingroup$

According to the German Wikipedia page about the Ackermann function, what you call $RA(3,n)$ can be expressed as $RA(3,n)=A(3,n)+12^n-2$. Unfortunately, there are no links given.

However, I once read an old paper about this function which gave some good insight into the computations involved to find the number of calls needed to compute $A(m,n)$ (see "The Ackermann function: a theoretical, computational, and formula manipulative study" by Yngve Sundblad). The author does not give a general expression for $RA(m,n)$, as "it is difficult to give [one]". I think this paper can be found online.

$\endgroup$
1
  • 1
    $\begingroup$ Hi ADG, thanks for the reply. But unfortunately it doesn't seem to give the right answer as the formula you've given for $RA(3,2) = A(3,2) + 12^2 -2 = 29 + 144 - 2 = 171$, not the $541$ I'm counting. It can't be some sort of simplification to the calculation process either, as my $RA(3,9)$ is much smaller than the one provided by your formula. I will look up the paper you suggested, so thank you for that pointer. $\endgroup$ – Moriarty Nov 16 '17 at 4:47
1
$\begingroup$

ln RA(3,n) vs n

If you run a fit of ln RA(m=3, n) vs n, you obtain slope of 1.5082 with intercept of 3.0792 with $R^2$ of 0.9971 Looks like the relationship is approximately 21.7*exp(1.5n)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.