192
правки
Изменения
м
Нет описания правки
{{Определение
|definition=
'''Образцом''' (англ. ''pattern'') называется конечное множество слов, объединённое определённым общим свойством.
}}
{{Определение
|definition=
'''Язык <tex>L</tex> удовлетворяет свойству <tex>A</tex>''', если <tex>L \in A</tex> ( этот язык содержится в <tex>A</tex>).
}}
{{Определение
|definition=
'''Язык <tex>L</tex> удовлетворяет образцу <tex>AX</tex>''', если <tex>L</tex> содержит все элементы <tex>AX</tex>.
}}
{{Определение
|definition=
'''Язык <tex>L</tex> удовлетворяет множеству образцов <tex>X\Gamma</tex>''', если <tex>L</tex> удовлетворяет хотя бы одному образцу <tex>A X \in X\Gamma</tex>.
}}
Теорема Райса-Шапиро позволяет дать простое описание перечислимым свойствам языков. Заметим, что вычислимо работать с произвольными языками возможности нет, поэтому далее неявно подразумевается, что все рассматриваемые языки являются [[Перечислимые языки|перечислимыми]].
Райса-Шапиро
|statement=
Свойство языков <tex>A</tex> перечислимо тогда и только тогда, когда существует перечислимое множество образцов <tex>\iff \exists\Gamma</tex>, такое, что <tex>: L</tex> удовлетворяет <tex>\in A</tex> тогда и только тогда, когда <tex>\iff L</tex> удовлетворяет <tex>\subseteq \Gamma</tex>.
}}
== См. также==
* [[m-сводимость]]
* [[Примеры_неразрешимых_задач:_проблема_соответствий_Поста | Проблема соответствий Поста]]
* [[Неразрешимость исчисления предикатов первого порядка]]
== Источники информации ==
