computability theory - Ackermann-related function

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