Ackermann Function primitive recursive

You seem to be conflating primitive recursive functions with total recursive functions. Actually, primitive recursive are a subset of total recursive functions. The hierarchy can be described informally as follows:

• Partial recursive functions are defined by an algorithm which only works on some inputs.
• Total recursive functions are defined by an algorithm which works on all inputs but can take an arbitrarily long time to compute.
• Primitive recursive functions are defined by an algorithm that completes in a knowable time (“not too long” for some theoretic definition of long).

More precisely (though I'll refer you to Wikipedia or some other reference for a complete definition), a primitive recursive function can be computed by a sequence of elementary computations where there is a way to bound the running time at every step. The only form of recursion allowed in the definition is primitive recursion, where a function calls itself on a smaller argument. All primitive recursions can be reduced to giving definitions for $f(0)$ (not involving $f$) and $f(n+1)$ as a function of $f(n)$ only.

General recursive definitions allow an extra operation: looking for the smallest $n$ that makes some property come true. In general, it's impossible to know how far you'll have to go to find such an $n$.

The definition of the Ackermann function contains the clause $A(m+1,n+1) = A(m, A(m+1, n))$. The “next” value of the function (going from $n$ to $n+1$) depends on calls with larger parameters (starting with $A(m+1,n)$). So the definition is not in primitive recursive form. It takes some work which I am not going to reproduce here, but you can show that there is no alternate presentation of the Ackermann function that uses only primitive recursion. Yet the function is well-defined, because computing $A(?,n)$ only requires computations of $A(?,n')$ with $n' < n$.

If you prefer a programming approach, recursive functions can be computed with dynamic memory allocation and while loops. Primitive recursive functions can be computed with only for loops, where the loop bound may be computed at run time but must be known when the loop starts.

Here's a proof showing why Ackermann's function is not primitive recursive.

The key to showing that A is not primitive recursive, is to find a properties shared by all primitive recursive functions, but not by A . One such property is in showing that A in some way ``grows'' faster than any primitive recursive function

Also, here's a proof showing that Ackermann's function is both a total function and a recursive function.

The intuitive reason for why it is not primitive recursive is that it is recursing on more than one parameters, the primitive recursive functions are defined by functions recursing on only one parameter.

It is more complicated to show that a function is not a primitive recursive because we have to prove than no primitive recursive function will compute the same function, i.e. the fact that the definition of Ackermann function is not explicitly primitive recursive doesn't mean that there is no primitive recursive way of computing the same function. And the easiest way to show this cannot happen (AFAIK) is to show that it grows faster than any primitive recursive function so it cannot be one of them.

There is a hierarchy for recursive functions using recursion similar to primitive recursion but with more parameters. IIRC, Ackermann function is in the second level (taking primitive recursive functions to be the first level), i.e. can be computed by recursion on two parameters.