Blums axioms

views updated

Blum's axioms Two axioms in complexity theory, formulated by M. Blum. Let M1,M2,…,Mn,…

be an effective enumeration of the Turing machines and let fi be the partial recursive function of a single variable that is computed by Mi. (For technical reasons it is simpler to think in terms of partial recursive functions than set (or language) recognizers.) If F1,F2,…,Fn,…

is a sequence of partial recursive functions satisfying

axiom 1:

fi(n) is defined if and only if Fi(n) is defined,

and axiom 2:

Fi(x) ← y is a recursive predicate of i, x, and y,

then Fi(n) is a computational complexity measure and can be thought of as the amount of some “resource” consumed by Mi in computing fi(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).