Изменения

'''forall''' <tex>x_i d_i :</tex> все возможные разбиения <tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex> '''if''' <tex>(p_1(x_1x_{d_1}) == 1) \land (p_1(x_2x_{d_2}) == 1) \land \ ... \ \land (p_1(x_nx_{d_n}) == 1)</tex> '''return''' 1

'''forall''' <tex>x_1d_{1, x_2 2} :</tex> все возможные разбиения на две части <tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex> '''if''' <tex>(p_1(x_1x_{d_1}) == 1 \land p_2(x_2x_{d_2}) == 1)</tex> '''return''' 1

Пусть <tex>p_1</tex> и <tex>p_2</tex> — полуразрешающие программы для языков <tex>L_1</tex> и <tex>L_2</tex> соответственно. Для доказательства достаточно написать полуразрешающую или перечисляющую программу для каждого случая. Для некоторых языков предоставим оба варианта. Заметим, что <tex>p_1</tex> и <tex>p_2</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</tex> и <tex>L_2</tex> и выдавать по очереди слова из <tex>L_1</tex> и <tex>L_2</tex> соответственно.

'''forall''' <tex>x_i d_i :</tex> все возможные разбиения <tex>x_{d_1}x_{d_2} \ .. \ x_{d_n} :</tex> текущее разбиение <tex>x</tex> '''if''' <tex>(p_1(x_1x_{d_1}) == 1) \land (p_1(x_2x_{d_2}) == 1) \land \ ... \ \land (p_1(x_nx_{d_n}) == 1)</tex> '''return1''' 1 Перечислитель же строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле по тайм-лимиту и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их.

'''forall''' <tex>x_1d_{1, x_2 2} :</tex> все возможные разбиения на две части <tex>x_{d_1}x_{d_2} :</tex> текущее разбиение <tex>x</tex> '''if''' <tex>(p_1(x_1x_{d_1}) == 1 \land p_2(x_2x_{d_2}) == 1)</tex> '''return1''' 1  Перечислитель же для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их конкатенацию.&nbsp;

Рассмотрим язык <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> может быть не перечислим.