Введение

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

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

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

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

В дальнейшем обозначает стандартное однородное перечисление всех наборов с. е. Множество называется иммунным, если оно бесконечно, но для каждого индекса , у нас есть или эквивалентно: нет бесконечного подмножества, которое является c. e Множество называется простым, если оно c. e. и его комплемент иммунен. Множество называется эффективно невосприимчивым, если оно бесконечно, но существует рекурсивная функция, такая, что для каждого индекса , у нас есть множество, называемое эффективно простым, если оно c. e. и его комплемент эффективно невосприимчивый. Каждый эффективно простой набор является простым и Тьюринговым. Множество называется гипериммунным, если оно бесконечно, но не является вычислимо доминирующим, где список членов в порядке. Множество называется гиперпростым, если оно простое, а его комплемент гипериммунный.