Тюринг машиналарын жылдамдату үшін таспа символдарының күрделілігін арттыру

Speeding up Turing machines by increasing tape symbol complexity
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.

For single tape Turing machines, linear speedup holds for machines with execution time at least It provably does not hold for machines with time showed that for
nondeterministic single tape Turing machines of time complexity linear speedup can be achieved without increasing the alphabet.

Regan 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 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.