You are given, as input, some Turing Machine M and some string w. The problem is

Question

You are given, as input, some Turing Machine M and some string w. The problem is to determine whether the machine M, when executed on the input string w, ever moves its read-head to the left. Explain why the following “algorithm” is faulty:

if (some delta-rule in M has an ‘L’ in the last entry of the 5-tuple of that delta-rule)

-->then when M is executed on w, the read-head will move left at some time during the computation.

--> --> else when M is executed on w, the read-head NEVER moves left during the computation.

Thanks a lot for your help!8

Explanation / Answer

The proof is by contradiction. Assume that this problem is decidable, then we will show that ATM (the acceptance problem) is also decidable: ATM = { | M is a TM and M accepts w}. Let R be a Turing machine that decides the LEFTMOST problem. That is, R decides the language

LEFTMOST = { | M on input w ever attempts to move its head left when it's head is on the left-most tape cell }.

Now, the idea is to construct a Turing machine S that decides ATM in such a way that it uses R. We can do it as follows: On input , S first modifies machine M to M´, so that M´ moves its head to the left from the left-most cell only when M accepts its input. To ensure that during its computation M´ doesn't move the head left from the left-most position, machine M´ first shifts the input w one position to the right, and places a special symbol on the left-most tape cell. The computation of M´ starts with the head on the second tape cell. If during its computation M´ ever attempts to move its head to the left-most tape cell, M´ finds out that it did so by reading the special symbol and then puts the head back to the second cell, and continues its execution. If M would enter an accept state, then M´ enters a loop that forces the head to move always to the left.

After S has constructed M´ it runs the decider R on input < M´; w>. If R accepts then S accepts, otherwise if R rejects then S rejects. Therefore, ATM is decidable, which is a contradiction.

Define M' as a turing machine that takes a pair (M,w) as input, where M is a turing machine encoded in some form recognized by M' and w is the input to M.

M' stops and accepts (M,w) whenever the head of the simulated machine M moves to the left while processing input w

For a particular input to M' (M,w), construct the turing machine P as follows:

We have reduced the Universal Turing Machine U to P. Since we know that L(U) is not decidable, we conclude that L(P) is not decidable. Consequently, M' is not decidable.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.