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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Райса-Шапиро)
(не показаны 32 промежуточные версии 5 участников)
Строка 1: Строка 1:
== Определение образца ==
+
{{Определение
 +
|definition=
 +
'''Образцом''' (англ. ''pattern'') называется конечное множество слов, объединённое [[Свойства_перечислимых_языков._Теорема_Успенского-Райса|свойством]].
 +
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть <tex>\gamma=\{\langle x_1,y_1\rangle,\langle x_2,y_2\rangle,\ldots ,\langle x_n,y_n\rangle\}</tex>.<br />
+
'''Язык <tex>L</tex> удовлетворяет свойству <tex>A</tex>''', если <tex>L \in A</tex> ( этот язык содержится в <tex>A</tex>).
Тогда <tex>\gamma</tex> называется образцом.
 
 
}}
 
}}
 
== Свойство образца ==
 
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть <tex>A_{\gamma}=\{p | p(x_1)=y_1 \wedge p(x_2)=y_2 \wedge \ldots \wedge p(x_n)=y_n\}</tex>, где <tex>\langle x_i, y_i\rangle \in \gamma</tex>.<br />
+
'''Язык <tex>L</tex> удовлетворяет образцу <tex>X</tex>''', если <tex>L</tex> содержит все элементы <tex>X</tex>.
Тогда <tex>A_{\gamma}</tex> называется свойством образца <tex>\gamma</tex>.
 
 
}}
 
}}
 
+
{{Определение
== Лемма о перечислимости свойства образца ==
+
|definition=
 
+
'''Язык <tex>L</tex> удовлетворяет множеству образцов <tex>\Gamma</tex>''', если <tex>L</tex> удовлетворяет хотя бы одному образцу <tex>X \in \Gamma</tex>.
{{Лемма
 
|statement =
 
Свойство <tex>A_{\gamma}</tex> перечислимо для любого образца <tex>\gamma</tex>.
 
|proof =
 
Построим полуразрешитель <tex>A_{\gamma}</tex>:
 
<tex>q(p):</tex>
 
  for <tex>\langle x_i, y_i\rangle \in \gamma</tex>
 
      if <tex>p(x_i) \not= y_i</tex>
 
          while True
 
  return 1
 
Полуразрешителя достаточно для доказательства перечислимости.
 
 
}}
 
}}
  
== Лемма о перечислимости свойства перечислимого множества образцов ==
 
  
 
{{Лемма
 
{{Лемма
|statement =
+
|statement=
Пусть <tex>\Gamma</tex> {{---}} перечислимое множество образцов, <tex>A_{\Gamma} = \bigcup\limits_{\gamma \in \Gamma}{A_{\gamma}}</tex>.
+
Пусть <tex>A</tex> перечислимое свойство языков, <tex>G \in A</tex>. Тогда верно следствие: <tex>G \subset H \Rightarrow H \in A</tex>.
Тогда <tex>A_{\Gamma}</tex> {{---}} перечислимо.
+
|proof=
|proof =
+
Строим доказательство от противного. Пусть <tex>G \in A</tex>, <tex>G \subset H</tex>, <tex>H \notin A</tex>, <tex>K</tex> — перечислимое неразрешимое множество. Построим следующую вычислимую функцию:
Построим полуразрешитель <tex>A_{\Gamma}</tex>:
+
<tex>f(x, y) = \begin{cases}
<tex>q(p):</tex>
+
x \in H & y \in K\\
  for <tex>k = 1\ldots +\infty</tex>
+
x \in G & y \notin K
      for <tex>\gamma \in \Gamma[1..k]</tex>
+
\end{cases}</tex>
          if <tex>(p \in A_{\gamma})|_{TL(k)}</tex>
 
              return 1
 
Полуразрешителя достаточно для доказательства перечислимости.
 
}}
 
  
 +
Вычисляется эта функция следующим образом: параллельно запускаем проверки <tex>x \in G</tex> и <tex>y \in K</tex>. Если <tex>x \in G</tex>, то <tex>x \in H</tex>, следовательно, функция возвращает единицу вне зависимости от <tex>y</tex>. Если <tex>y \in K</tex>, то запускаем проверку <tex>x \in H</tex>.
  
== Теорема Райса-Шапиро ==
+
Разрешим множество <tex>K</tex>с помощью этой функции. Для проверяемого элемента <tex>y</tex> подготовим программу <tex>g</tex>:
  
{{Теорема
+
  <tex>g(x):</tex>
|statement =
+
    '''if''' <tex>x \in H</tex>
Свойство функций <tex>A</tex> перечислимо тогда и только тогда, когда <tex>\exists \Gamma: A = A_{\Gamma}</tex>, где <tex>\Gamma</tex> {{---}} перечислимое множество образцов.
+
      '''return''' <tex>y \in K</tex>
|proof =
+
    '''if''' <tex>x \in G</tex>
<tex>\Leftarrow</tex>
+
      '''return''' <tex>y \notin K</tex>
  
Очевидно (перебор по TL).
+
После этого запустим параллельно проверки <tex>y \in K</tex> и <tex>L(g) \in A</tex>. Если <tex>y \in K</tex>, то первая проверка завершится. Иначе функция <tex>g</tex> задаёт язык <tex>G</tex>, который обладает свойством <tex>A</tex>, следовательно, вторая проверка завершится, сигнализируя о том, что <tex>y \notin K</tex>. Но <tex>K</tex> не является разрешимым множеством, получено противоречие.
 +
}}
  
  
<tex>\Rightarrow</tex>
 
 
Здесь нам потребуются две вспомогательные леммы.
 
 
{{Лемма
 
{{Лемма
|statement =
+
|statement=
Пусть <tex>A</tex> {{---}} перечислимое свойство функций, <tex>g \in A</tex>, <tex>h</tex> {{---}} продолжение <tex>g</tex>.
+
Пусть <tex>A</tex> перечислимое свойство, <tex>G \in A</tex>. Тогда существует конечное множество <tex>H \in A</tex>, которое является подмножеством <tex>G</tex>.
Тогда <tex>h \in A</tex>.
+
|proof=
|proof =
+
Строим доказательство от противного. Пусть <tex>G \in A</tex>, и любое конечное подмножество <tex>G</tex> не удовлетворяет свойству <tex>A</tex>, <tex>K</tex> — перечислимое неразрешимое множество. Определим следующую функцию:
Докажем от противного.
+
* <tex>f(x, y) = false</tex>, если за <tex>x</tex> шагов перечисления <tex>K</tex> появилось слово <tex>y</tex>.
Пусть <tex>g \in A</tex>, <tex>h</tex> {{---}} продолжение <tex>g</tex>, <tex>h \notin A</tex>.
+
* <tex>f(x, y) = x \in G</tex> иначе.
 +
Заметим, что если <tex>y \in K</tex>, то <tex>f(x, y)</tex> распознаёт некоторое конечное подмножество <tex>G</tex> и всё множество <tex>G</tex> иначе. Эта функция тривиальным образом разрешима, построим с её помощью разрешитель <tex>K</tex>. Аналогично доказательству первой леммы, подготовим программу <tex>g</tex>:
  
Рассмотрим перечислимое и неразрешимое множество <tex>K</tex> и следующую программу:
+
  g(x):
 +
    '''return''' f(x, y)
  
<tex>V(n, x) =
+
После этого параллельно запустим проверки <tex>y \in K</tex> и <tex>L(g) \in A</tex>. Аналогично, данная процедура разрешает множество <tex>K</tex>. Но <tex>K</tex> не является разрешимым, получено противоречие.
  \begin{cases}
+
}}
    h(x)\text{, if $n \in K$;}\\
 
    g(x)\text{, else.}
 
  \end{cases}</tex>
 
  
<tex>V</tex> {{---}} вычислимая (можно параллельно запустить  <tex>g(x)</tex> и проверку, принадлежит ли <tex>n</tex> множеству <tex>K</tex> (просто перечисляя это множество); если <tex>g(x)</tex> успешно выполнится, то вернуть её результат).
 
  
Пусть <tex>p(x)=V(n, x)</tex>.
+
'''Теорема Райса-Шапиро''' позволяет дать простое описание перечислимым свойствам языков. Заметим, что вычислимо работать с произвольными языками возможности нет, поэтому далее неявно подразумевается, что все рассматриваемые языки являются [[Перечислимые языки|перечислимыми]].
  
Тогда программа, которая запускает параллельно проверку (1), принадлежит ли <tex>n</tex> множеству <tex>K</tex> (просто перечисляя это множество) и проверку (2), принадлежит ли <tex>p</tex> множеству <tex>A</tex>, является разрешающей программой для множества <tex>K</tex>, потому что:
+
Заметим, что образцы являются конструктивными объектами, следовательно, можно говорить о разрешимых и перечислимых множествах образцов.
* если <tex>n \in K</tex>, то проверка (1) завершится, а проверка (2) зависнет (так как <tex>p</tex> ведёт себя как <tex>h</tex>, которая не содержится в <tex>A</tex>); пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1;
 
* если <tex>n \notin K</tex>, то проверка (1) зависнет, а проверка (2) завершится (так как <tex>p</tex> ведёт себя как <tex>g</tex>, которая содержится в <tex>A</tex>); пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 0.
 
  
Противоречие, так как брали неразрешимое <tex>K</tex>.
+
{{Теорема
 +
|about=
 +
Райса-Шапиро
 +
|statement=
 +
Свойство языков <tex>A</tex> перечислимо <tex>\iff \exists\Gamma : L \in A \iff L \subseteq \Gamma.</tex>
 
}}
 
}}
  
 +
<tex>\Rightarrow</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>.
|statement =
 
Если <tex>A</tex> {{---}} перечислимое свойство функций, <tex>g \in A</tex>, то <tex>\exists h</tex>, такое что <tex>|Dom(h)| < +\infty</tex>, <tex>g</tex> {{---}} продолжение <tex>h</tex>, <tex>h \in A</tex>.
 
|proof =
 
Докажем от противного.
 
Пусть <tex>\not\exists h</tex>, удоволетворяющая условию леммы.
 
  
Рассмотрим перечислимое и неразрешимое множество <tex>K</tex> и следующую программу:
+
  A(L):
 +
    '''for''' t = 1 '''to''' <tex>\infty</tex>
 +
      '''for''' i = 1 '''to''' t
 +
        ok <tex>=</tex> ''true''
 +
      '''for''' j = 1 '''to''' <tex>|\Gamma_i|</tex>
 +
        '''if''' <tex>\lnot L|_t (\Gamma_{ij})</tex>
 +
          ok <tex>=</tex> ''false''
 +
        '''if''' ok
 +
          '''return''' ''true''
  
<tex>V(n, x) =
+
<tex>\Leftarrow</tex>
   \begin{cases}
+
:Для доказательства в другую сторону будем использовать две леммы, приведённые выше. Полуразрешитель для множества образцов, удовлетворяющих <tex>\Gamma</tex> строится следующим образом: для каждого образца <tex>\gamma</tex> строится текст программы
    g(x)\text{, if (1);}\\
+
   f<tex>{}_\gamma</tex>(x):
    \perp\text{, else;}
+
    '''return''' x <tex>{} \in \gamma</tex>
  \end{cases}</tex>
+
:Текст программы передаётся полуразрешителю <tex>A</tex>.
  
где условие <tex>(1)</tex> следующее: через <tex>x</tex> шагов перечисления <tex>K</tex> число <tex>n</tex> не появилось.
+
:Докажем, что данное построение корректно. Обозначим множество образцов, принимаемое построенным выше полурарешителем <tex>\Gamma</tex>. Пусть существует <tex>\gamma \in \Gamma</tex> такой, что <tex>L</tex> удовлетворяет <tex>\gamma</tex>. По определению <tex>\Gamma</tex>, язык <tex>\gamma</tex> удовлетворяет свойству <tex>A</tex>. Язык <tex>L</tex> удовлетворяет свойству <tex>A</tex> по первой лемме как надмножество <tex>\gamma</tex>.
  
Тогда программа, которая запускает параллельно проверку (1), принадлежит ли <tex>n</tex> множеству <tex>K</tex> (просто перечисляя это множество) и проверку (2), принадлежит ли <tex>V(n, x)</tex> множеству <tex>A</tex>, является разрешающей программой для множества <tex>K</tex>, потому что:
+
:Пусть <tex>L \in A</tex>. Тогда по второй лемме найдётся образец <tex>\gamma</tex>, который является подмножеством <tex>L</tex> и удовлетворяет свойству <tex>A</tex>. Следовательно, этот образец лежит в множестве <tex>\Gamma</tex> и язык <tex>A</tex> удовлетворяет множеству образцов <tex>\Gamma</tex>, что и требовалось доказать.
* если <tex>n \notin K</tex>, то <tex>V(n, x) \equiv g(x)</tex> для <tex>\forall n</tex>, поэтому проверка (2) завершится. Проверка (1) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 0;
 
* если <tex>n \in K</tex>, то завершится проверка (1). Также, в этом случае <tex>|Dom(V(n, x))| < +\infty</tex>, так как <tex>V(n, x) = g(x)</tex> при <tex>x = 0\ldots t-1</tex> для какого-то <tex>t</tex>. <tex>g</tex> является продолжением <tex>V(n, x)</tex>. По предположению от противного <tex>V(n, x) \notin A</tex> <tex>\Rightarrow</tex> проверка (2) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1.
 
  
Противоречие, так как брали неразрешимое <tex>K</tex>.
+
== См. также==
}}
 
  
 +
* [[m-сводимость]]
 +
* [[Примеры_неразрешимых_задач:_проблема_соответствий_Поста | Проблема соответствий Поста]]
 +
* [[Неразрешимость исчисления предикатов первого порядка]]
  
Вернёмся к доказательству теоремы.
+
== Источники информации ==
 +
* ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)
  
Функции с конечной областью определения записываются так:
+
[[Категория: Теория формальных языков]]
 
+
[[Категория: Теория вычислимости]]
<tex>f(x):</tex>
+
[[Категория: Примеры неразрешимых задач]]
    if <tex>x = x_1</tex>
 
        return <tex>y_1</tex>
 
    <tex>\cdots</tex>
 
    if <tex>x = x_n</tex>
 
        return <tex>y_n</tex>
 
    <tex>\perp</tex>
 
 
 
Такие функции перечислимы. Значит, такие функции, удоволетворяющие <tex>A</tex>, тоже перечислимы.
 
 
 
<tex>A_{\Gamma} \subseteq A</tex> по первой вспомогательной лемме.
 
 
 
<tex>A \subseteq A_{\Gamma}</tex> по второй вспомогательной лемме.
 
 
 
Значит, <tex>A = A_{\Gamma}</tex>.
 
}}
 

Версия 18:50, 16 января 2017

Определение:
Образцом (англ. pattern) называется конечное множество слов, объединённое свойством.


Определение:
Язык [math]L[/math] удовлетворяет свойству [math]A[/math], если [math]L \in A[/math] ( этот язык содержится в [math]A[/math]).


Определение:
Язык [math]L[/math] удовлетворяет образцу [math]X[/math], если [math]L[/math] содержит все элементы [math]X[/math].


Определение:
Язык [math]L[/math] удовлетворяет множеству образцов [math]\Gamma[/math], если [math]L[/math] удовлетворяет хотя бы одному образцу [math]X \in \Gamma[/math].


Лемма:
Пусть [math]A[/math] — перечислимое свойство языков, [math]G \in A[/math]. Тогда верно следствие: [math]G \subset H \Rightarrow H \in A[/math].
Доказательство:
[math]\triangleright[/math]

Строим доказательство от противного. Пусть [math]G \in A[/math], [math]G \subset H[/math], [math]H \notin A[/math], [math]K[/math] — перечислимое неразрешимое множество. Построим следующую вычислимую функцию: [math]f(x, y) = \begin{cases} x \in H & y \in K\\ x \in G & y \notin K \end{cases}[/math]

Вычисляется эта функция следующим образом: параллельно запускаем проверки [math]x \in G[/math] и [math]y \in K[/math]. Если [math]x \in G[/math], то [math]x \in H[/math], следовательно, функция возвращает единицу вне зависимости от [math]y[/math]. Если [math]y \in K[/math], то запускаем проверку [math]x \in H[/math].

Разрешим множество [math]K[/math]с помощью этой функции. Для проверяемого элемента [math]y[/math] подготовим программу [math]g[/math]:

 [math]g(x):[/math]
   if [math]x \in H[/math]
     return [math]y \in K[/math]
   if [math]x \in G[/math]
     return [math]y \notin K[/math]
После этого запустим параллельно проверки [math]y \in K[/math] и [math]L(g) \in A[/math]. Если [math]y \in K[/math], то первая проверка завершится. Иначе функция [math]g[/math] задаёт язык [math]G[/math], который обладает свойством [math]A[/math], следовательно, вторая проверка завершится, сигнализируя о том, что [math]y \notin K[/math]. Но [math]K[/math] не является разрешимым множеством, получено противоречие.
[math]\triangleleft[/math]


Лемма:
Пусть [math]A[/math] — перечислимое свойство, [math]G \in A[/math]. Тогда существует конечное множество [math]H \in A[/math], которое является подмножеством [math]G[/math].
Доказательство:
[math]\triangleright[/math]

Строим доказательство от противного. Пусть [math]G \in A[/math], и любое конечное подмножество [math]G[/math] не удовлетворяет свойству [math]A[/math], [math]K[/math] — перечислимое неразрешимое множество. Определим следующую функцию:

  • [math]f(x, y) = false[/math], если за [math]x[/math] шагов перечисления [math]K[/math] появилось слово [math]y[/math].
  • [math]f(x, y) = x \in G[/math] иначе.

Заметим, что если [math]y \in K[/math], то [math]f(x, y)[/math] распознаёт некоторое конечное подмножество [math]G[/math] и всё множество [math]G[/math] иначе. Эта функция тривиальным образом разрешима, построим с её помощью разрешитель [math]K[/math]. Аналогично доказательству первой леммы, подготовим программу [math]g[/math]:

 g(x):
   return f(x, y)
После этого параллельно запустим проверки [math]y \in K[/math] и [math]L(g) \in A[/math]. Аналогично, данная процедура разрешает множество [math]K[/math]. Но [math]K[/math] не является разрешимым, получено противоречие.
[math]\triangleleft[/math]


Теорема Райса-Шапиро позволяет дать простое описание перечислимым свойствам языков. Заметим, что вычислимо работать с произвольными языками возможности нет, поэтому далее неявно подразумевается, что все рассматриваемые языки являются перечислимыми.

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

Теорема (Райса-Шапиро):
Свойство языков [math]A[/math] перечислимо [math]\iff \exists\Gamma : L \in A \iff L \subseteq \Gamma.[/math]

[math]\Rightarrow[/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]=[/math] true
     for j = 1 to [math]|\Gamma_i|[/math]
       if [math]\lnot L|_t (\Gamma_{ij})[/math]
         ok [math]=[/math] false
       if ok
         return true

[math]\Leftarrow[/math]

Для доказательства в другую сторону будем использовать две леммы, приведённые выше. Полуразрешитель для множества образцов, удовлетворяющих [math]\Gamma[/math] строится следующим образом: для каждого образца [math]\gamma[/math] строится текст программы
 f[math]{}_\gamma[/math](x):
   return x [math]{} \in \gamma[/math]
Текст программы передаётся полуразрешителю [math]A[/math].
Докажем, что данное построение корректно. Обозначим множество образцов, принимаемое построенным выше полурарешителем [math]\Gamma[/math]. Пусть существует [math]\gamma \in \Gamma[/math] такой, что [math]L[/math] удовлетворяет [math]\gamma[/math]. По определению [math]\Gamma[/math], язык [math]\gamma[/math] удовлетворяет свойству [math]A[/math]. Язык [math]L[/math] удовлетворяет свойству [math]A[/math] по первой лемме как надмножество [math]\gamma[/math].
Пусть [math]L \in A[/math]. Тогда по второй лемме найдётся образец [math]\gamma[/math], который является подмножеством [math]L[/math] и удовлетворяет свойству [math]A[/math]. Следовательно, этот образец лежит в множестве [math]\Gamma[/math] и язык [math]A[/math] удовлетворяет множеству образцов [math]\Gamma[/math], что и требовалось доказать.

См. также

Источники информации

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