304
правки
Изменения
м
Будем говорить, что язык удовлетворяет образцу <tex>A</tex>, если он содержит все слова <tex>A</tex>. Также будем говорить, что язык удовлетворяет множеству образцов, если он удовлетворяет хотя бы одному образцу из этого множества.
вынес определения
Теорема Райса-Шапиро позволяет дать простое описание перечислимым свойствам языков. Заметим, что вычислимо работать с произвольными языками возможности нет, поэтому далее неявно подразумевается, что все рассматриваемые языки являются [[Перечислимые языки|перечислимыми]].
{{Определение
|definition=
'''Свойством программ''' называется множество текстов программ
}}{{Определение
|definition=
'''Образцом''' называется конечное множество слов.
}}{{Определение
|definition=
'''Язык <tex>L</tex> удовлетворяет образцу <tex>A</tex>''', если <tex>L</tex> содержит все элементы <tex>A</tex>
}}{{Определение
|definition=
'''Язык <tex>L</tex> удовлетворяет множеству образцов <tex>X</tex>''', если <tex>L</tex> удовлетворяет хотя бы одному образцу <tex>A \in X</tex>.
}}
Заметим, что образцы являются конструктивными объектами, следовательно, можно говорить о разрешимых и перечислимых множествах образцов.
