Простой набор

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

Связь с проблемой Поста

Простые множества были разработаны Эмилем Леоном Постом в поисках неполного по Тьюрингу в.п. множества. Существуют ли такие множества, известно как проблема Поста . Пост должен был доказать две вещи, чтобы получить свой результат: что простое множество не вычислимо и что K , проблема остановки , не сводится по Тьюрингу к A. A В первой части ему это удалось (что очевидно по определению), но в другой части ему удалось доказать лишь редукцию «многие единицы» .

Идея Поста была подтверждена Фридбергом и Мучником в 1950-х годах с использованием нового метода, названного методом приоритетов . Они дают простую (и, следовательно, невычислимую) конструкцию множества, но не позволяющую вычислить проблему остановки.

Формальные определения и некоторые свойства

Далее, $W_{e}$ обозначает стандартный равномерно в.п. список всех в.п. наборов.

• Набор $I\subseteq \mathbb {N}$ называется иммунным, если $I$ бесконечно, но для любого индекса $e$, у нас есть $W_{e}{\text{ infinite}}\implies W_{e}\not \subseteq I$. Или, что то же самое: не существует бесконечного подмножества $I$ это се.
• Набор $S\subseteq \mathbb {N}$ называется простым, если он представляет собой ce и его комплемент невосприимчив.
• Набор $I\subseteq \mathbb {N}$ называется эффективно иммунным, если $I$ бесконечно, но существует рекурсивная функция $f$ такая, что для каждого индекса $e$, у нас это есть $W_{e}\subseteq I\implies \#(W_{e})<f(e)$.
• Набор $S\subseteq \mathbb {N}$ называется эффективно простым, если он представляет собой ce и его комплемент эффективно иммунен. Каждое эффективно простое множество просто и по Тьюрингу.
• Набор $I\subseteq \mathbb {N}$ называется гипериммунным, если $I$ бесконечно, но $p_{I}$ не является вычислимо доминируемым, где $p_{I}$ это список членов $I$ чтобы.
• Набор $S\subseteq \mathbb {N}$ называется гиперпростым, если он прост и его дополнение гипериммунно.

Ссылки

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