Show that a Turingmachine with tapes that are infinite in both directions semi-decides the same languages as a classical TM. Apart from the entry-word, the tapes are filled with empty spaces and the head's on the first letter of the entry-word

Under "classical" TM we understand a TM that has a tape that starts at the first letter and is infinite at the right side.

I don't quite understand what to prove here. The only difference between the two TM's is that I can/can't hit the left border of the tape. I could make this scenario a rejected state in the double infinite TM because it can't happen on the single infinite TM.

Any tips?

  • 1
    $\begingroup$ Can you prove that there is a bijection between the integers and natural numbers? This proof can be done in a similar way with a few additional steps. $\endgroup$ – awillia91 Mar 28 at 19:19
  • $\begingroup$ I can do that but why do I need to proof it that way? What's the idea behind it? $\endgroup$ – Quotenbanane Mar 28 at 19:36
  • $\begingroup$ Think about the cells of the double sided tape being labelled by integers, and those of the single sided tape by natural numbers. Can you think of a way we could simulate the double sided tape with just one side? $\endgroup$ – awillia91 Mar 28 at 19:38

The intent of this assignment seems to be to demonstrate that allowing Turing Machines to treat the tape as infinite in both directions will not increase the computational power of the Turing Machine; in other words, that for any unbounded-tape TM, there exists an equivalent classical TM. This means you can't just "reject if we go too far to the left" on the unbounded-tape TM, because our proof has to be applicable to all unbounded-tape TMs, not just ones that conveniently do this.

Understanding the equivalence of these two definitions of TM is important because both definitions are widely used in the academia, and many proofs using TMs are easier on one of these models over the other. Knowing that they are equivalent allows one to pick the easier model for a given situation.

For a basic idea of how to prove these two models of computation equivalent, consider that shifting the entire contents of the tape to the right can be done by a classical TM, allowing it to dynamically claim more space on the left of existing tape contents as needed. You can utilize this behavior to simulate an unbounded-tape TM in a classical TM.


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.