Two axioms in complexity theory, formulated by M. Blum. Let
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
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).