Изменения

<tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать разрешающую программу (разрешатель) для каждого случая.

<tex>p(x)</tex>

'''return''' <tex>(p_1(x) == 1) \lor (p_2(x) == 1)</tex>

<tex>p(x)</tex>

'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 1)</tex>

<tex>p(x)</tex>

'''return''' <tex>(p_1(x) == 0)</tex>

<tex>p(x)</tex>

'''return''' <tex>(p_1(x) == 1) \land (p_2(x) == 0)</tex>

<tex>p(\langle x, y \rangle)</tex>

'''return''' <tex>(p_1(x) == 1) \land (p_2(y) == 1)</tex>

<tex>p(x)</tex>

Разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все подслова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex>, иначе — не принадлежит.

<tex>p(x)</tex>

Пусть <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</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

полуразрешающая программа:

'''then return 1'''

полуразрешающая программа:

'''then return 1'''

полуразрешающая программа (по аналогии с <tex>L_1^*</tex> для разрешимого <tex>L_1</tex>):

Перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

полуразрешающая программа: