patternMinor
Showing that deciding whether a given TM accepts a word of length 5 is undecidable
Viewed 0 times
acceptsshowingundecidablelengthwordthatdecidingwhethergiven
Problem
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:
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
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!
Source
Solution
Suppose that $M$ halts on input $w$ and consider the behaviour of $M'$ when it is given input $w'\!$. $M'$ first deletes its input $w'$ and replaces it with $w$, which means that the behaviour of $M'$ doesn't depend on what input it actually receives. Then, $M'$ simulates $M$ on input $w$. So, if $M$ halts on $w$, $M'$ halts for every input, becaues $M'$ ignores its input and just pretends to be $M$ running with input $w$. Likewise, if $M$ does not halt on $w$, $M'$ doesn't halt for any input.
Context
StackExchange Computer Science Q#23804, answer score: 4
Revisions (0)
No revisions yet.