8
$\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, 2017 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, 2017 at 4:36

3 Answers 3

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, 2017 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, 2017 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$
1
  • $\begingroup$ So y ticks are 0, 2, 4, 6, 8, ... From n = 1 to 10 the # function calls are [106, 541, 2432, 10307, 42438, 172233, 693964, 2785999, 11164370, 44698325] (2) ln 541 = 6.29, (6) ln 172233 = 12.05, (7) ln 693964 = 13.45 $\endgroup$ Mar 14, 2023 at 11:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .