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

Мера сложности Блюма — это пара ${\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\}}$ является разрешимым.