Blum's axioms

Blum's axioms Two axioms in complexity theory, formulated by M. Blum. Let M₁,M₂,…,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_i. (For technical reasons it is simpler to think in terms of partial recursive functions than set (or language) recognizers.) If F₁,F₂,…,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_i in computing 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).