Let $M$ be a one-band TM and $w$ a word. We say that M tries to move the head over the left margin of the band if, while the head is in the leftmost position of $w$, the TM $M$ tries to move to the left.

Show that the language

$ LEFT_{TM} = \{<M,w> | $ M is a TM of the type above $\}$

is not decidable.

How can I show that such a language is not decidable?

I was thinking about using the TM $A$ which accepts any input and reduce it to $LEFT_{TM}$, but I'm not sure how. I would appreciate a nudge in the right direction.

  • $\begingroup$ @D.W. Sorry for not being clear, improved the question. $\endgroup$ – GeomForFun May 31 '18 at 19:27
  • $\begingroup$ I encourage you to spend more time trying approaches to the problem before asking here, and show us in the question what you've tried. You should try to reduce another language that you know is undecidable to this language. Most folks probably won't be very interested in solving your exercise for you, but show us what progress you've made and where specifically you got stuck, and perhaps we can give you assistance. $\endgroup$ – D.W. May 31 '18 at 20:20

You can reduce the halting problem to your problem. Roughly speaking, the reduction goes along the following lines:

Given a Turing machine $T$, construct a Turing machine $T'$ which simulates $T$ but never ventures to the left of the starting symbol. If $T$ halts, it then proceeds to go all the way to the left, until it goes beyond the starting symbol.

If you can do this, then you will have shown that LEFT is undecidable.

So how do you construct the machine $T'$? The difficult part is to somehow arrange that it never goes to the left of the starting symbol. Fortunately, this is essentially equivalent to showing that Turing machines with a one-sided infinite tape are equivalent to Turing machines with a two-sided infinite tape. You can look this up in many sources, or come up with a simulation of your own. There are many different ways to do it. Be creative!

One thing which might be unclear is what it means to simulate $T$ without going to the left of the starting symbol. What if $T$ wants to go to the left of the starting symbol? We are not looking for a literal simulation. Rather, we want to simulate each step of $T$ using a series of steps in $T'$, in such a way that the state of $T$ can be read from the state of $T'$. As a simple example, you can think of a Turing machine over the tape alphabet $\{0,1\}$ which simulates a Turing machine with tape alphabet $\{00,01,10,11\}$ by using two cells to store each symbol. We are looking for something similar: simulating a two-sided infinite tape using a one-sided infinite tape.

  • $\begingroup$ I'm not sure I can follow. $\endgroup$ – GeomForFun May 31 '18 at 19:58
  • $\begingroup$ Unfortunately, that's the best I can do. Perhaps you can contact a TA. $\endgroup$ – Yuval Filmus May 31 '18 at 19:59
  • $\begingroup$ My question is rather how to choose $f$ such that $f(<M,w>) = <M', w'>$ such that $<M', w'> \in LEFT$, once I have that I think the conclusion comes by contradiction. $\endgroup$ – GeomForFun May 31 '18 at 20:10
  • $\begingroup$ The function $f$ is $f(\langle T,w \rangle) = \langle T',w \rangle$. I suggest looking at some examples. $\endgroup$ – Yuval Filmus May 31 '18 at 20:11
  • $\begingroup$ So $T'$ is the concatenation of $HALT$ and $T$ ? $\endgroup$ – GeomForFun May 31 '18 at 20:26

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.