# Turing machine on input w tries to move its head past the left end of the tape

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.

• 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. – 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
Else:
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.