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

Теорема Райса-Шапиро позволяет дать простое описание перечислимым свойствам языков.

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

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

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

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

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

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

Доказательство в одну сторону тривиально: пусть [math]\Gamma[/math] — перечислимое множество образцов. Будем обозначать за [math]\Gamma_i[/math] образец с номером [math]i[/math], а за [math]\Gamma_{ij}[/math] — элемент с номером [math]j[/math] образца с номером [math]i[/math]. Далее приведён код перечислителя [math]A[/math], который принимает на вход код перечислителя [math]L[/math] и возвращает значение [math]L \in A[/math].

 A(L)
   for t = 1 to [math]\infty[/math]
     for i = 1 to t
       ok [math]\leftarrow[/math] true
       for j = 1 to [math]|\Gamma_i|[/math]
         if [math]\lnot L|_t (\Gamma_{ij})[/math]
           ok [math]\leftarrow[/math] false
       if ok
         return true

Литература

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