## Quick Reference

Two axioms in complexity theory, formulated by M. Blum. Let

*M*_{1},*M*_{2},…,*M** _{n}*,…

be an effective enumeration of the Turing machines and let *f** _{i}* be the partial recursive function of a single variable that is computed by

*M*

*. (For technical reasons it is simpler to think in terms of partial recursive functions than set (or language) recognizers.) if*

_{i}*F*_{1},*F*_{2},…,*F** _{n}*,…

is a sequence of partial recursive functions satisfying axiom 1:

*f** _{i}*(

*n*) is defined if and only if

*F*

*(*

_{i}*n*) is defined,

and axiom 2:

*F** _{i}*(

*x*) ≤

*y*is a recursive predicate of

*i*,

*x*, and

*y*,

then *F** _{i}*(

*n*) is a computational complexity measure and can be thought of as the amount of some “resource” consumed by

*M*

*in computing*

_{i}*f*

*(*

_{i}*n*). This notion represents a useful abstraction of the basic resources — time and space. Several remarkable theorems about computational complexity have been proved for any measure of resources satisfying the two axioms (see gap theorem, speedup theorem).

**From:**
Blum's axioms
in
A Dictionary of Computing »

*Subjects:*
Computing.