Timeline for Turing machine that does not halt on any input
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2018 at 15:00 | vote | accept | idontunderstandthis | ||
| Jun 15, 2018 at 14:46 | comment | added | David Richerby | Almost, but you're doing the reduction the wrong way around. You're supposed to use whether or not $M'\in T$ to decide whether $M$ halts (reducing the halting problem to $T$, which shows that $T$ is undecidable because the halting problem is), not using whether or not $M$ halts to decide whether $M'\in T$ (reducing $T$ to the halting problem, which just shows that $T$ isn't any harder than the halting problem, while leaving open the possibility that it might be easier). But $M'\notin T$ if and only if $M(w)$ halts, so you don't need to do any more work; just write the answer the right way. :-) | |
| Jun 15, 2018 at 14:25 | comment | added | idontunderstandthis | So $M'$ writes $w$ and then simulates $M(w)$, if $M(w)$ halts that means $M' {\not \in}T$ and it rejects, otherwise it accepts? | |
| Jun 15, 2018 at 14:06 | comment | added | David Richerby | @idontunderstandthis Yes. That's asking a slightly different problem (showing that a language isn't even RE, let alone decidable) but, if you understand what's there, you should be able to answer your question. | |
| Jun 15, 2018 at 14:00 | comment | added | idontunderstandthis | you mean cs.stackexchange.com/questions/39651/…? | |
| Jun 15, 2018 at 13:47 | comment | added | David Richerby | $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. | |
| Jun 15, 2018 at 13:44 | comment | added | idontunderstandthis | 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?? | |
| Jun 15, 2018 at 12:55 | history | edited | David Richerby | CC BY-SA 4.0 |
added 19 characters in body
|
| Jun 15, 2018 at 12:54 | comment | added | David Richerby | 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$. | |
| Jun 15, 2018 at 12:20 | comment | added | idontunderstandthis | 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 :( | |
| Jun 15, 2018 at 11:17 | history | answered | David Richerby | CC BY-SA 4.0 |