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.

EDITAnd these guys (a lot more trustworthy), claim the opposite: ropas.snu.ac.kr/~gslee/Publi/ackermann_ramsey.pdf $\endgroup$typing the email right now$\endgroup$2more comments