Consider the language

$$ L = \{ \langle M,w \rangle \mid \text{$M$ on input $w$ tries to move its head past the left end of the tape}\}. $$

Prove whether L is decidable or not.

I tried to prove it as undecidable through reduction method but could'nt reduce the language halt to L inorder to prove that it is undecidable.

  • 3
    $\begingroup$ I think you should try harder. Already solved two questions for you. Now it's time for you to do the rest on your own. $\endgroup$ – Yuval Filmus Apr 24 at 13:53
Construct Turing Machine M':
        On input x: Ignore the input x
        Simulate the run of machine M on w a separate tape
        If M accepts or reject: 
             Move the head of M' left
             Do Nothing

The machine M' described above will "try" to move the head on left only if M halts on w.

If L is decidable, then we can check for membership of $(M',\epsilon)$; but that will decide that $M$ halts on $w$ (The Halting Problem).

Hence, the language L is undecidable.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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