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, where k > 1.[1] [2] 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.[1]
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
\Sigma\cup\Sigma3
The new machine N starts with encoding the given input into a new alphabet (that is why its alphabet must include
\Sigma
[# || _ || a || b || b || a || b || b || a || _ || ...] | [# || (_,_,_) || (_,_,_) || (_,_,_) || ...] | ||
[# || _ || _ || _ || _ || _ || _ || _ || _ || _ || ...] | [# || (_,a,b) || (b,a,b) || (b,a,_) || ...] |
After the initialization, the state of N is
(q0;~~~?,(\,\,\),?;~~~?,(\,a,b),?;~~~[1,1])
?
[1,1]
(\,\,\)
(\,a,b)
[# || _ || _ || b || b || a || '''b''' || b || a || _ || ...] | [# || (_,a,b) || (b,a,b) || ('''b''',_,_) || ...] | ||
[# || _ || a || b || '''b''' || a || b || b || _ || _ || ...] | [# || (_,_,'''b''') || (b,a,b) || (b,a,_) || ...] |
(q;~~~?,(\,\,b),?;~~~?,(b,\,\),?;~~~[3,1])
?
(q;~~~\#,(\,\,b),(b,a,b);~~~(b,a,b),(b,\,\),(\,\,\);~~~[3,1])
[# || _ || _ || _ || _ || _ || '''b''' || b || a || _ || ...] | [# || (_,a,b) || ('''b''',_,_) || (_,_,_) || ...] | ||
[# || _ || a || b || '''b''' || _ || _ || _ || _ || _ || ...] | [# || (_,_,_) || (_,_,'''b''') || (b,a,_) || ...] |
(q';~~~?,(\,\,b),?;~~~?,(b,\,\),?;~~~[3,1])
Initialization requires 2n + 3 steps. In the simulation, 6 steps of N simulate m steps of M. Choosing m > 6c produces the running time bounded by
f(n)/c+2n+3.
The theorem as stated above also holds forTuring machines with 1-way, read-only input tapeand
k\ge1
For single-tape Turing machines, linear speedup holds for machines with execution time at least
n2
t(n)\in\Omega(nlogn)\capo(n2)
The proof of the speedup theorem clearly hinges on the capability to compress storage by replacing the alphabet with a larger one.Geffert[4] showed that fornondeterministic single-tape Turing machines of time complexity
T(n)\gen2
Regan[5] considered a property of a computational model called information vicinity. This property is related to the memory structure: a Turing machine has linear vicinity, while a Kolmogorov-Uspenskii machine and other pointer machines have an exponential one. Regan’s thesis is that the existence of linear speedup has to do with having a polynomial information vicinity. The salient point in this claim is that a model with exponential vicinity will not have speedup even if changing the alphabet is allowed (for models with a discrete memory that stores symbols). Regan did not, however, prove any general theorem of this kind. Hühne [6] proved that if we require the speedup to be obtained by an on-line simulation (which is the case for the speedup on ordinary Turing machines), then linear speedup does not exist on machines with tree storage.