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.
Best Answer
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
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.