Blum's axioms

Show Summary Details

Quick Reference

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).

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.