Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
I think this question is a better fit for cs.stackexchange.com –  utdiscant Aug 13 '12 at 4:27
1  
@utdiscant No, this question belongs here. –  Andres Caicedo Aug 13 '12 at 5:12
1  
@AndresCaicedo: At the very least, it belongs to both sites. Where you want to post is essentially decided by the kind of answer you want. The only current tag (computer-science) should be a hint towards this question's affiliation, though. –  Raphael Aug 13 '12 at 7:41

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.