A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which are decided by deterministic or nondeterministic log-space Turing machines, respectively. The two-way Turing machines may move their head on the input tape into two-way (left and right directions) while the one-way Turing machines are not allowed to move the input head on the input tape to the left.

Hartmanis and Mahaney have investigated the classes $1L$ and $1NL$ of languages recognizable by deterministic one-way log-space Turing machine and nondeterministic one-way log-space Turing machine, respectively. They have shown that $1NL \subseteq L$ if and only if $L=NL$.

See the paper here(it is free to download):


I wonder this question:

Is $L \subset 1NL$ when $L \neq NL$?

Moreover, I wonder this another question:

Is there any reference that shows whether at least one of the options $L \subset 1NL$ or $1NL \subset L$ or $L = 1NL$ should be true?

Thanks in advance!!!


If they can only move the head right, they are equivalent to finite automata.

| cite | improve this answer | |
  • $\begingroup$ They can only move the head right on the input tape: they can move two-way on the work tapes. I vote for your answer anyway. Do not hesitate to be more specific, please. Thanks in advance!!! $\endgroup$ – Frank Vega Mar 8 at 20:03
  • 2
    $\begingroup$ @FrankVega, I suggest editing the question to clarify the definition of those complexity classes. $\endgroup$ – D.W. Mar 9 at 1:14
  • $\begingroup$ @D.W.: Is better now? $\endgroup$ – Frank Vega Mar 9 at 1:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.