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

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

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

Определения

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

Φ : N → P ( 1 ) , {displaystyle Phi :mathbb {N} o mathbf {P} ^{(1)},}

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

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