= Solution
Let a deterministic <Turing machine> $M$ decide $A$ with at most $s(n)=c\log(n+2)$ work-tape cells. Fix an <input> $x$ of length $n$. A <Turing machine configuration> is determined by the control state, the read-only <input>-head position, the work-tape contents, and the work-head positions. For one work tape with <alphabet> $\Gamma$, their number is bounded, up to harmless fixed factors, by
$$
|Q|(n+2)(s(n)+1)|\Gamma|^{s(n)}.
$$
The factors respectively count the state, <input>-head position, work-head position and work-tape contents. With a fixed number $r$ of work tapes, replace the last two factors by $(s(n)+1)^r|\Gamma|^{rs(n)}$ if each tape is allowed $s(n)$ cells; this still gives a valid <polynomial> upper bound. Two-way work tapes only change fixed factors in the head-position bounds.
Since
$$
|\Gamma|^{c\log_2(n+2)}
=(n+2)^{c\log_2|\Gamma|},
$$
there are at most $(n+2)^d$ <Turing machine configurations> for some constant $d$ depending on $M$. If a deterministic computation repeats one of its <Turing machine configurations> on the fixed <input>, all subsequent steps repeat too, so it never halts. But $M$ is a decider. It therefore halts before any repetition and takes at most a <polynomial> number of steps. The same <Turing machine> is consequently a <polynomial-time algorithm>, establishing
$$
\boxed{\mathrm{Logspace}\subseteq\mathrm{PTime}.}
$$
It would be incorrect to count just the work-tape contents and omit the read-only <input>-head position; that position is part of the <Turing machine configuration> even though the <input> itself is not charged as work space.
Back to article page
