= Solution
Use <Turing machines> with a two-way read-only <input> tape, bounded by endmarkers, and a fixed finite number of read-write work tapes over a fixed finite <alphabet>. Work-tape cells count towards <space complexity>; the read-only <input> does not. For <input> length $n$, use $O(\log(n+2))$ to include the small-length cases.
\b[$\mathrm{Logspace}$, or <L>, is the class of <formal languages> decided by a deterministic such machine using at most $c\log(n+2)$ work-tape cells for some fixed constant $c$.] It must halt on every <input> and accept exactly the members.
\b[$\mathrm{NLogspace}$, or <NL>, is the class of <formal languages> accepted by a <Nondeterministic Turing machine> with the same work-space bound on every computation branch.] An <input> is accepted if and only if at least one branch accepts. One may require all branches to halt: the <configuration graph> has only a <polynomial> number of <vertices>, so a <logarithmic space> counter can stop any branch that has taken more steps than that bound. If an accepting computation exists, one exists with no repeated <Turing machine configuration>, so this convention does not change the <complexity class>.
In standard <space complexity> notation,
$$
\boxed{\mathrm L=\mathrm{DSPACE}(O(\log n)),\qquad
\mathrm{NL}=\mathrm{NSPACE}(O(\log n)).}
$$
Back to article page
