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

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

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

Определения

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

$\mathrm{\Phi }:\mathbb{N}\to {𝐏}^{(1)},$

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

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