Are total recursive functions recursively enumerable?

In quite some literature I found that primitive recursive functions are recursively enumerable (r.e.), but total recursive ones are not. Then, what set do they belong to?

I am asking since I learned that even the halting problem is in r.e.

Thanks for understanding!

-

migrated from stackoverflow.comFeb 21 '12 at 19:29

This question came from our site for professional and enthusiast programmers.

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. – bellpeace Feb 20 '12 at 6:53
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. – Marc van Leeuwen Mar 12 '12 at 8:55
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. – Marc van Leeuwen Mar 12 '12 at 8:59
"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. – bellpeace Mar 15 '12 at 20:25

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, 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! – Zhen Lin Feb 21 '12 at 20:38
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? – bellpeace Feb 22 '12 at 6:17
@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. – Gilles Feb 22 '12 at 15:55
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. – u never know Mar 2 '12 at 1:37
@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). – Gilles Mar 2 '12 at 10:01

Gilles, I agree that the set of all programs (i.e., source code) that finitely express the class of total recursive functions is not recursively enumerable (or called computably enumerable). But the class of total recursive functions is itself recursively enumerable. Here is a proof:

Let a Turing machine M enumerate all partial recursive functions. For each step, it simulates program p on the i th input for j steps. If p stops with a result k, then it generates a record <p, i, k, m> and increases the number m by 1, here m serves as the index of the record. If p doesn't stop, it doesn't generate anything and moves on to the next step to continue the enumeration process.

Given a time in the future, M generates a finite set of such records, each of which has a unique index m. When we sort all the records in the syntactical order (or Godel numbers) of programs, we can obtain a set of records sharing the same program p. Such a set doesn't constitute the complete but a subset of the properties of p.

When we let M runs forever, i.e., in countably infinite steps, we would eventually generate the entire records that constitute the complete class of total recursive functions. (Consequently, at the end of the infinite time, of course that never comes, all the records sharing the same p constitute the entire properties of p.)

This set is very special. It doesn't resolve the halting problem unless we waited to the end of infinite time. It represents a strictly subset of all total recursive functions at any given time in the future. But it progressively accumulates more and more records, and eventually converges to the complete properties of all total recursive functions. This set is recursively enumerable.

By the way, the diagonal method you used only shows that we have uncountable total functions in the number-theoretical theory while all total recursive functions are countable. An uncountable set is certainly not recursively enumerable.

-