54
правки
Изменения
м
Разрешатель Разрешитель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.
Разрешатель Разрешитель будет перебирать все возможные разбиения на два слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex>, иначе — не принадлежит.
'''for''' <tex>k = 1\ .. \ \infty </tex> '''if''' <tex> (p_1|_k(x) == 1) \lor (p_2|_k(x) == 1) </tex> '''then return 1'''
'''for''' <tex>k = 1\ .. \ \infty </tex> '''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(x) == 1) </tex> '''then return 1'''
'''for''' <tex>k = 1\ .. \ \infty </tex> '''if''' <tex> (p_1|_k(x) == 1) \land (p_2|_k(y) == 1) </tex> '''then return 1'''
Нет описания правки
|proof=
Пусть <tex>p_1</tex> и <tex>p_2</tex> — разрешающие программы для языков
<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешательразрешитель) для каждого случая.
* Разрешающая программа для языка <tex> L_1 \cup L_2 :</tex>
<tex>p(x)</tex>
'''forforall''' <tex>x_i :</tex> разбиение <tex>x</tex> '''if''' <tex>(p_1(x_ix_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''then return''' 1
'''return''' 0
* Для языка <tex> L_1 L_2 : </tex>
<tex>p(x)</tex>
'''forforall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1
'''return''' 0
}}
|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>
<tex>p(x)</tex>
Перечислитель же для этого языка будет по очереди на один шаг запускать перечислители для <tex>L_1</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.
<tex>p(x)</tex>
* Для языка <tex> L_1 \times L_2 :</tex>
<tex>p(\langle x, y \rangle)</tex>
* Для языка <tex> L_1^* :</tex>
<tex>p(x)</tex>
'''forforall''' <tex>x_i :</tex> разбиение <tex>x</tex> '''if''' <tex>(p_1(x_ix_1) == 1) \land (p_1(x_2) == 1) \land \ ... \ \land (p_1(x_n) == 1)</tex>
'''then return''' 1
<tex>p(x)</tex>
'''forforall''' <tex>x_1, x_2 :</tex> разбиение <tex>x</tex>
'''if''' <tex>(p_1(x_1) == 1 \land p_2(x_2) == 1)</tex>
'''then return''' 1
== Литература ==
* ''Верещагин Н. К., Шень А.'' '''Лекции по математической логике и теории алгоритов. Часть 3. Вычислимые функции''' — -- М.: МЦНМО, 1999
