Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I wanted to put this originally on math.stackexchange, since I considered it to be a straightforward question and probably a fairly known fact. After I failed to solve the problem, I browsed through literature and what a surprise - two books claim it is primitive recursive, one resource claims it isn't, and neither one gives proof or reference. One paper also claims that inverse Ackermann function is slower than any primitive recursive function. If it were primitive recursive, I don't see why would that hold.

Now, my questions would be: which one is right - $Ack^{-1}$ is/isn't primitive recursive, and is/isn't slower than any primitive recursive function.

If it's a bad MO question, I'll migrate it to M.SE, no problem.

share|improve this question
5  
Seems like a very nice question... –  Igor Rivin Sep 21 '11 at 9:08
add comment

3 Answers

up vote 24 down vote accepted

The inverse Ackermann function is primitive recursive.

One way to see this is to use the fact that a function $f$ is primitive recursive when and only when

  1. the graph of $f$ is primitive recursive, and
  2. $f$ is bounded above by some primitive recursive function.

The graph of the Ackermann function is primitive recursive, i.e. the characteristic function of the set $\lbrace \langle x, y, z \rangle : z = A(x,y)\rbrace$ is primitive recursive. This is because checking that $A(x,y) = z$ is easy once $x, y, z$ are given. One can always construct a table of all previous values of $A$ used to justify that $A(x,y) = z$. If $z$ is indeed the correct answer, then the code for this table is not much bigger than $\langle x, y, z\rangle$ (smaller than $17^{17^{x+y+z}}$, for example). So, given a proposed triple $\langle x, y, z \rangle$, we can search for the relevant table and determine whether or not $A(x,y) = z$ is true in a primitive recursive fashion. Of course, the Ackermann function is not bounded above by a primitive recursive function, but that is the only thing that goes wrong.

Since the graph of the Ackermann function is primitive recursive, then so is the graph of the inverse Ackermann function $Ack^{-1}(z) = \max\lbrace x : A(x,x) \leq z\rbrace$. Moreover, the growth rate of $Ack^{-1}$ is bounded by some primitive recursive function (e.g. the identity function). It follows that $Ack^{-1}$ is indeed primitive recursive.

share|improve this answer
2  
The inverse of Ackermann function is not only primitive recursive, but also computationally easy (polynomial time), by the same argument. –  Emil Jeřábek Sep 21 '11 at 12:43
1  
Year and a half ago I asked for a proof that graph of Ackermann function is primitive recursive (mathoverflow.net/questions/19732/ackermann-related-function), but I failed to notice that this fact leads to answer I needed in this case. Thank you! –  Harun Šiljak Sep 21 '11 at 13:28
    
Just to add a little question there: $f$ is PR iff graph is PR and $f$ is bounded above by a PR. Ackermann function itself would be a nice example that condition 1. is not enough, but what would be a good example that 2. is not enough either, if we consider recursive functions (i.e. what would be a nice simple example of recursive, but not primitive recursive function bounded by a PR?). I like to remember counterexamples with theorems, that's why I'm asking this. –  Harun Šiljak Sep 21 '11 at 14:50
5  
The characteristic function of any recursive but not primitive recursive predicate will do, as it is bounded by constant 1. –  Emil Jeřábek Sep 21 '11 at 15:30
    
Exactly the same example I thought of later (it was just a problem I couldn't remember an example of such a predicate), thank you! –  Harun Šiljak Sep 21 '11 at 16:41
add comment

Maybe the following is of interest.

There is a pointer in the literature provided by Soare's book on r.e. degrees. In an exercise one should show that the bijective primitive recursive functions do not form a group. In rough terms the hint suggests that the inverse of the Ackermann function has no prim rec inverse.

share|improve this answer
1  
Hi Andreas! Welcome to MO! –  François G. Dorais Sep 23 '11 at 21:45
add comment

In this discussion

http://math.stackexchange.com/questions/31294/growth-rate-of-primitive-and-mu-recursive-functions

The last comment states that inverse Ackermann is NOT primitive recursive, but I have no idea why that's true, but maybe you can follow-up...

EDIT And these guys (a lot more trustworthy), claim the opposite:

http://ropas.snu.ac.kr/~gslee/Publi/ackermann_ramsey.pdf

share|improve this answer
    
Actually that answer was the resource I had in mind while writing 'one resource claims it isn't'. I wanted to bump that topic, but decided to open a new one instead. –  Harun Šiljak Sep 21 '11 at 9:16
1  
Why don't you just write to the guy and ask? –  Igor Rivin Sep 21 '11 at 9:29
1  
Good idea! typing the email right now –  Harun Šiljak Sep 21 '11 at 9:32
1  
Let us know what he says, it's an interesting question... –  Igor Rivin Sep 21 '11 at 9:33
add comment

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.