Изменения

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

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

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

|statement =Свойство Пусть <tex>A_{A</tex> — перечислимое свойство языков, <tex>G \gamma}in A</tex> перечислимо для любого образца . Тогда верно следствие: <tex>G \gammasubset H \Rightarrow H \in A</tex>.|proof =ОчевидноСтроим доказательство от противного. Пусть <tex>G \in A</tex>, как строится программа<tex>G \subset H</tex>, которая возвращает 1<tex>H \notin A</tex>, если <tex>p K</tex> — перечислимое неразрешимое множество. Построим следующую вычислимую функцию:<tex>f(x, y) = \begin{cases}x \in H & y \in A_K\\x \in G & y \notin K\end{\gammacases}</tex> ( Вычисляется эта функция следующим образом: параллельно запускаем проверки <tex>x \in G</tex> и <tex>py \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>.}}

{{Лемма|statement =Пусть После этого запустим параллельно проверки <tex>y \Gammain K</tex> - перечислимое множество образцов, и <tex>A_{\Gamma} = \bigcup\limits_{\gamma L(g) \in \Gamma}{A_{\gamma}}A</tex>.Тогда Если <tex>A_{y \Gamma}in K</tex> - перечислимо, то первая проверка завершится.|proof =Приведём программу, выдающую 1, если Иначе функция <tex>p \in A_{\Gamma}g</tex>: задаёт язык <tex>q(p):G</tex> for , который обладает свойством <tex>k = 1..+\inftyA</tex> for , следовательно, вторая проверка завершится, сигнализируя о том, что <tex>y \gamma \in \Gamma[1..k]notin K</tex> if . Но <tex>(p \in A_{\gamma})|_{TL(k)}K</tex> return 1Такой программы достаточно для доказательства перечислимостине является разрешимым множеством, получено противоречие.

{{Лемма|statement=Пусть <tex>A</tex> — перечислимое свойство, <tex>G \in A</tex>. Тогда существует конечное множество <tex>H \in A</tex>, которое является подмножеством <tex>G</tex>.|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>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>:

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

:Очевидно После этого параллельно запустим проверки <tex>y \in K</tex> и <tex>L(перебор по TLg)\in A</tex>.Аналогично, данная процедура разрешает множество <tex>K</tex>. Но <tex>K</tex> не является разрешимым, получено противоречие.}}

:Здесь нам потребуются две вспомогательные леммы.:{{Лемма|statement =Пусть <tex>A</tex> - перечислимое свойство функцийЗаметим, <tex>g \in A</tex>что образцы являются конструктивными объектами, <tex>h</tex> - продолжение <tex>g</tex>.Тогда <tex>h \in A</tex>.|proof =Докажем от противного.Пусть <tex>g \in A</tex>следовательно, <tex>h</tex> - продолжение <tex>g</tex>, <tex>h \notin A</tex>можно говорить о разрешимых и перечислимых множествах образцов.

Рассмотрим перечислимое и неразрешимое множество {{Теорема|about=Райса-Шапиро|statement=Свойство языков <tex>KA</tex> и следующую программуперечислимо <tex>\iff \exists\Gamma :L \in A \iff L \subseteq \Gamma.</tex>}}

<tex>V(n, x) = \begin{cases} h(x)\text{, if $n \in K$;}\\ g(x)\text{, else.} \end{cases}Leftarrow</tex>

: Доказательство в одну сторону тривиально: пусть <tex>V\Gamma</tex> - вычислимая (можно параллельно запустить — перечислимое множество образцов. Будем обозначать за <tex>\Gamma_i</tex> образец с номером <tex>g(x)i</tex> и проверку, принадлежит ли а за <tex>\Gamma_{ij}</tex> — элемент с номером <tex>nj</tex> множеству образца с номером <tex>Ki</tex> (просто перечисляя это множество); если . Далее приведён код полуразрешителя <tex>g(x)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>p\lnot L|_t (x\Gamma_{ij})</tex> ok <tex>=V(n, x)</tex>.''false'' '''if''' ok '''return''' ''true''

Тогда программа, которая запускает параллельно проверку, принадлежит ли <tex>n\Rightarrow</tex> множеству <tex>K</tex> (просто перечисляя это множество):Для доказательства в другую сторону будем использовать две леммы, и проверкуприведённые выше. Полуразрешитель для множества образцов, принадлежит ли удовлетворяющих <tex>p\Gamma</tex> множеству <tex>A</tex>, является разрешающей программой строится следующим образом: для множества <tex>Kкаждого образца </tex> (так как если <tex>p \in Agamma</tex>, то строится текст программы f<tex>n {}_\notin Kgamma</tex> по построению <tex>V(n, x)</tex>).:Противоречие, так как брали неразрешимое '''return''' x <tex>K</tex>.}{}  {{Лемма|statement =Если <tex>A</tex> - перечислимое свойство функций, <tex>g \in A</tex>, то <tex>\exists hgamma</tex>, такое что :Текст программы передаётся полуразрешителю <tex>|Dom(h)| < +\infty</tex>, <tex>g</tex> - продолжение <tex>h</tex>, <tex>h \in A</tex>.|proof =Рассмотрим перечислимое и неразрешимое множество <tex>K</tex> и следующую программу:

:Докажем, что данное построение корректно. Обозначим множество образцов, принимаемое построенным выше полурарешителем <tex>V(n, x) = \begin{cases} g(x)Gamma</tex>. Пусть существует <tex>\text{, if (1);}gamma \in \ Gamma</tex> такой, что <tex>L</tex> удовлетворяет <tex>\perpgamma</tex>. По определению <tex>\text{Gamma</tex>, else;} язык <tex>\gamma</tex> удовлетворяет свойству <tex>A</tex>. Язык <tex>L</tex> удовлетворяет свойству <tex>A</tex> по первой лемме как надмножество <tex>\end{cases}gamma</tex>.

где условие :Пусть <tex>L \in A</tex>. Тогда по второй лемме найдётся образец <tex>(1)\gamma</tex> следующее: через , который является подмножеством <tex>L</tex> и удовлетворяет свойству <tex>A</tex>. Следовательно, этот образец лежит в множестве <tex>x\Gamma</tex> шагов перечисления и язык <tex>KA</tex> число удовлетворяет множеству образцов <tex>n\Gamma</tex> не появилось, что и требовалось доказать.