I have a question about undecidability. And I hope you could point out where I am wrong.

The question is: to decide the following question as (A) recursive, (B) RE but not recursive, (C) not RE.

$L = \{\langle M\rangle|M \text{ is a TM and } |L(M)| \geq 3\}$

If we use $HP$ as halting problem and $\overline{HP}$ as the complement of halting problem. Then the solution could be (B) RE but not recursive (Taken from the Internet):

enter image description here

I understand this proof. But I have another proof as follows, and I can't figure it out why it is wrong.

We prove this by a reduction from $\overline{HP}$. Simulate $M'$ on input $w$ works as follows: it runs $M$ on $x$ and rejects if $M$ halts on $x$.

(1) $\langle M, x\rangle \in \overline{HP}$ $\rightarrow$ $M$ doesn't halt on $x$ $\rightarrow$ $M'$ accepts all inputs $\rightarrow$ $|L(M')| \geq 3 $ $\rightarrow$ $M' \in L$

(2) $\langle M, x\rangle \notin \overline{HP}$ $\rightarrow$ $M$ halts on $x$ $\rightarrow$ $M'$ doesn't accept any input $\rightarrow$ $|L(M')| < 3$$\rightarrow$ $M' \notin L$

Thus $\overline{HP} \leq_m L$. As $\overline{HP}$ is not RE, $L$ is not RE, which is wrong.

So where is wrong?


  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 12 '17 at 13:33
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – Raphael Feb 12 '17 at 13:34
  • 1
    $\begingroup$ We discourage "please check my proof" questions, because they're only of interest to somebody who's come up with the exact same proof. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Feb 12 '17 at 14:09
  • $\begingroup$ Thanks for pointing these points out! I will make sure that I won't do this again next time. $\endgroup$ – fear Feb 12 '17 at 16:50

Recall that if a TM $M$ doesn't halt on input $x$, then $x \notin L(M)$

Your mistake is in (1), if $M$ doesn't halt on $x$, then $M'$ doesn't halt too (since the simulation of $M$ on $x$ doesn't halt). so $M'$ doesn't accept any input, that is $L(M')=\phi$.

  • $\begingroup$ Thank you! But I am still confused by "if $M$ doesn't halt on $x$, then $M'$ doesn't halt too". I have simulated a Turing machine $M'$ that rejects if $M$ doesn't halt. Where is wrong? $\endgroup$ – fear Feb 12 '17 at 16:52
  • $\begingroup$ On your solution you wrote that $M'$ rejects if $M$ halts on $x$. You generally can't know if a TM doesn't halt on a specific input (This is the halting problem). If you reject when $M$ halts, $M'$'s language will be the same whether $M$ halts on $x$ or not (the empty language). $\endgroup$ – dave Feb 12 '17 at 18:53
  • $\begingroup$ Many thanks! I just want to confirm if my understanding is right. 1. if $M$ doesn't halt on $x$, then no matter how I simulate $M'$, $M'$ will always doesn't accept any string. 2. If I accept when $M$ halts, then I will get $|L(M')| > \text{finite number}$. 3. I am not so sure about your last sentence, should it be "If I reject when $M$ halts, then $M'$'s language is kind of complement to $M$". Am I correct regarding to 1, 2, and 3. Thanks again! $\endgroup$ – fear Feb 12 '17 at 20:20
  • $\begingroup$ 1. You could simulate in many other ways that will make $M'$ accept other languages. but nothing will achieve the desired correctness, i.e, there is no way to get "$M$ doesn't halt on $x$ if and only if $|L(M')| \geq 3$ ". 2. if you accept when $M$ halts on $x$ then you get $L(M)= \Sigma^{*}$ if $M$ halts on $x$ and $L(M)= \phi$ otherwise. (which is the opposite of what you need, and indeed this is the reduction from $HP$). and 3. As i siad, in case you reject when $M$ halts on $x$ you get $L(M')=\phi$ in both cases: if $M$ halts on $x$ and if it doesn't. $\endgroup$ – dave Feb 12 '17 at 20:35
  • $\begingroup$ Could you explain a little bit more about point 1? Now it seems to me that if $M$ doesn't halt on $x$, then actually you can't do anything on top of it -- $M'$ built on $M$ doesn't halt also. Then if $M'$ doesn't halt, it can't accept any language. Again, thank you for your great comments! They helped me a lot. You made my day. $\endgroup$ – fear Feb 12 '17 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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