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

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

• 1 Связь с проблемой Post
• 2 Формальные определения и некоторые свойства
• 3 Примечания
• 4 Ссылки

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

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

• Набор $I\; \subseteq \; N\; \{\backslash \; displaystyle\; I\; \backslash \; substeq\; \backslash \; mathbb\; \{N\}\}$называется иммунным, если $I\; \{\backslash \; displaystyle\; I\}$бесконечно, но для каждого индекса $е\; \{\backslash \; displaystyle\; e\}$, у нас есть $W\; e\; бесконечный\; ⟹\; W\; e\; ⊈\; I\; \{\backslash \; displaystyle\; W\_\; \{e\}\; \{\backslash \; text\; \{infinite\}\}\; \backslash \; подразумевает\; W\_\; \{e\}\; \backslash \; not\; \backslash \; подэтап\; I\}$. Или, что эквивалентно: не существует бесконечного подмножества $I\; \{\backslash \; displaystyle\; I\}$, которое было бы рекурсивно перечислимым.
• Множество $S\; \subseteq \; N\; \{\backslash \; displaystyle\; S\; \backslash \; substeq\; \backslash \; mathbb\; \{N\}\}$называется простым, если он рекурсивно перечислим и его дополнение невосприимчиво.
• Набор $I\; \subseteq \; N\; \{\backslash \; displaystyle\; I\; \backslash \; Substeq\; \backslash \; mathbb\; \{N\}\}$называется эффективно иммунным, если $I\; \{\backslash \; displaystyle\; I\}$бесконечно, но существует рекурсивная функция $f\; \{\backslash \; displaystyle\; f\}$таким образом, чтобы для каждого индекса $e\; \{\backslash \; displaystyle\; e\}$мы имели, что .
• Набор $S\; \subseteq \; N\; \{\backslash \; displaystyle\; S\; \backslash \; substeq\; \backslash \; mathbb\; \{N\}\}$называется эффективно простым, если он рекурсивно перечислим и его дополнение эффективно иммунно.. Каждый эффективно простой набор прост и полон по Тьюрингу.
• Набор $I\; \subseteq \; N\; \{\backslash \; displaystyle\; I\; \backslash \; substeq\; \backslash \; mathbb\; \{N\}\}$называется гипериммунным, если $I\; \{\backslash \; displaystyle\; I\}$бесконечно, но $p\; I\; \{\backslash \; displaystyle\; p\_\; \{I\}\}$не доминирует вычислимо, где $p\; I\; \{\backslash \; displaystyle\; p\_\; \{I\}\}$- это список элементов $I\; \{\backslash \; displaystyle\; I\}$по порядку.
• Набор $S\; \subseteq \; N\; \{\backslash \; displaystyle\; S\; \backslash \; substeq\; \backslash \; mathbb\; \{N\}\}$называется гиперпростым, если он простой, а его дополнение гипериммунно.

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