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

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

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

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

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

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

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

  • области определения и совпадают.
  • множество является разрешимым.