304
правки
Изменения
м
Теорема Райса-Шапиро позволяет дать простое описание перечислимым свойствам языков. Заметим, что вычислимо работать с произвольными языками возможности нет, поэтому далее неявно подразумевается, что все рассматриваемые языки являются [[Перечислимые языки|перечислимыми]].
эстетические и концептуальные правки
{{Определение
|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>.
}}
Теорема Райса-Шапиро позволяет дать простое описание перечислимым свойствам языков. Заметим, что вычислимо работать с произвольными языками возможности нет, поэтому далее неявно подразумевается, что все рассматриваемые языки являются [[Перечислимые языки|перечислимыми]].
Заметим, что образцы являются конструктивными объектами, следовательно, можно говорить о разрешимых и перечислимых множествах образцов.
