Past exam of the computer science course of the University of Oxford / 2015 / Computational complexity / 2 / b / Solution

The linear speedup theorem concerns multitape Turing machines whose finite control and tape alphabet may change. Formally, for $k>1$, if a deterministic $k$-tape Turing machine decides $A$ within $T(n)$ steps on every input of length $n$, then for every constant $c>0$ there is a deterministic $k$-tape Turing machine deciding the same formal language withThe additive constant is independent of $n$; in the usual normalized formulation the bound is $T(n)/c+n+2$, with the integer-rounding convention absorbed in the constant.^[ref]

The construction packs a fixed number of old tape symbols into each new symbol and uses a larger finite control to simulate blocks of old steps. Initial input packing explains the additive linear term. If $T(n)/n\to \infty$, choosing a larger constant $c$ makes the total asymptotic time complexity an arbitrarily small constant multiple of $T(n)$.

It does not promise arbitrary speed increases on fixed hardware. Larger packed symbols and transition tables cease to be single constant-cost hardware operations without limit. The theorem also retains the input-reading overhead. It is a statement about changing the abstract machine description and primitive operations, rather than an unlimited implementation optimization on one processor.