Изменения
→Теорема о простом множестве
Рассмотрим программу <tex>q</tex>:
'''function''' <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>
}}
Простые множества являются примерами перечислимых множеств, не являющихся m-полными. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы m-полным <ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 2012. с. 58, c. 62. ISBN 5-900916-36-7]</ref>. .
== См. также ==
*[[Перечислимые языки]]
