Материал из Викиконспекты
| Определение: |
| Множество [math]A[/math] называется иммунным, если [math]A[/math] - бесконечное, для любого бесконечного перечислимого [math]B[/math], [math]B \not \subset A[/math]. |
| Определение: |
| Множество [math]A[/math] называется простым, если [math]A[/math] - перечислимое, бесконечное, и дополнение [math]A[/math] - иммунно. |
| Теорема: |
Существует простое множество. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим все программы, каждая из них задает некоторый перечислимый язык, причем каждому перечислимому языку соответствует какая-то программа - его перечислитель.
Напишем следующую программу [math]q[/math]:
[math]q[/math]:
for [math](TL = 1\ \ldots +\infty)[/math]
for [math](i = 1\ \ldots TL)[/math]
запустить [math]i[/math]-ую в главной нумерации программу на [math]TL[/math] шагов
напечатать первый [math]x[/math], который вывела эта программа, такой что [math]x \geqslant 2 i[/math]
Множество [math]E(q)[/math], которое перечисляет эта программа:
- перечислимо;
- бесконечно. Существует бесконечное количество бесконечных множеств. В каждом из них есть элемент [math]x \geqslant 2 * i[/math], где [math]i[/math] - номер программы перечисляющей это множество.
Дополнение этого множества [math]\overline{E(q)}[/math]:
- бесконечно. Для первых [math]k[/math] слов, множеству [math]E(q)[/math] принадлежат не более [math]\frac{k}{2}[/math].
- для любого перечислимого множества [math]B[/math], существует его элемент принадлежащий [math]E(q)[/math], и следовательно не принадлежащий [math]\overline{E(q)}[/math], [math]\overline{E(q)} \not \subset A[/math]
Таким образом [math]\overline{E(q)}[/math] --- иммунно, а [math]E(q)[/math] --- простое. |
| [math]\triangleleft[/math] |
