Recursively enumerable set? Any hints?

Question

I don't mean to be pulling answers out of you, but I'm stuck. Any advice on the right direction would be appreciated. I have the following set $X$ ={$n$ where $n$ is a number of a turing machine $M$ that does not halt when given $n$ as input}

My gut instinct is that it's not. And that's because the question asks about the set of all x's that are not partially decidable. Recursively enumerable languages ARE partially decidable, so it can't be REL.

Is this correct? And is this sufficient reasoning?

Thanks.

Answer 1

If $X$ is r.e., there is a Turing machine $T$ such that $T$ halts on input $n$ iff $T_n$ does not halt on input $n$. Say $T=T_m$. Then $T_m$ halts on input $m$ iff $T_m$ does not halt on input $m$. Thus, $X$ cannot be r.e.

Answer 2

The set $Y$ of all natural numbers $n$ such that $n$ is the number of a Turing machine that halts on input $n$ is r.e..

The set $K$ of all natural numbers $n$ such that $n$ is not the number of a Turing machine is recursive.

It follows that the set $Y\cup K$ of natural numbers $n$ such that $n$ is the number of a Turing machine that halts on input $n$ or $n$ is not the number of a Turing machine is r.e..

But $Y\cup K$ is the complement of $X$. So if $X$ is r.e., then since its complement is r.e., $X$ is recursive. But that is not the case, since if $X$ is recursive, then $X\cup K$ is recursive, and therefore $Y$ is recursive. It is well-known that $Y$ is not recursive.

Answer 3

A useful well-known result is that a set $A \subset \omega$ is computable (recursive, decidable) if and only if $A$ and $\omega - A$ are computably enumerable.

Let $X$ be your set above. Then $\omega - X$ is the set of $n$ such that the $n^\text{th}$ Turing machine halts on $n$. This set equivalent to the Halting Problem set. It is well-known that the Halting Problem set is computably enumerable but not computable. Hence, if $X$ is computably enumerable, then you have that both $X$ and $\omega - X$ are both computable enumerable. By the result of the first paragraph, you would have that $\omega - X$, the Halting Problem set, is computable. Contradiction!