192
правки
Изменения
Нет описания правки
{{Определение
|definition=
'''Образцом''' (англ. ''pattern'') называется конечное множество слов, объединённое [[Свойства_перечислимых_языков._Теорема_Успенского-Райса|свойством]].
}}
Заметим, что образцы являются конструктивными объектами, следовательно, можно говорить о разрешимых и перечислимых множествах образцов.
Райса-Шапиро
|statement=
Свойство языков <tex>A</tex> перечислимо тогда и только тогда, когда существует перечислимое множество образцов <tex>\iff \exists\Gamma</tex>, такое, что <tex>: L</tex> удовлетворяет <tex>\in A</tex> тогда и только тогда, когда <tex>\iff L</tex> удовлетворяет <tex>\subseteq \Gamma.</tex>.
}}
<tex>\Rightarrow</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>=</tex> ''true'' '''for''' j = 1 '''to''' <tex>|\Gamma_i|</tex> '''if''' <tex>\lnot L|_t (\Gamma_{ij})</tex> ok <tex>=</tex> ''false'' '''if''' ok '''return''' ''true'' <tex>\Leftarrow</tex>:Для доказательства в другую сторону будем использовать две леммы, приведённые выше. Полуразрешитель для множества образцов, удовлетворяющих <tex>\Gamma</tex> строится следующим образом: для каждого образца <tex>\gamma</tex> строится текст программы 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>\Gamma</tex>, что и требовалось доказать. == См. также== * [[m-сводимость]]* [[Примеры_неразрешимых_задач:_проблема_соответствий_Поста | Проблема соответствий Поста]]* [[Неразрешимость исчисления предикатов первого порядка]] == Источники информации ==
* ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Примеры неразрешимых задач]]
