Простой набор
-
Определение простых множеств
- Простое множество — это вычислимо перечислимое множество, которое является ко-бесконечным и не содержит бесконечных подмножеств, которые являются вычислимыми.
- Простые множества являются примерами вычислимых множеств, которые не могут быть вычислены.
-
Связь с проблемой Поста
- Эмиль Леон Пост разработал простые множества в поисках не полной по Тьюрингу системы счисления.
- Вопрос о существовании таких множеств известен как проблема Поста.
- Пост доказал, что простые множества не могут быть вычислены, но не смог доказать, что проблема остановки не сводится к ним по Тьюрингу.
-
Формальные определения и свойства
- W_BOSe обозначает стандарт равномерно распределенного по времени перечисления всех вычислимых множеств.
- Иммунные множества — это бесконечные множества, для которых каждое подмножество не является вычислимым.
- Простые множества — это вычислимо перечислимые множества, дополнения которых обладают иммунитетом.
- Эффективно простые множества — это вычислимо перечислимые множества, компоненты которых эффективно укрепляют иммунитет.
- Гипериммунные множества — это бесконечные множества, дополнения которых не являются вычислимо доминирующими.
- Гиперпростые множества — это простые множества, дополнения которых являются гипериммунными.
-
Рекомендации по форматированию
- В статье приведены рекомендации по форматированию библиографических описаний и HTML-кода.