2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

It's not clear to me whether you care about constant factors. The complexity can be worse by at most a factor of two. Given a one-ended Turing machine, simulate a standard turing machine by letting the odd positions be the ones on the right and the even positions the ones on the left. Then moving one position on the simulated machine corresponds to moving two on the one-ended machine, which is a factor of two worse. Crossing between left and right at the center is obviously cheap. I don't know if there are languages actually requiring a factor of two.

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.

$\endgroup$
  • $\begingroup$ Also, I think either the machine needs to be amended with an end-of-tape detector in "hardware" or you need a special symbol as "software " end-of-tape marker. $\endgroup$ – Hagen von Eitzen Jun 29 '13 at 22:48
  • $\begingroup$ @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. $\endgroup$ – dfeuer Jun 29 '13 at 23:35

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.