Blooms axiom

I beräkningskomplexitetsteori är Blooms axiom axiom som definierar egenskaper hos komplexitetsmått på en uppsättning beräkningsbara funktioner . Dessa axiom formulerades först av Manuel Blum 1967.

Det är viktigt att både Blums accelerationssats och gapsatsen är sanna för alla komplexitetsmått som uppfyller dessa axiom. De mest kända exemplen på sådana åtgärder är exekveringstiden (TIME) och mängden minne som används (SPACE).

Definitioner

Bloom-komplexitetsmåttet är paret som består av Gödel-uppräkningen av beräkningsbara funktioner och den beräkningsbara funktionen $(\varphi ,\Phi )$ $\varphi$ ${\displaystyle \mathbf {P} ^{(1)))$

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

uppfyller följande Blooms axiom . Vi betecknar med den i- :te beräkningsbara funktionen enligt Gödel-numreringen , och med — den beräkningsbara funktionen . $\varphi _{i}$ $\varphi$ ${\displaystyle \Phi _{i))$ $\Phi (i)$

domänerna för och sammanfaller. $\varphi _{i}$ ${\displaystyle \Phi _{i))$
uppsättningen är lösbar . ${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\))$