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