Blums axioms
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).
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).
More From encyclopedia.com
Primitive Recursion , primitive recursive function A function that can be obtained from certain initial functions by a finite number of applications of composition and pri… Computer Science , The term Computer Science encompasses three different types of research areas: computability, efficiency, and methodology.
General Introduction
Compu… Equation , equation An expression that asserts the equality of two terms. To be precise, an equation has the following form. Let Σ be a signature and let t1(X1,… Function , A function is a mathematical relationship between two sets of real numbers. These sets of numbers are related to each other by a rule that assigns ea… inverse , inverse
1. (converse) of a binary relation R. A derived relation R–1 such that whenever x R y then y R–1 x
where x and y are arbitrary elements of th… Domain , Domain
The domain of a relation is the set that contains all the first elements, x, from the ordered pairs (x,y) that make up the relation. In mathem…
You Might Also Like
NEARBY TERMS
Blums axioms