What lies between primitive recursion and total recursion?

Question

My understanding is that there are total recursive functions that are not primitive recursive, such as the Ackermann function. What classes of functions (or sets) lie between primitive recursion and total recursion, that include and exclude the Ackermann function?

Answer 1

Primitive recursive functions are a 'recursively enumerable' (listable) subset of the total recursive functions, which in turn are a subset of the partial recursive functions. So the memberships look like:

Primitive recursive $ \subset $ total recursive $ \subset $ partial recursive

Finding a recursively enumerable list of total recursive functions which contains the set of primitive recursive functions as a proper subset can be easily done using diagonalization:

Suppose we have a recursively enumerable list $S=f_1, f_2, ..., f_n,... $ of all primitive recursive functions. Because the primitive recursive functions are total, we know the output of each $f_n(x)$ will always be defined for all $x \in N $. Define the following diagonal function $d(x)=f_x(x)+1 $ for all $x \in N$. Obviously this function is not primitive recursive: if we let $d$ be in our original list $S$, i.e. $d=f_e$ for some natural number $e$, then we'd have $d(e)=f_e(e)=f_e(e)+1 $ which implies $0=1$ (a contradiction). Because each $f_n$ is primitive recursive and defined for all natural numbers $n$, and because adding 1 is obviously recursive, this implies $d$ is a total recursive function that is not primitive recursive.

The following is a recursively enumerable list of total recursive functions which contains the primitive recursive functions as a proper subset.

$S' = d,f_1, f_2, ..., f_n,... $

The memberships would look like:

$S$ (primitive recursive) $ \subset S' \subset $ total recursive $ \subset $ partial recursive

This process could be repeated by renaming the recursively enumerable members of $S'$ as $S'=f'_1, f'_2, ... f'_n,...$ to reveal $ S''$ and repeated further to reveal $ S'''$ and $ S''''$ such that we'd have:

$S$ (primitive recursive) $ \subset S' \subset S'' \subset S''' \subset S'''' \subset $ total recursive $ \subset $ partial recursive

There is much more to be said about all this, but I figured I'd give you a little teaser.