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