Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Actually this is not as hard as it may seem at first. The trick is to let the $\mu$ operator search for a computation of the Ackerman function, i.e. the table of values up to the input, and then check that the table follows the definition of the function. What is needed is encoding/decoding finite sequences, and checking the table. Encoding/decoding are explicitly defined in many textbooks, the checking can be done by a bounded universal quantifier over a simple relation between the entries of the table. The bounded universal quantifier can be expressed as bounded multiplication, –  Kaveh Jun 8 '11 at 3:36
    
and an explicit definition of bounded multiplication in terms of $\mu$-recursion can also be found in textbooks. –  Kaveh Jun 8 '11 at 3:37
    
@Kaveh yes, the same idea implemented in P. Smith's “An introduction to Godel's theorems”. Encodings and application of minimisation operator are given there. The tricky part is how to generate the “table” as you name it. Smith skiped it. So it seems that I'll have to think on it harder instead of waiting for solutions here ;) At least thanks for your approval of the general approach. –  Artem Pelenitsyn Jun 8 '11 at 9:55
    
The table is just a finite sequence where the entries are indexed by the result of a pairing function. $\mu c: \forall x<Len(c) \forall y,z<x , x=<y,z> \to c_{<y,z>} = R(c,x,y)$ where $R(c,x,y)$ is the rhs of the equation for $Ack(x,y)$. –  Kaveh Jun 8 '11 at 16:14

2 Answers 2

up vote 9 down vote accepted

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

share|improve this answer
    
Thanks! One more question (maybe quite naive, sorry): pattern-matching-like definitions (f(0) = ..., f(n+1) = ...) used widely, but I doubt they are really alowed by the definition of mu-recursive function. Are they? –  Artem Pelenitsyn Jun 8 '11 at 18:17
    
This kind of case distinction (for example, defining $f(x,y)$ by $f(0,y)=g(y)$ and $f(x+1,y) = h(x,y)$) is just a special case of primitive recursion that doesn't actually use the previous value. In the computation of $A(x,y)$, the you would additionally use auxiliary functions and the inverses $\pi_1,\pi_2$ quite a bit if you wanted to break this down to the basic set of operations. –  Klaus Draeger Jun 9 '11 at 12:01
    
For example, you could translate the definition of $e$ as $e(s)=f_1(\pi_1(s),\pi_2(s))$, where $f_1(z,0)=p(z,0)$ and $f_1(z,m+1)=f_2(z,\pi_1(m+1),\pi_2(m+1))$, where $f_2\dots$ you get the idea. –  Klaus Draeger Jun 9 '11 at 12:06

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.

share|improve this answer
1  
Hi François. It's nice to see you on cstheory. –  Kaveh Jun 9 '11 at 13:13
    
Hi Kaveh. Nice to finally get to answer something here! –  François G. Dorais Jun 10 '11 at 0:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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