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