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

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

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

Простые множества были изобретены Эмилем Леоном Постом в поисках неполного по Тьюрингу рекурсивно перечислимого множества. Существуют ли такие наборы - это проблема Поста . Сообщение было доказать две вещи, чтобы получить свой результат, является то , что простой набор, скажем А , не Тьюринг-сводится к пустому множеству, и что 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}) <f (e)}$
• Набор называется эффективно простым, если он рекурсивно перечислим, а его дополнение эффективно невосприимчиво. Каждый эффективно простой набор прост и полон по Тьюрингу.${\ Displaystyle S \ substeq \ mathbb {N}}$
• Множество называется гипериммунным, если оно бесконечно, но не подчиняется вычислимо, где - список членов по порядку. ^[2]${\ Displaystyle I \ substeq \ mathbb {N}}$${\ displaystyle I}$${\ displaystyle p_ {I}}$${\ displaystyle p_ {I}}$${\ displaystyle I}$
• Набор называется гиперпростым, если он простой и его дополнение гипериммунно. ^[3]${\ Displaystyle S \ substeq \ mathbb {N}}$

Заметки [ править ]

Ссылки [ править ]

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