Изменения
йдется
{{Определение
|definition = Множество натуральных чисел <tex>A</tex> называется '''простым''' (англ. '' simple set''), если <tex>A</tex> — перечислимое, бесконечное и дополнение <tex>\overline{A}</tex> {{---}} иммунное.
}}
==Теорема о простом множестве=существовании простого множества={{Теорема|statement=Существует простое множество.|proof=
Рассмотрим все программы.
Для некоторого [[Перечислимые_языки | перечислимого языка]] какая-то из них является его перечислителем.
Рассмотрим программу <tex>q</tex>:
<tex>q</tex>(): '''for ''' <tex>(TL = 1\ \ldots +\infty)</tex> '''for ''' <tex>(i = 1\ \ldots TL)</tex> запустить <tex>i</tex>-ую в [[Главные нумерации|главной нумерации]] программу на <tex>TL</tex> шагов напечатать первый <tex>x</tex>, который вывела эта программа, такой что <tex>x \geqslant 2 i;</tex> ничего не печатать, если такого числа не найдется.
|statement=<tex>\overline{E(q)}</tex> {{---}} бесконечно.
|proof=
Среди чисел от <tex>1</tex> до <tex>k</tex> множеству <tex>E(q)</tex> принадлежат не более <tex>\fracdfrac{k}{2}</tex>.Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\fracdfrac{k}{2}</tex>.
}}
Теперь докажем теорему.
{{Теорема
|statement=Существует простое множество.
|proof=
[[#Лемма 2|Из леммы (2)]] и [[#Лемма3|из леммы (3)]] следует, что <tex>\overline{E(q)}</tex> {{---}} иммунно.
}}
Простые множества являются примерами перечислимых множеств, не являющихся <tex>m</tex>-полными<ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012. с. 58. ISBN 5-900916-36-7]</ref>. Именно так и возникло понятие простого множества: Пост (англ. ''Post'' ) искал пример перечислимого неразрешимого множества, которое не было бы <tex>m</tex>-полным<ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012.c. 62. ISBN 5-900916-36-7]</ref>. .
== См. также ==
*[[Перечислимые языки]]
*[[m-сводимость]]
== Примечания ==
<references />
== Источники информации ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория:Разрешимые и перечислимые языки]]
