# turing machines – Is the set of recursive subsets of the set of natural numbers not r.e.?

I think that the set of recursive subsets of the set of natural numbers is not r.e. (meaning the set of codes of those subsets according to an admissible numbering).
I think I can provide the sketch of the proof of such statement and I would like to ask if what I write is correct.

PROOF SKETCH

This statement is equivalent to prove that the set of characteristic functions of recursive sets of natural numbers is not r.e., we are talking about recursive functions of this form: $$f: mathbb{N} longrightarrow {0,1}$$.
To be precise we are talking of the set of the codes according to an admissible numbering of those functions.

For any such function $$f_k$$ there is an infinite recursive binary sequence: $$f_k(0), f_k(1),…,f_k(i),…: i in mathbb{N}$$.
Let $$TM_k$$ be a Turing machine that on empty input outputs the binary sequence associated to $$f_k$$.

Let $$widetilde{TM}$$ be a Turing machine that enumerates those Turing machines $$TM_k: k in mathbb{N}$$ (to be precise it enumerates the codes of those Turing machines).

We can build a Turing machine $$widehat{TM}$$ that given as input the code of any Turing machine $$TM_x$$ runs both $$TM_x$$ and $$widetilde{TM}$$.
Then one of those two things must happen, either $$TM_x$$ halts or $$widetilde{TM}$$ outputs the code of
$$TM_x$$ which means $$TM_x$$ does not halt. So $$widetilde{TM}$$ can decide the halting problem (restricted to $$TM$$‘s with empty input but it is equivalent to the general halting problem, see this link), which is a contradiction.
So $$widetilde{TM}$$ can not be built, the set of $$TM_k$$ is not r.e. and so the set of recursive subsets of the set of natural numbers is not r.e. $$blacksquare$$

I assume the Turing degree of this set is $$mathbf{0}’$$ because an oracle for the halting problem make this set recursive.