2

I read that the set of partial recursive functions is recursively enumerable while the set of total recursive functions is not. Isn't the set of total recursive functions a proper subset of the set of partial recursive functions?

The argument for recursively enumerability of the set of partial recursive functions is that you can list the programs that compute them in a lexicographic order and use the index in that ordering as an argument of a function with two variables. The diagonal argument is used to show that the set of total recursive functions is not recursively enumerable. But why would the first argument fail in case of total rec. functions? Could anyone clarify this at all?

  • It looks as if you (or the source of your reading) confuse "countable" with "recursively enumerable". The set of total recursive functions is countable, but there is no effective enumeration of it. That is, there is no total recursive function of two variables such that the functions obtained by fixing the first argument are exactly all the total recursive functions of one variable. – Andreas Blass Apr 21 '14 at 14:07
  • You're right, I misinterpreted. I will fix the question, but I am still wondering as to why there is such a function of two variables (universal function) for partially defined recursive functions, but there is not for total recursive functions? –  Apr 21 '14 at 14:22
  • If the universal function is defined so that the first argument is the index in a lexicographic ordering of the programs that compute partially defined functions, why wouldn't the same argument work for total recursive functions. –  Apr 21 '14 at 14:28
  • To effectively enumerate the total recursive functions, using the same idea as for partial ones, you'd need an indexing. It's pretty easy to list all programs (in lexicographic order, as you said), but to effectively list just the total ones, you'd need to separate total from non-total ones. There's no way to effectively decide, given an arbitrary program, whether it computes a total function. Nor is there even a way to effectively list enough total programs to have at least one computing each total recursive function. – Andreas Blass Apr 21 '14 at 14:29
  • @AndreasBlass I get it now. Thank you. If you would make that last comment into an answer I would accept it. –  Apr 21 '14 at 14:34

0 Answers0