Simulations between Turing machines I've got a question. How can i simulate Turing machine with a double-sided infinite tape by a Turing machine with one-sided infinite tape? The condition is, that the simulation of one step of the first machine must be equal to O(1) steps of second machine. Do you have any idea, how to do this?
As I understand your question, the double-sided machine has a tape indexed by $\mathbb{Z}$ and the one-sided has a tape indexed by $\mathbb{N}$.

The question then boils down to finding a bijection f between the two sets st. $\forall z \in \mathbb{Z}: |f(z) - f(z+1)| &lt; k$ for some constant k. Can you find such a bijection:

Hint: k = 3 is sufficient.