Thank you for your answer! When does a functional reject a PR function? It seems to me that your construction works for accepting, not for deciding properties (in the terminology of automata/language theory). In the first case (accepting) the convergence of $\Gamma^{\varphi_i}(0)\downarrow$ corresponds to acceptance, the divergence to rejection. But deciding a property can only be done by recursive functionals (output NO or YES). [By the way, in your construction of $A$ you use the terms ACCEPT and REJECT meaning "put in $A$" and "put out of $A$", respectively. Is it so?]

I don't completely understand your construction. First a minor point, in step 2 what is $\Gamma^\sigma_{i,s}$ (with the pair (i,s) as subscript)? I think you are diagonalizing against ALL Turing functionals $\Gamma_0$, $\Gamma_1$,... But some of these functionals (with some PR functions as oracles) must be partial recursive functions. And it is not decidable if, say, $\Gamma^\sigma_j(0)$ converges (given $j$ and $\sigma$). But the construction of $A$ seems to depend on this halting problems (step 2), and so $A$ does not seem to be recursive.

That's interesting. Let me just make a simple observation: if follows that we can compute, from the right to the left and in a primitive recursive fashion, the successive bits of Ack(x,y); however the whole value of Ack(x,y) can not be primitive recursively computed. This shows that Ack(x,y) is not primitive recursive only because it grows too fast. A similar argument uses Agraph(x,y,z): we can compute in succession A(x,y,0), A(x,y,1)... but there is no primitive recursive way of finding z such that A(x,y,z)=1.

Thanks for your observations! I was thinking in the version A(0,n)=n+1, A(m+1,0)=A(m,1), A(m+1,n+1)=A(m,A(m+1,n)), as used for instance in the wikipedia. I was interested in a version for which the function Abit(m,n,b), the bit b of A(m,n), is not PR.

To F. G. Dorais. 1. Yes, your interpretation is ok. 2. How can we bound the tables? Does for instance A(x-1,A(x,y-1))%m depend only on (x-1)%m and A(x,y-1)%m (the args mod m)? Or does it depend on the entire computation?

Very interesting. I couldn't yet look carefully at those papers, but correct me if I'm wrong: (1) the function which is total recursive and not PR is the complexity of a certain (verification) problem. (2) that function grows faster than any PR function - it is not "small".

Just a few comments. The function of the "comes along... function" is (or can be) then the Turing machine execution time. For the function $f$ mentioned in the question (top), the "fast growing function" is the simulation time of $\phi_i(i)$ as a function of $i$. This is a way to show that no PR function can simulate all PR functions; a similar diagonal argument applies to every class of total recursive functions whose elements (descriptions of functions) can be effectively enumerated. This condition does not apply to the class of ALL total recursive functions.