What is primitive recursive class and non primitive recursive class

Question

How ackermann is an non primitive recursive class

Answer 1

Looking at ackermann:

A(0, y) = y+1
A(x, 0) = A(x-1, 1)
A(x, y) = A(x-1, A(x, y-1))

You see that the second parameter grows larger on the bottom right there.

Looking at the primitive recursion function:

R[g,h](0, y) = g(y)
R[g,h](x, y) = h(R[g,h](x-1, y), x-1, y)

We would obviously pick `g(y) = y+1` so we get the first clause of `A`.

This is not a proof but as you see the `R` recurses, but with ever decreasing values. And using programmer lingo, `h` never "runs" until all the recursion is done.

Intuitively the `x` here is like a for loop counter and at the end of the day, the function `h` collects all the numbers 0...x and a bunch of `y`s into a single number (in a primitive recursive way). That is not enough to model the nested recursion we see in the third ackermann clause.

I hope that does something for you, it's the simplest explanation I can come up with.

Answer 2

If we add an operator called `μ` to all the primitive-recursive ones we get the class of μ-recursive functions, and ackermann is part of those.

I don't have a direct proof for that either, but afaik μ-recursive functions are as powerful as turing machines and ackermann can be computed by TMs so it must be μ-recursive.

The busy beaver function for example cannot be computed by a TM so it isn't μ-recursive either.