# Proving that the language of TMs with finite left head moves is undecidable

I'm trying to prove that the following language is undecidable:$$\{ \langle M, w \rangle ~|~ M \text{ is a TM where its head moves left a finite number of times on } w \}$$

But I'm having a bit of trouble. I know I have to do some type of reduction, but I'm not really sure what. Can a Turing Machine be simulated by one which only moves left? if so, then I think I could show $A_{TM}$ reduces to it. Any hints would be appreciated.

Hint: Reduce from the halting problem. Given a Turing machine $M$ and an input $w$, you want to come up with a new pair $\langle M',w \rangle$ such that $M$ halts on $w$ iff $M'$ makes a finite number of left moves on $w'$. Now if $M$ halts on $w$ then in particular it makes a finite number of left moves, but the other direction is not true. Think of a way of ensuring that if $M$ makes an infinite number of moves in any direction, then $M'$ makes an infinite number of left moves. (You might want to add some spurious moves.)
• I've been working on this, but still don't quite have it. Why should $M'$ make an infinite number of left moves if $M$ makes infinite moves in any direction? Shouldn't $M'$ halt if $M$ makes and infinite number of right moves? – Joseph Webb Nov 11 '13 at 20:00
• I've been thinking about using using $M'$ to create another TM $M''$ to check if $M$ makes a finite number of right moves on $w$. Then the halting problem could be solved by checking if $M'$ and $M''$ accept (the contradiction). Am I on the right track? I really appreciate all the help. – Joseph Webb Nov 11 '13 at 23:08