[Solved]: Proving that the language of TMs with finite left head moves is undecidable

Problem Detail: 

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.

Asked By : Joseph Webb

Answered By : Yuval Filmus

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.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/17892

 Ask a Question

 Download Related Notes/Documents