Теорема Райса-Шапиро

Определение:

Образцом называется конечное множество слов.

Будем говорить, что язык удовлетворяет образцу [math]A[/math], если он содержит все слова [math]A[/math]. Также будем говорить, что язык удовлетворяет множеству образцов, если он удовлетворяет хотя бы одному образцу из этого множества.

Заметим, что образцы являются конструктивными объектами, следовательно, можно говорить о разрешимых и перечислимых множествах образцов.

Теорема (Райса-Шапиро):

Свойство языков [math]A[/math] перечислимо тогда и только тогда, когда существует перечислимое множество образцов [math]\Gamma[/math], такое, что [math]L[/math] удовлетворяет [math]A[/math] тогда и только тогда, когда [math]L[/math] удовлетворяет [math]\Gamma[/math].

Литература

• Верещагин Н. К., Шень A. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
• Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.: Издательский дом «Вильямс», 2008. — С. 528 — ISBN 978-5-8459-1347-0 (рус.)