Изменения
Нет описания правки
{{Определение
|definition = Множество А <tex>A</tex> называется '''имунным''', если А <tex>A</tex> - бесконечное, для любого бесконечного перечислимого <tex>B</tex>, <tex>B \not \subset A</tex>.
}}
{{Определение
|definition = Множество <tex>A </tex> называется '''простым''', если <tex>A </tex> - перечислимое, бесконечное, и дополнение <tex>A </tex> - имунно.
}}
Рассмотрим все программы, каждая из них задает некоторый перечислимый язык, причем каждому перечислимому языку соответствует какая-то программа - его перечислитель.
Напишем следующую программу <tex>q</tex>:
q:
Множество <tex>E(q)</tex>, которое перечисляет эта программа:
* перечислимо;
* бесконечно (. Существует бесконечное количество бесконечных множеств. В каждом из них есть элемент <tex>x \geqslant 2 * i</tex>, где <tex>i </tex> - номер программы перечисляющей это множество.)
Дополнение этого множества <tex>\overline{E(q)}</tex>:
* бесконечно. Для первых <tex>k </tex> слов, множеству <tex>E(q) </tex> принадлежат не более <tex>\frac{k}{2}</tex>.* для любого перечислимого множества <tex>B</tex>, существует его элемент принадлежащий <tex>E(q)</tex>, и следовательно не принадлежащий <tex>\overline{E(q)}</tex>, <tex>\overline{E(q)} \not \subset A</tex>
Таким образом <tex>\overline{E(q)}</tex> --- имунно, а <tex>E(q)</tex> --- простое.
}}
