## Blums axioms

**Blum's axioms** 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*be the partial recursive function of a single variable that is computed by

_{i}*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).

#### More From encyclopedia.com

## Blums axioms

#### You Might Also Like

#### NEARBY TERMS

**Blums axioms**