Изменения

== {{Определение образца =|definition='''Образцом''' (англ. ''pattern'') называется конечное множество слов, объединённое [[Свойства_перечислимых_языков._Теорема_Успенского-Райса|свойством]].}}

Пусть '''Язык <tex>\gamma=\{\langle x_1,y_1\rangle,\langle x_2,y_2\rangle,\ldots ,\langle x_n,y_n\rangle\}L</tex>.удовлетворяет свойству <tex>A<br /tex>Тогда ''', если <tex>L \gammain A</tex> ( этот язык содержится в <tex>A</tex> называется образцом).

Пусть '''Язык <tex>A_{\gamma}=\{p | p(x_1)=y_1 \wedge p(x_2)=y_2 \wedge \ldots \wedge p(x_n)=y_n\}L</tex>, где удовлетворяет образцу <tex>\langle x_i, y_i\rangle \in \gammaX</tex>.<br />Тогда ''', если <tex>A_{\gamma}L</tex> называется свойством образца содержит все элементы <tex>\gammaX</tex>.

 == Лемма о перечислимости свойства образца == {{ЛеммаОпределение|statement definition=Свойство '''Язык <tex>A_{\gamma}L</tex> перечислимо для любого образца удовлетворяет множеству образцов <tex>\gammaGamma</tex>.|proof =Построим полуразрешитель ''', если <tex>A_{\gamma}L</tex>: удовлетворяет хотя бы одному образцу <tex>q(p):</tex> for <tex>\langle x_i, y_i\rangle X \in \gamma</tex> if <tex>p(x_i) \not= y_iGamma</tex> while True return 1Полуразрешителя достаточно для доказательства перечислимости.

|statement =Пусть <tex>\GammaA</tex> {{---}} — перечислимое множество образцовсвойство языков, <tex>A_{\Gamma} = \bigcup\limits_{\gamma G \in \Gamma}{A_{\gamma}}A</tex>.Тогда верно следствие: <tex>A_{G \subset H \Rightarrow H \Gamma}in A</tex> является перечислимым.|proof =Построим полуразрешитель Строим доказательство от противного. Пусть <tex>A_{G \Gamma}in A</tex>: , <tex>q(p):G \subset H</tex> for , <tex>k = 1H \ldots +\inftynotin A</tex> for , <tex>\gamma \in \Gamma[1..k]K</tex>— перечислимое неразрешимое множество. Построим следующую вычислимую функцию: if <tex>f(p x, y) = \begin{cases}x \in H & y \in A_{K\\x \in G & y \notin K\gamma})|_end{TL(k)cases}</tex> return 1Полуразрешителя достаточно для доказательства перечислимости.}}

{{Теорема|statement = <tex>g(x):</tex>Свойство функций '''if''' <tex>Ax \in H</tex> перечислимо тогда и только тогда, когда '''return''' <tex>y \exists \Gamma: A = A_{\Gamma}in K</tex>, где '''if''' <tex>x \Gammain G</tex> {{---}} перечислимое множество образцов.|proof = '''return''' <tex>y \Leftarrownotin K</tex>

Очевидно После этого запустим параллельно проверки <tex>y \in K</tex> и <tex>L(перебор по TLg)\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> не является разрешимым множеством, получено противоречие.}}

|statement =Пусть <tex>A</tex> {{---}} — перечислимое свойство функций, <tex>g G \in A</tex>, . Тогда существует конечное множество <tex>hH \in A</tex> {{---}} продолжение <tex>g</tex>.Тогда , которое является подмножеством <tex>h \in AG</tex>.|proof =Докажем Строим доказательство от противного.Пусть <tex>g G \in A</tex>, и любое конечное подмножество <tex>hG</tex> {{---}} продолжение не удовлетворяет свойству <tex>gA</tex>, <tex>h \notin AK</tex>. Рассмотрим — перечислимое и неразрешимое множество . Определим следующую функцию:* <tex>f(x, y) = false</tex>, если за <tex>x</tex> шагов перечисления <tex>K</tex> и следующую программу:появилось слово <tex>y</tex>.* <tex>Vf(nx, xy) = x \begin{cases}in G</tex> иначе. h(x)\text{Заметим, if $n что если <tex>y \in K$;}\\ g</tex>, то <tex>f(x, y)\text{</tex> распознаёт некоторое конечное подмножество <tex>G</tex> и всё множество <tex>G</tex> иначе. Эта функция тривиальным образом разрешима, elseпостроим с её помощью разрешитель <tex>K</tex>.} \end{cases}Аналогично доказательству первой леммы, подготовим программу <tex>g</tex>:

<tex>V</tex> {{---}} вычислимая (можно параллельно запустить <tex> g(x)</tex> и проверку, принадлежит ли <tex>n</tex> множеству <tex>K</tex> (просто перечисляя это множество); если <tex>g: '''return''' f(x)</tex> успешно выполнится, то вернуть её результатy).

Пусть <tex>p(x)=V(n, x)</tex>.<br>Назовем (1) проверку на принадлежность <tex> n </tex> множеству <tex> K </tex> (просто перечисляя это множество), а (2) проверку на принадлежность <tex> p </tex> множеству <tex> A </tex>. Тогда программа, которая После этого параллельно запускает запустим проверки (1) и (2), является разрешающей программой для множества <tex>K</tex>, так как:* если <tex>n y \in K</tex>, то проверка (1) завершится, а проверка (2) зависнет (и <tex>p</tex> ведёт себя как <tex>h</tex>, которая не содержится в <tex>A</tex>L(g); пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1;* если <tex>n \notin Kin A</tex>. Аналогично, то проверка (1) зависнет, а проверка (2) завершится (<tex>p</tex> ведёт себя как <tex>g</tex>, которая содержится в <tex>A</tex>); пусть в этом случае разрешающая программа для данная процедура разрешает множество <tex>K</tex> возвращает 0. Получили противоречие, так как брали Но <tex>K</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> и следующую программу:перечислимых множествах образцов.

<tex>V(n, x) = \begin{cases} g(x)\text{, if (0);}\\Теорема \perp\text{, else;}|about= \end{cases}</tex>Райса-Шапиро|statement=где условие <tex>(0)</tex> следующее: через <tex>x</tex> шагов перечисления <tex>K</tex> число <tex>n</tex> не появилось.<br>Назовем (1) проверку на принадлежность <tex> n </tex> множеству <tex> K </tex> (просто перечисляя это множество), а (2) проверку на принадлежность <tex> V(n, x) </tex> множеству Свойство языков <tex> A </tex>. Тогда программа, которая параллельно запускает проверки (1) и (2), является разрешающей программой для множества <tex>K</tex>, так как:* если перечислимо <tex>n \notin K</tex>, то <tex>V(n, x) iff \equiv g(x)</tex> для <tex>exists\forall n</tex>, поэтому проверка (2) завершится. Проверка (1) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 0;* если <tex>n Gamma : L \in K</tex>, то завершится проверка (1). Также, в этом случае <tex>|Dom(V(n, x))| < +\infty</tex>, так как <tex>V(n, x) = g(x)</tex> при <tex>x = 0A \ldots t-1</tex> для какого-то <tex>t</tex>. <tex>g</tex> является продолжением <tex>V(n, x)</tex>. По предположению от противного <tex>V(n, x) iff L \notin A</tex> <tex>subseteq \Rightarrow</tex> проверка (2) зависнет. Пусть в этом случае разрешающая программа для <tex>K</tex> возвращает 1Gamma. Противоречие, так как брали неразрешимое <tex>K</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>=</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>f(x):\Rightarrow</tex> if :Для доказательства в другую сторону будем использовать две леммы, приведённые выше. Полуразрешитель для множества образцов, удовлетворяющих <tex>x = x_1\Gamma</tex> return строится следующим образом: для каждого образца <tex>y_1\gamma</tex>строится текст программы f<tex>{}_\cdotsgamma</tex> if <tex>(x = x_n</tex>): '''return ''' x <tex>y_n{} \in \gamma</tex> :Текст программы передаётся полуразрешителю <tex>\perpA</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>.

:Пусть <tex>A_{L \Gamma} \subseteq in A</tex> . Тогда по первой вспомогательной второй лемменайдётся образец <tex>\gamma</tex>, который является подмножеством <tex>L</tex> и удовлетворяет свойству <tex>A</tex>. Следовательно, этот образец лежит в множестве <tex>\Gamma</tex> и язык <tex>A</tex> удовлетворяет множеству образцов <tex>\Gamma</tex>, что и требовалось доказать.

<tex>A \subseteq A_{\Gamma}</tex> по второй вспомогательной лемме== См.также==

 == Литература Источники информации ==