[Solved]: Showing that deciding whether a given TM accepts a word of length 5 is undecidable

Problem Detail: 

I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this:

Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$ accepts any string of length $5$, i.e., $L(M)$ contains a string of length $5$. The above figure shows how we can use this to construct a Turing Machine that can solve the Halting problem.

The output $M′$ of our translator behaves as follows:

1. $M′$ erases its own input and replaces it with the string w.
2. It them simulates $M$ on $w$.
3. If $M$ halts on $w$, then it goes into a final state (accepts its input). It is clear that if $M$ halts on $w$, $M′$ accepts all its inputs. So it accepts a string of length 5 as well. If $M$ does not halt on $w$, $M′$ does not accept any string at all. So it does not accept any string of length 5 either. So $L(M′)$ includes a string of length $5$ if and only of $M$ accepts $w$. So by running $M_5$ on $M′$, we can decide if $M$ halts on $w$ or not. But we know that this is not possible since the halting problem is undecidable. Hence $M_5$ does not exist and the given problem is undecidable.

What I am confused about is: "if $M$ halts on $w$, $M′$ accepts all its inputs" and "If $M$ does not halt on $w$, $M′$ does not accept any string at all". Can someone clarify why this is the case? I've been trying to work out the logic for so long. If any of you guys could help this would be great!

Source

Asked By : Andrew Reynolds

Answered By : Jasper

To decide if $M$ halts with input $w$, we use the Machine $M'$ that simulates $M$ with input $w$. If $M$ accepts $w$, $M'$ also accepts $w$ (from point 3 of your description). If however $M$ does not halt on input $w$, the simulation can not halt as well.

So far, nothing special has happened.

Now consider point 1 of your description: $M'$ does take an input, but immediately discards it.

So to decide if $M$ halts on $w$, we use $M_5$ to decide if $M'$ accepts a word of length 5. But $M'$s behavior is completely independent of it's own input, since it just simulates $M$ with fixed $w$.

Now: if $M$ halts on $w$, $M'$ will halt on every input (because it is discarded and $w$ is used instead), especially one of length 5. This will (magically/hypothetically) be detected of $M_5$.

If however $M$ does not halt on $w$, $M'$ will not halt on any input (again, because $M'$s input is irrelevant), especially it will not halt on any input of length 5. This can also be detected by $M_5$, and we have solved the halting problem.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23804