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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
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.
answered Jun 15, 2018 at 11:17
-
$\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$ Commented 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$ Commented 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$ Commented 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$ Commented Jun 15, 2018 at 13:47
-
$\begingroup$ you mean cs.stackexchange.com/questions/39651/…? $\endgroup$ Commented Jun 15, 2018 at 14:00