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

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

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

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

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

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

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