54
правки
Изменения
м
Нет описания правки
{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –{{- --}} разрешимы, тогда следующие языки разрешимы:
* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — {{---}} разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешитель) для каждого случая.
'''return''' 0
Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — {{---}} не принадлежит.
* Для языка <tex> L_1 L_2 : </tex>
'''return''' 0
Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешителя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — {{---}} не принадлежит.
}}
{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –{{- --}} перечислимы, тогда следующие языки перечислимы:
* Объединение <tex>L_1</tex> и <tex>L_2\ (L_1 \cup L_2)</tex>
|proof=
Пусть <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>
{{Теорема
|statement=
Языки <tex> L_1, L_2 </tex> –{{- --}} перечислимы, тогда следующие языки могут быть не перечислимы:
* Дополнение <tex>L_1\ (\overline{L_1})</tex>
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — {{–--}} М.: МЦНМО, 1999
