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

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

Образцом (англ. 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]\Leftarrow[/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]\Rightarrow[/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], что и требовалось доказать.

См. также

• m-сводимость
• Проблема соответствий Поста
• Неразрешимость исчисления предикатов первого порядка

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

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