Ackermann-related function

Question

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

Answer 1

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.

Answer 2

The key to do this is to realize the difference between computation and verification. Although computing value A(a,b) of the Ackermann function cannot be done primitive recursively, verifying whether a proposed number c is the correct value of A(a,b) can be done primitive recursively. (Note that computation and verification is also what distinguishes P and NP.)

In this case, the fact that this can be done hinges on the strong monotonicity properties of Ackermann's function. Indeed, if A(a,b) = c then all the previous values of A needed to compute A(a,b) are bounded by c. Therefore, the search for a valid computation verifying that A(a,b) = c can be bounded by a primitive recursive function B(a,b,c). Knowing this function B we can take a proposed value c for A(a,b), compute the bound B(a,b,c) and search up to this bound for a valid computation verifying that c is indeed equal to A(a,b). If no such computation is found we return 1, otherwise we return 0.

To make this a little more specific, let's say that computation for A(a,b) = c is a (coded) finite sequence of triples (a_i,b_i,c_i) which ends with the triple (a,b,c). Each such triple codes the fact that A(a_i,b_i) = c_i. The computation is valid when each such triple follows from previous triples and the rules for computing the Ackermann function. (Checking this is obviously primitive recursive.) For example a valid computation for A(1,1) = 3 is the sequence (0,1,2), (0,2,3), (1,0,2), (1,1,3).

Using the rules for computing Ackermann function and our specific method for coding finite sequences, we can compute an explicit bound B(a,b,c) on a valid computation verifying A(a,b) = c. The verification that B is primitive recursive should be straightforward if our coding of finite sequences is reasonable. Therefore, verifying A(a,b) = c can be done by a primitive recursive computation.

(The details of the last paragraph are best carried out in the privacy of one's office.)

Answer 3

Googling for "graph of the Ackermann function" gives this note by George Tourlakis, which proves both that the Ackermann function is not primitive recursive, and, at the end, that the graph is.