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?


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$ – idontunderstandthis Jun 15 '18 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$ – David Richerby Jun 15 '18 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$ – idontunderstandthis Jun 15 '18 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$ – David Richerby Jun 15 '18 at 13:47
  • $\begingroup$ you mean cs.stackexchange.com/questions/39651/…? $\endgroup$ – idontunderstandthis Jun 15 '18 at 14:00

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.