I'm struggling to find a way to show that $$T = \{ \langle M \rangle\mid M \text{does not halt on any input}\}$$ is undecidable. Should I use reduction? If so, reduce this to what &ndashp the halting problem?


1 Answer 1


To use reduction, you would need to show that the halting problem reduces $T$, not the other way around.

The reduction* in this case is a standard one. You want to know if $M$ halts on input $w$ but all you have is this lousy T-shirt a procedure that tells you if a machine loops on every input. So you construct a machine $M'$ such that does the same thing on every input, so that whether or not $M'\in T$ tells you whether or not $M$ halts on input $w$.

* Well, strictly a reduction: if there's one, there are infinitely many.

  • $\begingroup$ So i have to build $M'$ to solve the halting problem using $T$ right? How can i "make sure that thing tells you what $M$ does on input $w$", im sorry i dont really understand how to do this :( $\endgroup$ Jun 15, 2018 at 12:20
  • $\begingroup$ Not quite. You have to build $M'$ from $M$ and $w$ so that whether or not $M'\in T$ tells you whether or not $M(w)$ halts$. $\endgroup$ Jun 15, 2018 at 12:54
  • $\begingroup$ If $M' \in T$ then $M(w)$ doesnt halt. The thing i dont understand is how i go about the "any input" thing compared to having a $w$ or $w\#w$. Is it possible to say that $M'$ tests all possible inputs?? $\endgroup$ Jun 15, 2018 at 13:44
  • $\begingroup$ $M'$ doesn't need to test all inputs, because you only care about input $w$. Have you seen the proof that "Does this TM halt on every input?" is undecidable? The proof you need here is almost identical. $\endgroup$ Jun 15, 2018 at 13:47
  • $\begingroup$ you mean cs.stackexchange.com/questions/39651/…? $\endgroup$ Jun 15, 2018 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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