Теорема Райса-Шапиро — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(снёс прошлый вариант статьи, переписываю заново)
(доказательство в одну сторону + философия)
Строка 1: Строка 1:
 +
Теорема Райса-Шапиро позволяет дать простое описание перечислимым свойствам языков.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 13: Строка 14:
 
Свойство языков <tex>A</tex> перечислимо тогда и только тогда, когда существует перечислимое множество образцов <tex>\Gamma</tex>, такое, что <tex>L</tex> удовлетворяет <tex>A</tex> тогда и только тогда, когда <tex>L</tex> удовлетворяет <tex>\Gamma</tex>.
 
Свойство языков <tex>A</tex> перечислимо тогда и только тогда, когда существует перечислимое множество образцов <tex>\Gamma</tex>, такое, что <tex>L</tex> удовлетворяет <tex>A</tex> тогда и только тогда, когда <tex>L</tex> удовлетворяет <tex>\Gamma</tex>.
 
}}
 
}}
 +
Доказательство в одну сторону тривиально: пусть <tex>\Gamma</tex> — перечислимое множество образцов. Будем обозначать за <tex>\Gamma_i</tex> образец с номером <tex>i</tex>, а за <tex>\Gamma_{ij}</tex> — элемент с номером <tex>j</tex> образца с номером <tex>i</tex>. Далее приведён код перечислителя <tex>A</tex>, который принимает на вход код перечислителя <tex>L</tex> и возвращает значение <tex>L \in A</tex>.
 +
 +
  A(L)
 +
    for t = 1 to <tex>\infty</tex>
 +
      for i = 1 to t
 +
        ok <tex>\leftarrow</tex> true
 +
        for j = 1 to <tex>|\Gamma_i|</tex>
 +
          if <tex>\lnot L|_t (\Gamma_{ij})</tex>
 +
            ok <tex>\leftarrow</tex> false
 +
        if ok
 +
          return true
 +
  
 
== Литература ==
 
== Литература ==
 
* ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
 
* ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)

Версия 18:29, 14 января 2013

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

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

Будем говорить, что язык удовлетворяет образцу [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 (рус.)