Axioms of Blum

In the theory of computational complexity, Bloom axioms are axioms that determine the properties of measures of complexity on a set of computable functions . These axioms were first formulated by Manuel Blum in 1967.

It is important that both Blum’s acceleration theorem and the gap theorem hold for any complexity measures satisfying these axioms. The best-known examples of such measures are runtime (TIME) and memory usage (SPACE).

Definitions

Blum's complexity measure is a couple $(\varphi ,\Phi )$ ${\ displaystyle (\ varphi, \ Phi)}$ consisting of Gödel numbering $\varphi$ ${\ displaystyle \ varphi}$ computable functions $\mathbf {P} ^{(1)}$ ${\ displaystyle \ mathbf {P} ^ {(1)}}$ and computable functions

\Phi :\mathbb {N} \to \mathbf {P} ^{(1)},

{\ displaystyle \ Phi: \ mathbb {N} \ to \ mathbf {P} ^ {(1)},}

satisfying the following axioms of Blum . We denote by $\varphi _{i}$ ${\ displaystyle \ varphi _ {i}}$ ith computable function according to Gödel numbering $\varphi$ ${\ displaystyle \ varphi}$ , and through $\Phi _{i}$ ${\ displaystyle \ Phi _ {i}}$ - computable function $\Phi (i)$ ${\ displaystyle \ Phi (i)}$ .

areas of definition $\varphi _{i}$ ${\ displaystyle \ varphi _ {i}}$ and $\Phi _{i}$ ${\ displaystyle \ Phi _ {i}}$ match up.
lots of $\{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\}$ ${\ displaystyle \ {(i, x, t) \ in \ mathbb {N} ^ {3} | \ Phi _ {i} (x) = t \}}$ is solvable .

Axioms of Blum

Definitions

More articles: