patternMinor
Proving that the language of TMs with finite left head moves is undecidable
Viewed 0 times
provingleftthefinitemovesundecidablewithtmsheadlanguage
Problem
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.
\{ \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.
Solution
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.)
Context
StackExchange Computer Science Q#17892, answer score: 2
Revisions (0)
No revisions yet.