In quite some literature I found that primitive recursive functions are recursively enumerable, but total recursive ones are not. To what set do total recursive functions belong?
I am asking this since I learned that even the halting problem is in recursively enumerable.
Best Answer
Summary: total recursive functions are not recursively enumerable; the proof follows from a typical diagonal argument.
“Recursively enumerable” is a property of a set of integers. “Partial recursive” or “total recursive” or “primitive recursive” are properties of functions from integers to integers. The concepts aren't quite on the same plane. Then there's also the RE complexity class, which is a class of functions from some problem domain to booleans; saying that a decision problem is in RE is equivalent to saying that the language that it recognizes is recursively enumerable, if the language is encoded in in the integers.
It is not possible to encode all functions as integers (by a diagonal argument, the set of all functions from integers to integers is uncountable and therefore you cannot find a distinct integer for every function).
On the other hand, it is possible to encode all partial recursive functions as integers, for example by writing these functions in a programming language and reading the bytes that make up the source code as the digits of some integer in base 256 (there are many programs that implement each function, of course, so pick the one that gives the smallest integer). Note that an encoding must be one-to-one, but need not be surjective. If you take a particular such encoding (any “sensible” one will give equivalent results in the end), then you can consider a class of partial recursive functions (the class of all partial recursive functions, the class of primitive recursive functions, the class of constant functions, etc.) and ask what kind of properties the set of all encodings of such functions have.
The set of encodings of partial recursive functions is recursively enumerable. As above, consider the source code of functions expressed in some idealized programming language. Program sources are easy to enumerate: sort strings by length then in lexicographic order, and skip the ones that are not syntactically well-formed (this is a decidable procedure). You have an enumeration of the partial recursive functions (each function will be reached an infinite number of times in the enumeration since there are infinitely many ways to implement it).
On the other hand, the set of encodings of total recursive functions is not recursively enumerable. As often, the proof is based on a diagonal argument. Let $E(f)$ be the encoding of a function $f$ and $F(x)$ be the preimage of $x$ if it exists (i.e. $E(F(x))=x$). Suppose there is an enumeration $r$ of all encodings of recursive functions, i.e. a recursive function $r : \mathbb{N} \mapsto \mathbb{N}$ such that for any total recursive function $f$, there is an integer $x$ such that $r(x)=E(f)$. Define a function $h : \mathbb{N} \mapsto \mathbb{N}$ by $h(x) = F(r(x))(x) + 1$. Then $h$ is not a total recursive function (otherwise there would be some $x$ such that $h = F(r(x))$). Yet because $r$ is recursive, $h$ is total recursive. The assumption that the set of encodings of total recursive functions is recursively enumerable is thus false.
If you take the class of all primitive recursive functions, then it turns out that the set of encodings is recursively enumerable. In other words, you can list all the primitive recursive functions. The idea is pretty similar to the case of the partial recursive functions above. There is no decision procedure that given a program source, can determine whether it is the source of a primitive recursive function (more generally, there is no such decision procedure for any non-trivial property — this is Rice's theorem). But recall that every function can be implemented in (infinitely) many ways: it's enough to enumerate one implementation of every function. By definition, any primitive recursive function can be expressed with projections, constants, the successor function, composition and primitive recursion. Whether an expression is of this form is easily decidable (it's a context-free grammar plus a check that variable names are used correctly). So there is a way to enumerate a set that contains the source code of every primitive recursive function, and only contains the source code of primitive recursive functions. This provides an enumeration of the set of all encodings of primitive recursive functions.
(The enumeration of primitive recursive functions above lists every function many times, for example the identity function also appears as $x \mapsto x+0$, $x \mapsto S(S(S(x) \times 1)-3))$, etc. Interestingly, it is possible, but a lot more difficult, to enumerate the primitive recursive functions without duplication, even though equality of primitive recursive functions is not decidable. See The Primitive Recursive Functions are Recursively Enumerable by Stefan Kahrs).
P.S. “We cannot say for some non-primitive non-halting function is it in the set of primitive ones”: true, but that would tend to indicate that the primitive recursive functions are no r.e.; as seen above, they are, because it's enough to find one way of expressing the function that we can tell is primitive recursive. “If total recursive functions are in non-r.e., that means their complement is in r.e.”: no, that's wrong, the non-total-recursive functions are not recursively enumerable either; the halting problem is not semi-decidable either way.