3
$\begingroup$

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

enter image description here

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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
1
$\begingroup$

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 the input of $M'$ 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.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I understood the explanation of why this problem is undecidable. But my question is, we have finite strings of length 5 and if a TM really accepts string of length 5 then it should take maximum of 5 steps. So we have finite number of strings which we can run for finite number of steps . So shouldn't it be decidable ? $\endgroup$
    – Zephyr
    Commented Sep 9, 2017 at 6:48
  • 1
    $\begingroup$ @Zephyr It's not true that a Turing machine that accepts a string of length five must do so in at most five steps. Indeed, there's no computable bound on the number of steps it might take. $\endgroup$
    – David Richerby
    Commented Sep 9, 2017 at 18:26
  • $\begingroup$ every character in the input has to take minimum 1 step in standard Turing machine right ? $\endgroup$
    – Zephyr
    Commented Sep 10, 2017 at 5:42
  • 1
    $\begingroup$ @Zephyr That would argue for a minimum of five steps, not a maximum. But note that a machine can halt before reading its whole input -- for example, the language "the first character of the string is '$0$'" can be decided in one step, regardless of the length of the input. $\endgroup$
    – David Richerby
    Commented Sep 10, 2017 at 9:03
  • 1
    $\begingroup$ @Zephyr any machine that moves its head to the left at least once. $\endgroup$
    – David Richerby
    Commented Sep 10, 2017 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.