In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any k-tape Turing machine solving a problem in time f(n), there is another 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 ${\displaystyle k\geq 1}$ work tapes.

For single-tape Turing machines, linear speedup holds for machines with execution time at least ${\displaystyle n^{2}}$. It provably does not hold for machines with time ${\displaystyle t(n)\in \Omega (n\log n)\cap o(n^{2})}$.

The construction is based on packing several tape symbols of the original machine M into one tape symbol of the new machine N. It has a similar effect as using longer words and commands in processors: it speeds up the computations but increases the machine size. How many old symbols are packed into a new symbol depends on the desired speed-up.

Suppose the new machine packs three old symbols into a new symbol. Then the alphabet of the new machine is ${\displaystyle \Sigma \cup \Sigma ^{3}}$: it consists of the original symbols and the packed symbols. The new machine has the same number k > 1 of tapes. A state of N consists of the following components:

The new machine N starts with encoding the given input into a new alphabet (that is why its alphabet must include ${\displaystyle \Sigma }$). For example, if the input to 2-tape M is on the left, then after the encoding the tape configuration of N is on the right:

The new machine packs three old symbols (e.g., the blank symbol _, the symbol a, and the symbol b) into a new symbol (here (_,a,b)) and copies it the second tape, while erasing the first tape. At the end of the initialization, the new machine directs its head to the beginning. Overall, this takes 2n + 3 steps.

After the initialization, the state of N is ${\displaystyle (q_{0};~~~?,(\_,\_,\_),?;~~~?,(\_,a,b),?;~~~[1,1])}$, where the symbol ${\displaystyle ?}$ means that it will be filled in by the machine later; the symbol ${\displaystyle [1,1]}$ means that the head of the original machine points to the first symbols inside ${\displaystyle (\_,\_,\_)}$ and ${\displaystyle (\_,a,b)}$. Now the machine starts simulating m = 3 transitions of M using six of its own transitions (in this concrete case, there will be no speed up, but in general m can be much larger than six). Let the configurations of M and N be: