# How much slower is a Turing Machine if you only give it one end of the tape to work with?

Turing Machines start with the input string and tape head in the "middle" of a tape that extends infinitely in either direction. Suppose instead that the tape head starts at the "far left" of the tape: the tape extends infinitely to the right, but the tape head can never move further left than its starting position.

This "one-sided Turing Machine" is clearly Turing complete, but I wonder if this new model ever has inferior time complexity to a regular Turing machine.

Are there any languages that require asymptotically more time to decide on a one-sided Turing machine than a regular Turing machine? If so, what is the maximum asymptotic speedup required on a one-sided TM?

Edit: I think I missed a bit there, since the string to be recognized is put on the tape all together, rather than spread out, which means you could potentially need an additional $4n$ steps to spread it out before starting the simulation. There may be a better general way, of course.
• @HagenvonEitzen, the "software" approach shouldn't be too terrible. A simple approach would be to add a third "track" to the two-track tape I've described, which is set to $0$ everywhere but the first position, which is set to $1$. Again, I make no claim to attain the smallest constant factor, which would be a much trickier/interesting problem. Commented Jun 29, 2013 at 23:35