Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 3 / c

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, byThe 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.

Sincethere 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, establishingIt 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.