# TM with double-infinity tape semi-decides the same languages as classical TM

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?

• 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. – awillia91 Mar 28 at 19:19
• I can do that but why do I need to proof it that way? What's the idea behind it? – Quotenbanane Mar 28 at 19:36
• 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? – awillia91 Mar 28 at 19:38