Просмотр исходного текста страницы Свойства перечислимых языков. Теорема Успенского-Райса

== Свойства языков ==

Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> \mathrm {RE} </tex>.
{{Определение
|definition='''Свойством языков''' (англ. ''property of languages'') называется множество <tex> A \subset \mathrm {RE} </tex>.
}}
{{Определение
|definition=Свойство называется '''тривиальным''' (англ. ''trivial''), если <tex> A = \varnothing </tex> или <tex> A = \mathrm {RE} </tex>.
}}
{{Определение
|definition='''Язык свойства''' (англ. ''language of property'') <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.
}}
{{Определение
|definition=Свойство <tex> A </tex> называется '''разрешимым''' (англ. ''recursive''), если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].
}}
=== Примеры ===
'''Примеры свойств''':
# Язык должен содержать слово ''hello''.
# Язык должен содержать хотя бы одно простое число.

Псевдокод для  разрешителя <tex>L(A)</tex>, где <tex>A = \mathrm {RE}: </tex>
 <tex>p_A(p_X)</tex> <font color="green"> // <tex>p_X</tex> {{---}} полуразрешитель некоторого языка</font>
   '''return''' ''true''

Псевдокод для программы в общем случае, то есть для проверки того, что язык удовлетворяет свойству :
 <tex>p_A(p_X)</tex> 
   '''return''' <tex>L(p_X) \in A</tex>

Псевдокод полуразрешителя для языка свойства из первого примера:
 <tex>p_A(p_X)</tex> <font color="green"> // <tex>X</tex> {{---}} перечислимый язык в общем случае, поэтому <tex>p_A</tex> {{---}} полуразрешитель (по [[Теорема Райса-Шапиро |теореме Райса-Шапиро]])</font>
   '''return''' <tex>p_X</tex>('hello')

== Теорема Успенского-Райса ==
{{Теорема
|statement=
Язык никакого нетривиального свойства <tex>A</tex> не является разрешимым.
|proof=
Приведём доказательство от противного.
 
Предположим, что <tex>A</tex> разрешимо.

Пусть <tex>p_\infty</tex> {{---}} всегда зацикливающийся алгоритм. Для упрощения предположим, что <tex>p_\infty \in A</tex>. В противном случае доказательство аналогично.

Рассмотрим <tex>p_a</tex> {{---}} программу, такую что <tex>a \in \overline A</tex> (такое <tex>a</tex> существует, т.к. <tex>А</tex> {{---}} нетривиально). Рассмотрим также произвольное перечислимое неразрешимое множество <tex>X</tex>. Пусть <tex>p_X(n)</tex> {{---}} полуразрешитель <tex>X</tex>.

Зафиксируем произвольное <tex>n \in \mathbb{N}</tex> и построим следующую функцию 
<tex>Vn(x) = \begin{cases}
  p_a(x),  n \in X \\
  p_\infty(x), n \notin X \\
\end{cases} </tex>

<code>
 '''function''' <tex>V_n</tex>(x):
   '''if''' <tex>p_X</tex>(n) == 1
     '''return''' <tex>p_a</tex>(x)
   '''while''' ''true''
</code>

Получили, что если <tex>n \in X</tex>, то <tex>V_n \in L(\overline S)</tex>, а если <tex>n \notin X</tex>, то <tex>V_n \in L(S)</tex>. Таким образом, <tex>n \in X \iff V_n \in L(\overline S)</tex>. 

Так как <tex>\overline S</tex> {{---}} разрешимо, то можно проверить для любого <tex>a</tex>, лежит ли оно в <tex>\overline{S}</tex>. Но это тоже самое, что и проверка <tex>n \in X</tex>. Тогда можно для каждого <tex>n</tex> проверить, лежит ли оно в <tex>X</tex>, а следовательно и построить разрешитель для <tex>X</tex>. Так как <tex>X</tex> {{---}} неразрешимо, получили противоречие.


}}

== См. также ==
* [[Теорема о рекурсии]]
* [[Теорема Райса-Шапиро]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]
* Rice, H. G. {{---}} Classes of Recursively Enumerable Sets and Their Decision Problems." {{---}} Trans. Amer. Math. Soc. 74, 358-366, 1953.
* Хопкрофт Д., Мотванн Р., Ульманн Д. {{---}}Введение в теорию автоматов, языков и вычислений {{---}} стр. 397.
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Разрешимые и перечислимые языки]]