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.

  • $\begingroup$ My intuition is as follows. Primitive recursive functions are in r.e., since we cannot say for some non-primitive non-halting function is it in the set of primitive ones. If we could, we would have a solution to the halting problem. If total recursive functions are in non-r.e., that means their complement is in r.e. $\endgroup$
    – bellpeace
    Feb 20, 2012 at 6:53
  • $\begingroup$ You should be more specific about the halting problem being enumerable. You can enumerate (machine,input) pairs that terminate, but not machines that will invariably terminate. Similarly you can enumerate (function,argument) pairs for which the value is defined, but not the set of total functions. $\endgroup$ Mar 12, 2012 at 8:55
  • $\begingroup$ your comment is totally confused. How could a non-primitive function be in the set of primitive ones? Also (the integers encoding) total recursive functions are not r.e., but their complement not r.e. either, even less so in a certain sense. $\endgroup$ Mar 12, 2012 at 8:59
  • $\begingroup$ "How could a non-primitive function be in the set of primitive ones?" I was saying this in terms of giving a non-primitive non-halting function as an input to a decision procedure for the primitive recursive functions. $\endgroup$ Mar 15, 2012 at 20:25

1 Answer 1


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.

  • 1
    $\begingroup$ +1, comprehensive answer. But you should at least state the answer to the OP's question at the beginning rather than deferring it to your 5th paragraph! $\endgroup$
    – Zhen Lin
    Feb 21, 2012 at 20:38
  • $\begingroup$ Thanks for answering! Just one follow-up question on your last statement. On wikipedia I found that halting-problem is characterized as semi-decidable (halting;I know that wikipedia is not a source of information I should be using, but even you used it). From language point of view, it makes sense to me. My decision procedure can actually just simulate TM on its input. If it's suppose to terminate, procedure will return true, loop otherwise, which is Turing-recognizable. Am I missing something? $\endgroup$ Feb 22, 2012 at 6:17
  • $\begingroup$ @bellpeace WP is usually ok on mathematical topics. Regarding your follup-up: you can easily semi-decide whether a TM halts on a particular input. But what's needed here is to know whether the TM halts on every input; that is not even semi-decidable. $\endgroup$ Feb 22, 2012 at 15:55
  • $\begingroup$ I need help to better understand the proof. If a primitive recursive function is a row in the diagonal matrix and therefore all the rows are the complete set of primitive recursive functions. Then is the resulting function, h(x) = F(r(x))(x) + 1, primitive recursive or not primitive recursive? It is not primitive recursive according to the reasoning method of the proof. At the same time, it is primitive recursive because the function h(x) = F(r(x))(x) + 1 is in a form of primitive recursive functions. $\endgroup$ Mar 2, 2012 at 1:37
  • $\begingroup$ @uneverknow $h$ is not constructed in a primitive recursive way. When we assume that the set of recursive functions is r.e., it means we have a recursive function $r$ to enumerate the set. If we wish to enumerate the set of primitive recursive functions instead, we still get an enumeration function that's recursive, but may or may not be primitive recursive. So when working on the set of p.r. functions, $h$ ends up being recursive and not primitive recursive, that's ok (and in fact it's a way of proving that there exist recursive functions that aren't primitive recursive). $\endgroup$ Mar 2, 2012 at 10:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .