A read-only-input logarithmic-space machine

A read-only-input machine has one input tape containing $x$, whose head may move in either direction but whose cells are never changed, and finitely many read/write work tapes. Its work space on inputs of length $n$ is the number of visited work-tape cells, not the input cells. A deterministic machine decides when it halts on every input; a nondeterministic machine decides when every branch halts and some branch accepts exactly the inputs in the language.

It is a logspace machine when its work space is $O({\log }_2(n+2))$. The $n+2$ convention also covers the empty input. This is a work-space convention, distinct from the all-tapes convention in The classes DTIME, NTIME, DSPACE, and NSPACE.