Bloomovy axiomy

V teorii výpočetní složitosti jsou Bloomovy axiómy axiómy , které definují vlastnosti mír složitosti na souboru vypočitatelných funkcí . Tyto axiomy poprvé formuloval Manuel Blum v roce 1967.

Je důležité, aby jak Blumova věta o zrychlení, tak věta o mezeře platila pro všechny míry složitosti, které splňují tyto axiomy. Nejznámějšími příklady takových měření jsou doba provádění (TIME) a množství použité paměti (SPACE).

Definice

Bloomova míra složitosti je dvojice sestávající z Gödelova výčtu vypočitatelných funkcí a vyčíslitelné funkce $(\varphi ,\Phi )$ $\varphi$ ${\displaystyle \mathbf {P} ^{(1)))$

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

splňující následující Bloomovy axiomy . Označujeme i - tou vyčíslitelnou funkcí podle Gödelova číslování a — vyčíslitelnou funkcí . $\varphi _{i}$ $\varphi$ ${\displaystyle \Phi _{i))$ $\Phi (i)$

domény a shodují se. $\varphi _{i}$ ${\displaystyle \Phi _{i))$
sada je řešitelná . ${\displaystyle \{(i,x,t)\in \mathbb {N} ^{3}|\Phi _{i}(x)=t\))$