Linear speedup theorem

For every constant $c>0$, a deterministic multitape Turing machine with more than one tape and time complexity bounded by $T(n)$ has an equivalent machine with the same tape count and bound $T(n)/c+n+O(1)$, allowing a larger finite control and tape alphabet. Blocks of old symbols become single new symbols, and finite control implements blocks of old steps. The linear overhead accounts for initial input packing. If $T(n)/n\to \infty$, the overhead can be absorbed to obtain any fixed constant speed increase for sufficiently large inputs. This does not supply unlimited speed increases for operations on fixed hardware.^[ref]