Blum's speedup theorem

A theorem showing that, for suitable computable functions and complexity measures, every program computing the function can be outperformed by an equivalent program by arbitrarily large computable factors.

Blum complexity measure: A program-cost measure satisfying Blum's two axioms: costs are defined exactly for computations that halt, and cost comparisons are decidable. The theorem's guarantee applies only to complexity measures with these two properties.
Computational complexity: The study of resources such as time and space required to compute functions or solve problems. Blum's theorem is a foundational result about program resource costs.
Blum's speedup theorem examples: Constructed computable functions whose programs admit arbitrarily large computable-factor improvements under suitable complexity measures. Examples make the theorem's abstract, measure-dependent claim concrete.
Manuel Blum: A computer scientist who developed axiomatic measures of program complexity and proved the speedup theorem. Blum introduced the framework and theorem that bear his name.
Diagonalization: A proof technique that constructs an object by differing from each item in an enumerated list at a selected point. The speedup proof builds a function that defeats successive candidate programs.
Program semantics: The mathematical meaning of a program, typically characterized by the outputs it produces and whether it halts. Equivalent programs in the theorem compute the same function despite differing costs.
Computability theory: The mathematical study of which functions and problems can be computed by algorithms. The theorem separates computability from the possibility of stable resource efficiency.
Axiomatic complexity theory: An approach that studies resource measures through formal properties rather than one machine-specific cost definition. Blum's axioms made the theorem apply across a broad class of complexity measures.
Program enumeration: An effective listing of programs, usually arranged so each program has a natural-number index. The proof uses program indices to compare each candidate with a later, faster equivalent.
Time complexity: A measure of the number of computational steps an algorithm takes as a function of input size. Running time is a familiar example of a Blum complexity measure.

Linked from 2 pages