Простой набор - Simple set

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

Отношение к проблеме Поста

Простые наборы были разработаны Эмиль Леон Пост в поисках неполного по Тьюрингу рекурсивно перечислимого множества. Существуют ли такие наборы, известно как Проблема с постом. Чтобы получить результат, Пост должен был доказать две вещи: во-первых, простой набор, скажем, А, не сводится по Тьюрингу к пустому множеству, и что K, то проблема остановки, не сводится по Тьюрингу к А. Он преуспел в первой части (что очевидно по определению), но в другой части ему удалось только доказать много-одно сокращение.

Это было подтверждено Фридбергом и Мучником в 1950-х годах с использованием новой техники, названной приоритетный метод. Они дают простую (и, следовательно, нерекурсивную) конструкцию для набора, но не решают проблему остановки.^[1]

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

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

Примечания

1. Nies (2009) стр.35
2. Nies (2009) стр.27
3. Nies (2009) стр.37

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

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