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

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

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

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

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

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

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

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

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

Рекомендации

• Купер, С. Б. (1999). «Теория местных дипломов», в Справочник по теории вычислимости, E.R. Griffor (ed.), Elsevier, стр. 121–153. ISBN  978-0-444-89882-1
• — (2003), Теория вычислимости, Чепмен-Холл. ISBN  1-584-88237-9

внешняя ссылка

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