= 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> with
$$
\boxed{T_c(n)\leq\frac{T(n)}c+n+O(1).}
$$
The 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.<Computational Complexity, slides 1 by Paul W. Goldberg (2023)>[Slides 47–48, PDF pp. 62–63: statement for k > 1 and block simulation]{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)$.
\b[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.
Back to article page
