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

В статье не хватает ссылок на источники (см. рекомендации по поиску ). Информация должна быть проверяема , иначе она может быть удалена. Вы можете статью, добавив ссылки на авторитетные источники в виде сносок . ( 3 марта 2023 )