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:
- $M′$ erases its own input and replaces it with the string w.
- It them simulates $M$ on $w$.
- 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!