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
