271
правка
Изменения
Нет описания правки
Пусть <tex>p_1</tex> и <tex>p_2</tex> {{---}} полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую программу для каждого случая. Заметим, что <tex>p_1</tex> и <tex>p_2</tex> могут зависнуть при использовании в полуразрешающей программе для соответствующего языка, но это допустимо.
* Полуразрешающая программа для языка <tex> L_1 \cup L_2 :</tex> :
<tex>p(x):</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''if''' <tex> (p_1(x)|_k == 1) \lor (p_2(x)|_k == 1) </tex>
'''return 1'''
* Для языка <tex> L_1 \cap L_2 :</tex> :
<tex>p(x):</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(x) == 1) </tex>
'''return 1'''
* Для языка <tex> L_1 \times L_2 :</tex> :
<tex>p(\langle x, y \rangle):</tex>
'''if''' <tex> (p_1(x) == 1) \land (p_2(y) == 1) </tex>
'''return 1'''
* Для языка <tex> L_1^* :</tex>:
<tex>p(x):</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^n \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных всевозможных разбиений слова <tex>x</tex> на подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_1|_k(x_2) == 1) \land \ ... \ \land (p_1|_k(x_n) == 1)</tex>
'''return 1'''
* Для языка <tex> L_1 L_2 : </tex> :
<tex>p(x):</tex>
'''for''' <tex>k = 1 \ .. \ \infty</tex>
'''forall''' <tex>{\{x_i\}}_{i=1}^2 \in P </tex>, где <tex>P</tex> {{---}} множество всех возможных всевозможных разбиений слова <tex>x</tex> на две подстроки
'''if''' <tex>(p_1|_k(x_1) == 1) \land (p_2|_k(x_2) == 1)</tex>
'''return 1'''
Языки <tex> L_1, L_2 </tex> {{---}} перечислимы, тогда следующие языки могут быть не перечислимы:
* Дополнение <tex>L_1\ (\overline{L_1})</tex>{{---}} дополнение <tex>L_1\</tex>;* Разность <tex>L_1 \backslash L_2</tex> {{---}} разность <tex>L_1</tex> и <tex>L_2\ (L_1 \backslash L_2)</tex>.
|proof=
Рассмотрим язык <tex> \overline{L_1} </tex>. Предположим, что он перечислим. Тогда, имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \overline{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \overline{L_1} </tex>. Тогда получится , что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать можно сказать, принадлежит ли оно <tex> L_1 </tex> или не принадлежитнет. Но мы знаем, что [[Разрешимые (рекурсивные) языки#Пример неразрешимого множества|существуют перечислимые, но не разрешимые неразрешимые языки]], следовательно, язык <tex> \overline{L_1} </tex> может быть не перечислим.
Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> {{---}} это <tex> \overline{L_2} </tex>. Про язык <tex> \overline{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.
}}
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' {{---}} М.: МЦНМО, 1999
