Linear speedup theorem

In computational complexity theory, the linear speedup theorem for Turing machines states that one can always make a Turing machine complete its task with less steps, by allowing it to use more symbols (i.e. a larger alphabet) on its tape(s).

Formally, it states that given any real c > 0 and any Turing machine using k tape(s) solving a problem in time f(n), there is another such k-tape machine that solves the same problem in time at most f(n)/c + 2n + 3, where k > 1. If the original machine is non-deterministic, then the new machine is also non-deterministic. The constants 2 and 3 in 2n + 3 can be lowered, for example, to n + 2.

The theorem also holds for Turing machines with 1-way, read-only input tape and work tapes.

For single-tape Turing machines, linear speedup holds for machines with execution time at least . It provably does not hold for machines with time .