Linear speedup theorem

Key takeaways

Linear speedup theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Linear speedup theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Linear speedup theorem from memory before moving on to harder problems.

Reference excerpt

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 k ≥ 1 {\displaystyle k\geq 1} work tapes. For single-tape Turing machines, linear speedup holds for machines with execution time at least n 2 {\displaystyle n^{2}} . It provably does not hold for machines with time t ( n ) ∈ Ω ( n log ⁡ n ) ∩ o ( n 2 ) {\displaystyle t(n)\in \Omega (n\log n)\cap o(n^{2})} .

Proof 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 Σ ∪ Σ 3 {\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 state of M; for each tape, three packed symbols that describe the packed symbol under the head, the packed symbol on the left, and the packed symbol on the right; and for each tape, the original head position within the packed symbol under the head of N. 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 ( q 0 ; ? , ( _ , _ , _ ) , ? ; ? , ( _ , a , b ) , ? ; [ 1 , 1 ] ) {\displaystyle (q_{0};~~~?,(\_,\_,\_),?;~~~?,(\_,a,b),?;~~~[1,1])} , where the symbol ? {\displaystyle ?} means that it will be filled in by the machine later; the symbol [ 1 , 1 ] {\displaystyle [1,1]} means that the head of the original machine points to the first symbols inside ( _ , _ , _ ) {\displaystyle (\_,\_,\_)} and ( _ , a , b ) {\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:

where the bold symbols indicate the head position. The state of N is ( q ; ? , ( _ , _ , b ) , ? ; ? , ( b , _ , _ ) , ? ; [ 3 , 1 ] ) {\displaystyle (q;~~~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])} . Now the following happens:

N moves right, left, left, right. After the four moves, the machine N has all its ? {\displaystyle ?} filled, and its state becomes ( q ; # , ( _ , _ , b ) , ( b , a , b ) ; ( b , a , b ) , ( b , _ , _ ) , ( _ , _ , _ ) ; [ 3 , 1 ] ) {\displaystyle (q;~~~\#,(\_,\_,b),(b,a,b);~~~(b,a,b),(b,\_,\_),(\_,\_,\_);~~~[3,1])}

Now N updates its symbols and state according to m = 3 transitions of the original machine. This may require two moves (update the current symbol and update one of its adjacent symbols). Suppose the original machine moves as follows (with the corresponding configuration of N on the right):

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Linear speedup theorem

Start with the simplest possible case. Write down what Linear speedup theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Linear speedup theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Linear speedup theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Linear speedup theorem

In research: Linear speedup theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Linear speedup theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Linear speedup theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Theorems in computational complexity theory, so understanding it makes those chapters shorter.
In everyday life: Look for Linear speedup theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Linear speedup theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Linear speedup theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Linear speedup theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Linear speedup theorem in simple terms?

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 Tu…

Why does Linear speedup theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Linear speedup theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Linear speedup theorem.