WikiSort.ru - Не сортированное

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.