Linear speedup theorem

In computational complexity theory, the linear speedup theorem for Turing machines states that given any real c > 0 and any Turing machine solving a problem in time f(n), there is another machine that solves the same problem in time at most cf(n) + n + 2.^[1]

Proof

Here is a sketch proof for the case c = ½. Suppose the Turing machine M solves the problem in f(n) steps and that it has k tape symbols and s internal states. Construct a new machine M' with k³ tape symbols, each symbol representing a "chunk" of 3 adjacent symbols in machine M. The tape of machine M' is a compressed representation of the tape of machine M, with cell i for machine M' representing the chunk of cells 2i-1, 2i and 2i+1 of machine M (note that these chunks overlap). In one computation step, M' simulates the computation of M until M's head leaves the chunk cells to the left or right (this simulation can be done in a single step because M can be in no more than 3sk³ states without leaving the chunk or repeating a state). During this simulation M may accept, in which case M' also accepts, or M may loop, in which case M' does nothing (and so also loops).

A final subtlety is that, because the chunks can overlap, they may contain inconsistent symbols on the overlapping parts. In this case, the chunk closest to the current head position is the correct one. When transitioning from one chunk to another, the state of the Turing machine is used to remember the overlapping symbol from the starting chunk temporarily, until it can be copied into the corresponding position of the destination chunk.

The construction requires that each computation step in M' corresponds to at least 2 computation steps of M. So M' takes no more than f(n)/2 steps, after an initial linear number of steps to convert the input tape into the compressed representation.

This proof can be easily generalized to all values of c > 0 by using greater numbers of adjacent symbols per chunk. A similar technique, known as the "tape compression theorem", allows for a similar constant factor reduction in the space requirements of a Turing machine.

References