Низкий (вычислимость)

В теории вычислимости степень Тьюринга [ X ] низкая , если скачок Тьюринга [ X '] равен 0'. Множество является низким, если оно имеет низкую степень. Поскольку каждое множество вычислимо по своему переходу, любое нижнее множество вычислимо в 0 ', но скачок множеств, вычислимых в 0 ', может ограничивать любую степень, рекурсивно перечислимую в 0 ' (инверсия скачка Шенфилда). X Низкое значение говорит о том, что его скачок X ′ имеет наименьшую возможную степень с точки зрения сводимости по Тьюрингу для скачка множества.

Существуют различные сопутствующие свойства низкой степени:

• Степень является низкой _n, если ее n-й прыжок является n-м прыжком из 0.
• Множество X является обобщенно низким, если оно удовлетворяет условию X ′ ≡ _T X + 0′, то есть: если его скачок имеет наименьшую возможную степень.
• Степень d является обобщенной ниже n, если ее n-й прыжок является (n-1)-м прыжком соединения d с 0'.

В более общем смысле, свойства множеств, которые описывают их вычислительную слабость (при использовании в качестве оракула Тьюринга), называются общим термином « свойства малости» .

По теореме о низком базисе Йокуша и Соаре любой непустой $\Pi _{1}^{0}$ класс в $2^{\omega }$ содержит набор низкой степени. Это означает, что, хотя низкие множества вычислительно слабы, они все же могут выполнять такие задачи, как вычисление завершения арифметики Пеано . На практике это позволяет ограничить вычислительную мощность объектов, необходимых для теоретико-рекурсивных конструкций: например, тех, которые используются при анализе теоретико -доказательной силы теоремы Рамсея .

См. также

• Высокая (вычислимость)
• Теорема о низком базисе

Ссылки

• Соаре, Роберт И. (1987). Рекурсивно перечислимые множества и степени. Исследование вычислимых функций и вычислимо порождённых множеств . Перспективы математической логики. Берлин: Springer-Verlag . ISBN  3-540-15299-7 . Збл   0667.03030 .
• Нис, Андре (2009). Вычислимость и случайность . Оксфордские руководства по логике. Том. 51. Оксфорд: Издательство Оксфордского университета. ISBN  978-0-19-923076-1 . Збл   1169.03034 .