Базисная теорема (вычислимость)

В теории вычислимости существует ряд базисных теорем . Эти теоремы показывают, что определенные виды множеств всегда должны иметь некоторые члены, которые, с точки зрения степени Тьюринга , не слишком сложны. Одно семейство базисных теорем касается непустых эффективно замкнутых множеств (т. е. непустых $\Pi _{1}^{0}$ множества в арифметической иерархии ); эти теоремы изучаются в рамках классической теории вычислимости. Другое семейство базисных теорем касается непустых аналитических множеств светлой грани (т.е. $\Sigma _{1}^{1}$ в аналитической иерархии ); эти теоремы изучаются в рамках гиперарифметической теории .

Эффективно закрытые множества

Эффективно замкнутые множества являются предметом изучения классической теории вычислимости. Эффективно замкнутое множество — это множество всех путей через некоторое вычислимое поддерево двоичного дерева. $2^{<\omega }$. Эти множества замкнуты в топологическом смысле как подмножества канторова пространства. $2^{\omega }$, а дополнение к эффективному замкнутому множеству является эффективным открытым множеством в смысле эффективных польских пространств . Клини доказал в 1952 году, что существует непустое, эффективно замкнутое множество без вычислимой точки (Купер 1999, стр. 134). Базисные теоремы показывают, что должны существовать точки, которые не «слишком далеки» от вычислимости в неформальном смысле.

Класс ${\mathcal {C}}\subseteq 2^{\omega }$ является основой эффективно замкнутых множеств, если каждое непустое эффективно замкнутое множество включает член ${\mathcal {C}}$ (Купер 2003, стр. 329). Базисные теоремы показывают, что определенные классы являются базовыми в этом смысле. Эти теоремы включают (Купер 1999, стр. 134):

• Теорема о низкой базисности : каждое непустое $\Pi _{1}^{0}$ множество имеет член низкой степени.
• Теорема о безгипериммунном базисе : каждое непустое $\Pi _{1}^{0}$ в множестве есть член со степенью отсутствия гипериммунитета .
• Теорема о базисе : каждое непустое $\Pi _{1}^{0}$ В наборе есть член рекурсивно перечислимой (пере) степени .

Вот, набор $X\subseteq \mathbb {N}$ низкий , если это прыжок Тьюринга $X'=\varnothing '$, степень проблемы остановки . $X$ имеет степень отсутствия гипериммунитета, если каждая сумма $X$-вычислимая функция $f\colon \mathbb {N} \to \mathbb {N}$ доминирует полная вычислимая функция $g$ (значение $f(n)\leq g(n)$ для всех $n$).

Никакие две из трех приведенных выше теорем не могут быть объединены для множества непротиворечивых пополнений PA (или просто EFA ; степени Тьюринга одинаковы). Единственная степень Тьюринга, позволяющая вычислить последовательное завершение PA, равна 0'. Однако теорему о низком базисе и теорему о безгипериммунном базисе можно комбинировать с избеганием конусов, т. е. для каждого невычислимого X мы можем выбрать элемент (как в теореме), который не вычисляет X . Теоремы также релятивизируют произвольную вещественную величину.

Аналитические наборы Lightface

Существуют также базисные теоремы для светлого лица. $\Sigma _{1}^{1}$ наборы. Эти базисные теоремы изучаются в рамках гиперарифметической теории . Одной из теорем является теорема о базисе Ганди, которая аналогична теореме о низком базисе. показывает Базисная теорема Ганди , что каждое непустое $\Sigma _{1}^{1}$ в множестве есть элемент, который является гиперарифметически низким, то есть его гиперпереход имеет ту же гиперстепень (а для теоремы даже ту же степень Тьюринга), что и множество Клини . ${\mathcal {O}}$.

Ссылки

• Купер, С.Б. (1999). «Теория локальной степени», в «Справочнике по теории вычислимости» , Э.Р. Гриффор (ред.), Elsevier, стр. 121–153. ISBN   978-0-444-89882-1
• - (2003), Теория вычислимости , Чепмен-Холл. ISBN   1-584-88237-9

Внешние ссылки

• Симпсон, С. « Обзор базисных теорем », слайды из книги «Теория вычислимости и основы математики» , Токийский технологический институт, 18–20 февраля 2013 г.