304
правки
Изменения
доказательство в одну сторону + философия
Теорема Райса-Шапиро позволяет дать простое описание перечислимым свойствам языков.
{{Определение
|definition=
Свойство языков <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)
for t = 1 to <tex>\infty</tex>
for i = 1 to t
ok <tex>\leftarrow</tex> true
for j = 1 to <tex>|\Gamma_i|</tex>
if <tex>\lnot L|_t (\Gamma_{ij})</tex>
ok <tex>\leftarrow</tex> false
if ok
return true
== Литература ==
* ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)
