Math 2.0

Computer science Computational complexity: resources and classes Theorem

Blum's speedup theorem

Builds on Computable functionTuring machine

Statement

Let φ0,φ1,…\varphi_0, \varphi_1, \ldots be an acceptable numbering of the partial computable functions ℕ→ℕ\N \to \N. Let Φ0,Φ1,…\Phi_0, \Phi_1, \ldots be a Blum complexity measure for it: each Φi\Phi_i is a partial function ℕ→ℕ\N \to \N such that

  1. Φi(x)\Phi_i(x) is defined if and only if φi(x)\varphi_i(x) is defined;
  2. the set of triples (i,x,m)(i, x, m) with Φi(x)=m\Phi_i(x) = m is decidable.

Let r ⁣:ℕ×ℕ→ℕr \colon \N \times \N \to \N be a total computable function. Then there is a total computable function f ⁣:ℕ→{0,1}f \colon \N \to \set{0, 1} with the following property. For every index ii with φi=f\varphi_i = f there is an index jj with φj=f\varphi_j = f and r(x,Φj(x))≤Φi(x)for all but finitely many x.r\big(x, \Phi_j(x)\big) \le \Phi_i(x) \quad \text{for all but finitely many } x.

Remarks

The running time of a Turing machine program, Φi(x)\Phi_i(x) = the number of steps of program ii on input xx, is a Blum complexity measure, and so is the space used. For example, take r(x,t)=2tr(x, t) = 2^t. The theorem gives a function ff such that every program for ff can be replaced by another program for ff that is exponentially faster on almost all inputs. So ff has no fastest program, even up to a large factor. The proof is a diagonal construction that cancels programs which run too fast on chosen inputs. The function ff built in the proof is artificial, and the theorem says nothing about natural problems.

Going deeper

For a student

The theorem works for any Blum complexity measure, so it is a fact about abstract complexity, not about Turing machines in particular. It shows that the complexity of a function cannot always be defined as the cost of a best program. Complexity classes are therefore defined by resource bounds, as in the time hierarchy theorem, rather than by optimal algorithms. The gap theorem of Borodin is another result of abstract complexity theory with a similar flavour.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph
Computable function, concept, no evidence levelComputable functionconceptTuring machine, concept, no evidence levelTuring machineconceptBlum's speedup theorem, statement, no evidence levelBlum's speedup theoremstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Computable function concept
  2. Turing machine concept
  3. Blum's speedup theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem
About this page
TagF53XQ3F2SN
URIm2://F53XQ3F2SN
Kindstatement, theorem
WritingW0 stub
MSC68Q15, 03D15
StatusThis copy of the site has no build data. Run m2 status F53XQ3F2SN.
AboutComputable function
UsesComputable function, Turing machine
Same as
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.