3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Joseph Webb Nov 11 '13 at 20:00
  • $\begingroup$ and what do you mean by spurious moves? I've never heard that phrase before. $\endgroup$ – Joseph Webb Nov 11 '13 at 20:01
  • $\begingroup$ It's not a technical phrase. It just means moves which are necessary for the computation, but can help with ensuring that the machine makes infinitely many left moves. $\endgroup$ – Yuval Filmus Nov 11 '13 at 20:02
  • $\begingroup$ 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. $\endgroup$ – Joseph Webb Nov 11 '13 at 23:08
  • 1
    $\begingroup$ I can't follow you. If you have a concrete suggestion, you can try to prove that it works. If you can't seem to prove that it works, perhaps it doesn't. $\endgroup$ – Yuval Filmus Nov 11 '13 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.