304
правки
Изменения
доказательство леммы 2
}}
{{Лемма
|statement=
Пусть <tex>A</tex> — перечислимое свойство, <tex>G \in A</tex>. Тогда существует конечное множество <tex>H \in A</tex>, которое является подмножеством <tex>G</tex>.
|proof=
Строим доказательство от противного. Пусть <tex>G \in A</tex>, и любое конечное подмножество <tex>G</tex> не удовлетворяет свойству <tex>A</tex>, <tex>K</tex> — перечислимое неразрешимое множество. Определим следующую функцию:
* <tex>f(x, y) = 0</tex>, если за <tex>x</tex> шагов перечисления <tex>K</tex> слово <tex>y</tex> не появилось.
* <tex>f(x, y) = x \in G</tex> иначе.
Заметим, что если <tex>y \in K</tex>, то <tex>f(x, y)</tex> распознаёт некоторое конечное подмножество <tex>G</tex> и всё множество <tex>G</tex> иначе. Эта функция тривиальным образом разрешима, построим с её помощью разрешитель <tex>K</tex>. Аналогично доказательству первой леммы, подготовим программу <tex>g</tex>:
g(x):
return f(x, y)
После этого параллельно запустим проверки <tex>y \in K</tex> и <tex>L(g) \in A</tex>. Аналогично, данная процедура разрешает множество <tex>K</tex>. Но <tex>K</tex> не является разрешимым, получено противоречие.
}}
== Литература ==
* ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)
