Изменения

'''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> ничего не печатать, если такого числа не найдется.

Простые множества являются примерами перечислимых множеств, не являющихся <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. с. 58, c. 62. ISBN 5-900916-36-7]</ref>. .