While doing some research, I came up with a problem of proving that 


$ f(a,b,c)=\begin{cases}1 &\text{ if }A(a,b)=c\\ \\\\ 0 &\text{ otherwise }\end{cases} $


is primitively recursive ($A$ is the Ackermann's function).


Any references, ideas or proofs?


(This may not be a good MO question, but since the participants in problem-solving sites listed in MO posting FAQ failed to solve it - I posted it there before - I was hoping for a solution here.)



Ackermann-related function
Here's a sketch of an argument which I expect could be made into a proof.


The key fact is that the Ackermann function fails to be primitive recursive only because it grows so quickly. More formally:


**Claim**. There exists a Turing machine T and a primitive recursive function f(a, b, c) (which is an increasing function of c) such that on input (a, b), T computes A(a, b) in at most f(a, b, A(a, b)) steps.


"Proof". Starting with the expression "A(a, b)", repeatedly expand terms of the form A(x, y) with the recursive definition, but do not simplify any of the resulting additions. The length of the string increases at every step, if we agree that the symbol "+" is "longer" than "A". The resulting string is a formal sum of positive integers, so its length is bounded by (a multiple of) A(a, b); hence the number of steps is also bounded above in terms of A(a, b), and we may perform each step in time polynomial in A(a, b).


Now, we can simulate a given Turing machine for a fixed number of steps using a primitive recursive function. We may therefore compute the graph of the Ackermann function with a primitive recursive function as follows: Given a, b, c,


* Compute f(a, b, c).
* Simulate the Turing machine T on input (a, b) for f(a, b, c) steps.
* If T has halted, then return whether c is equal to the output of T. If T has not halted, then c < A(a, b) so return false.


