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

В теории сложности вычислений аксиомы Блюма — это аксиомы, которые определяют свойства мер сложности на множестве вычислимых функций. Впервые эти аксиомы были сформулированы Мануэлем Блюмом в 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\}$ является разрешимым.