1
$\begingroup$

After having compiled several sources from handbooks or the web, and read some answers posted here, I'm still confused with the question of non recursive enumerability of total recursive functions, while partial recursive functions and primitive recursive functions are.

Indeed, partial recursive functions strictly contain total ones, that in turn strictly contain primitive recursive ones. So I am not looking for a proof that some are recursively enumerable or others are not, but I have trouble understanding why this "middle set" of total recursive functions has not a property that the "outer sets" have!?

Also, I didn't find a proof that the set of (Gödel numbers of) primitive recursive functions are not recursive? Is it non-sense?

And, what about elementary functions? Is it a recursive set? Recursively enumerable set?

Thanks.

$\endgroup$
1
  • $\begingroup$ The terminology used here is used in a nonstandard way that makes the question somewhat difficult to read. Each total recursive function is recursively enumerable (remember that a function is a set of ordered pairs). The set of total recursive functions is not recursively enumerable, however. Similarly, each total recursive function contains many partial recursive functions (and also contains some partial functions that are not recursive). But the set of all partial recursive functions contains the set of total recursive functions. $\endgroup$
    – Carl Mummert
    Oct 15, 2014 at 11:57

1 Answer 1

Reset to default
1
$\begingroup$

So I am not looking for a proof that some are recursively enumerable or others are not, but I have trouble understanding why this "middle set" of total recursive functions has not a property that the "outer sets" have!?

That in itself shouldn't be surprising. Every "difficult" set sits between the empty set and the set of all strings/numbers, even though those to sets are the easiest there are. It shouldn't be remarkable, then, that we can also sandwich a difficult set such as the set of (Turing machines that implement) total recursive functions, between two more interesting, but still easier, sets.

Also, I didn't found a proof that the set of (Gödel numbers of) primitive recursive functions are not recursive? Is it non-sense?

That depends on your encoding. It is possible to define a Gödel numbering such that every primitive recursive function has a number, and such that the set of numbers that encode primitive recursive functions is recursive.

The cost of that is that the numbering can't then include indices for all total recursive functions, at least not if the encoding is effective -- that is, there is an algorithm to get from the index of a function and a concrete function argument, to the value of the function at that argument.

If we have an effective (and otherwise well-behaved in a certain minimal sense) encoding that represents every total recursive function, then the set of numbers that happen to represent primitive recursive functions under that encoding is necessarily undecidable.

And, what about elementary functions? Is it a recursive set? Recursively enumerable set?

"Elementary functions" are usually taken to be certain functions $\mathbb R\to \mathbb R$, which live in a somewhat different world than the functions $\mathbb N\to\mathbb N$ (or equivalently $\{0,1\}^*\to\{0,1\}^*$) that we speak about in recursion theory.

Again, it is certainly possible to choose an encoding that can only encode elementary function but does encode all of them -- in which case set of indices of elementary functions is "boringly" recursive. But that doesn't help us much if what we were after was something we could give an arbitrary real function and ask whether it is elementary or not.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer. For the first point, I think I begin to glimpse the solution; I had the same problem with the recognition problem on a class of graphs, that is hard for a class in sandwich between two others, where the problem is easy. But in the same time, my intuition tells me that the biggest set should not have a property when one of its subsets has not... For the third point, I was talking about the class ELEMENTARY of "primitive recursive functions without primitive recursion" $\endgroup$
    – Greg82
    Oct 14, 2014 at 20:36
  • $\begingroup$ @Greg82: Oh sorry. I'm apparently not that well versed in complexity theory. $\endgroup$
    – hmakholm left over Monica
    Oct 14, 2014 at 20:50

You must log in to answer this question.

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