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

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

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

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

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

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

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

Примечания

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

• Соаре, Роберт 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.