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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определения[править | править вики-текст]

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

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

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