Explicit mu-recursive expression for Ackerman function

Question

Can you please point out how to build Ackerman function (actually I'm interested in a version proposed by Rózsa Péter and Raphael Robinson) via standard mu-recursive operators? I tried original papers by Péter and Robinson, but Péter's paper use a language different from English and Robinson's papers “Recursion and Double Recursion” and “Primitive Recursive Functions” also don't help: first of them seems more relevant, but is uses so called double recursion operator to define Ackerman function, so in this case explicit definition of the operator in mu-recursive terms is seeked.

Most closely to the answer goes P. Smith in “An introduction to Godel's theorems” (CUP, 2007) (29.4 The Ackermann-Peter function is μ-recursive), but he comes up with the following: “making the argument watertight is pretty tedious though not difficult. There’s nothing to be learnt from spelling out the details here: so we won’t.”

I also tried Rózsa Péter's book “Recursive functions” (1967, Academic press). There are plenty of variants for recursion operators given there. Usually one reduces to other. I believe that there is a type of recursion operator which fit for definition of Ackerman function and sequence of steps which reduce it to primitive redursion and minimisation operators, but I found myself unable to investigate the whole way down.

Answer 1

Breaking the Ackermann function all the way down to the elementary operators would really be quite lengthy, but here is a sketch:

Note that when computing $A(m,x)$ recursively, at any point of the computation you are dealing with an expression of the form $A(m_1,A(m_2,\dots,A(m_k,z)\dots)$. Given a bijective pairing function $p$ with inverse $(\pi_1,\pi_2)$, we can encode this state as $p(z,p(k,p(m_k,\dots,p(m_2,m_1)\dots)$ (just $p(z,0)$ in case $k=0$). We then can define the one-step evaluation function, given a state:

$e(p(z,0)) = p(z,0)$;

$e(p(z,p(k,p(0,c)))) = p(z+1,p(k-1,c))$;

$e(p(0,p(k,p(m+1,c)))) = p(1,p(k,p(m,c)))$;

$e(p(z+1,p(k,p(m+1,c)))) = p(z,p(k+1,p(m+1,p(m,c))))$.

You then get the n-step evaluation function using primitive recursion:

$E(0,m,x) = p(x,p(1,m))$ and $E(n+1,m,x) = e(E(n,m,x))$.

Finally, wrap $\mu$-recursion around $E$ to find the point where we get to a state of the form $p(z,0)$ - $z$ will be $A(m,x)$.

Answer 2

This is a variant of the idea posted by Kaveh, but I am posting anyway since it allows you to sweep many nasty details under the rug without actually doing any handwaving.

The key fact is that the graph of the Ackermann function is primitive recursive. It's not that hard to find a very crude primitive recursive bound $B(m,n,w)$ on the code for the table of Ackermann values needed to verify that $A(m,n) = w$. Don't try to get sharp bounds — the cruder the easier! Something like $B(m,n,w) = 2^{mw^w}$ should be good enough, but that depends on your choice of coding scheme. Since the verification of the table values can be described by a bounded formula, it is primitive recursive.

Once you have a primitive recursive definition for the graph $G(m,n,w)$ of the Ackermann function, simply define $A(m,n) = \mu w\,G(m,n,w)$.

Sadly, this strategy doesn't work for all functions defined by double (or multiple) recursion. The reason it works for the Ackermann function — as you will see when trying to figure out a good $B(m,n,w)$ — is that it grows very monotonically. For the general case, you must use Kaveh's idea and have $\mu$ look for the appropriate table of values. This is basically the same reason why the Kleene's Normal Form Theorem needs to do a projection after applying the $\mu$ operator.