1632
правки
Изменения
м
{{==Теорема|statementо существовании простого множества=Существует простое множество.|proof=
Рассмотрим программу <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> ничего не печатать, если такого числа не найдется.
<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>
В <tex>E(q)</tex> будет содержаться первый [[#Лемма 1|По первой лемме]] существует элемент множества <tex>B</tex> не превосходящий , принадлежащий <tex>2 iE(q)</tex>, где и, следовательно, не принадлежащий <tex>i</tex> — номер перечислителя множества <tex>B\overline{E(q)}</tex>.
Cуществует элемент Среди чисел от <tex>B1</tex> принадлежащий до <tex>k</tex> множеству <tex>E(q)</tex>, и следовательно принадлежат не принадлежащий более <tex>\dfrac{k}{2}</tex>.Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\dfrac{k}{2}</tex>.
{{Лемма
|statement=<tex>\overline{E(q)}</tex> — бесконечно.
|proof=
Среди чисел от <tex>1</tex> до <tex>k</tex>, множеству <tex>E(q)</tex> принадлежат не более <tex>\frac{k}{2}</tex>.
Следовательно <tex>\overline{E(q)}</tex> принадлежат не менее <tex>\frac{k}{2}</tex>
}}
Вернемся к доказательству теоремы== См.также ==*[[Перечислимые языки]]*[[m-сводимость]]== Примечания ==
Получаем:<references />
<tex>\overline{E(q)}</tex> == Источники информации ==* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7* Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — иммунноМ.:Мир, 1972. С. 141-143.<tex>E(q)<* [https://tex> — простоеen.wikipedia.org/wiki/Simple_set Wikipedia {{---}} Simple set]
}}[[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория:Разрешимые и перечислимые языки]]
rollbackEdits.php mass rollback
{{Определение
|definition = Множество натуральных чисел <tex>A</tex> называется '''иммунным'''(англ. ''immune set''), если <tex>A</tex> — бесконечное, для любого бесконечного перечислимого множества <tex>B</tex>, <tex>B \not \subset A</tex>оно бесконечно и не содержит бесконечных перечислимых подмножеств.
}}
{{Определение
|definition = Множество натуральных чисел <tex>A</tex> называется '''простым'''(англ. '' simple set''), если <tex>A</tex> — перечислимое, бесконечное, и дополнение <tex>\overline{A}</tex> — {{---}} иммунное.
}}
Рассмотрим все программы.
Для некоторого [[Перечислимые_языки | перечислимого языка, ]] какая-то из них является его перечислителем.Рассмотрим программу <tex>q</tex>:
Обозначим <tex>E(q)</tex> — множество, которое перечисляет эта программа.
Докажем несколько лемм , из которых будет очевидна правильность утверждения теоремы.===Лемма 1===
Необходимо, чтобы перечислимое множество <tex>E(q)</tex> имело иммунное дополнение. Это означает, что <tex>E(q)</tex> должно пересекаться с любым бесконечным перечислимым множеством.
{{Лемма
|id= ==lemma==
|about=1
|statement=Для любого бесконечного перечислимого множества <tex>B</tex> существует его элемент, принадлежащий <tex>E(q)</tex>.
|proof=
По построению, для любого множества <tex> B </tex> в <tex>E(q)</tex> будет содержаться первый его элемент не меньший <tex>2 i</tex>, где <tex>i</tex> {{---}} номер перечислителя множества <tex>B</tex>.
}}
===Лемма 2===
{{Лемма
|id= ==lemma==|about=2 |statement=Для любого бесконечного перечислимого множества <tex>B</tex>верно, существует его элемент принадлежащий что <tex>B \not \subset \overline{E(q)}</tex>.
|proof=
}}
===Лемма 3==={{Лемма|id= ==lemma==|about=3|statement=Для любого перечислимого множества <tex>B</tex> <tex>B \not \subset \overline{E(q)}</tex>{{---}} бесконечно.
|proof=
}}
Теперь докажем теорему.
{{Теорема
|statement=Существует простое множество.
|proof=
[[#Лемма 2|Из леммы (2)]] и [[#Лемма3|из леммы (3)]] следует, что <tex>\overline{E(q)}</tex> {{---}} иммунно.
По построению <tex>E(q)</tex> перечислимо, его дополнение иммунно и, [[#Лемма 3|по лемме (3)]], бесконечно, а значит {{---}} оно простое.
}}
Простые множества являются примерами перечислимых множеств, не являющихся <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>. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы <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>. .
