304
правки
Изменения
доказательство леммы 1
Доказательство в одну сторону тривиально: пусть <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>.
Для доказательства в другую сторону понадобятся следующие леммы:
{{Лемма
Строим доказательство от противного. Пусть G \in A, G \subset H, H \notin A, K — перечислимое неразрешимое множество. Построим следующую вычислимую функцию: f(x, y) = \begin{cases} x \in H & y \in K\\ x \in G & y \notin K \end{cases}
Вычисляется эта функция следующим образом: параллельно запускаем проверки x \in G и y \in K. Если x \in G, то x \in H, следовательно, функция возвращает единицу вне зависимости от y. Если y \in K, то запускаем проверку x \in H.
С помощью этой функции можно разрешить множество K следующим образом: для проверяемого элемента y подготовим программу g:
g(x):
return f(x, y)
После этого запустим параллельно проверки
|statement=
Пусть <tex>A</tex> — перечислимое свойство языков, <tex>G \in A</tex>. Тогда верно следствие: <tex>G \subset H \Rightarrow H \in A</tex>.
|proof=
Строим доказательство от противного. Пусть <tex>G \in A</tex>, <tex>G \subset H</tex>, <tex>H \notin A</tex>, <tex>K</tex> — перечислимое неразрешимое множество. Построим следующую вычислимую функцию:
<tex>f(x, y) = \begin{cases}
x \in H & y \in K\\
x \in G & y \notin K
\end{cases}</tex>
Вычисляется эта функция следующим образом: параллельно запускаем проверки <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>:
g(x):
return f(x, y)
После этого запустим параллельно проверки <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> не является разрешимым множеством, получено противоречие.
}}
== Литература ==
* ''Верещагин Н. К., Шень A.'' Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. {{---}} М.: Издательский дом «Вильямс», 2008. {{---}} С. 528 {{---}} ISBN 978-5-8459-1347-0 (рус.)
