Аксиомы Блюма

В теории сложности вычислений аксиомы Блюма — это аксиомы, которые определяют свойства мер сложности на множестве вычислимых функций. Впервые эти аксиомы были сформулированы Мануэлем Блюмом в 1967 году.

Важным является тот факт, что и теорема Блюма об ускорении, и теорема о промежутке верны для любых мер сложности, удовлетворяющих этим аксиомам. Наиболее известными примерами таких мер являются время выполнения (TIME) и объем используемой памяти (SPACE).

Определения

Мера сложности Блюма — это пара $(\varphi, \Phi)$, состоящая из гёделевой нумерации $\varphi$ вычислимых функций $\mathbf{P}^{(1)}$ и вычислимой функции

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

удовлетворяющей следующим аксиомам Блюма. Мы обозначаем через $\varphi_i$ i-ю вычислимую функцию согласно гёделевской нумерации $\varphi$, а через $\Phi_i$ — вычислимую функцию $\Phi(i)$.

• области определения $\varphi_i$ и $\Phi_i$ совпадают.
• множество $\{(i,x,t) \in \mathbb{N}^3 | \Phi_i(x) = t\}$ является разрешимым.