Изменения

Если языки разрешимы, значит для каждого из них есть разрешающая программа. Тогда разрешающая программа для языка <tex>L_1 \cup L_2</tex> будет запускать разрешающую для каждого языка и выводить 1, если оба разрешателя выдали 1, 0 во всех остальных случаях. Для языка <tex> L_1 \cap L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 0, если оба разрешателя выдали 0, 1 во всех остальынх случаях. Для языка <tex> \bar{L_1} </tex> разрешатель будет выдавать результат, обратный результату разрешателя для <tex> L_1 </tex>. Для языка <tex> L_1 \backslash L_2 </tex> разрешающая программа будет запускать оба разрешателя и выдавать 1, если первый разрешатель вернет 1, а второй 0 и 0 во всех остальных случаях. Для языка <tex> L_1^* </tex> разрешатель будет перебирать все возможные разбиения данного ему слова на подслова, и для каждого проверять принадлежность <tex> L_1 </tex>. Если хотя бы в одном разбиении все слова будут принадлежать <tex> L_1 </tex>, то все слово принадлежит <tex> L_1^* </tex> иначе не принадлежит. Для языка <tex> L_1 L_2 </tex> разрешающая программа будет перебирать все возможные разбиения на 2 слова и проверять принадлежность первого слова <tex> L_1 </tex> и второго слова <tex> L_2 </tex>. Если хотя бы для одного разбиения оба разрешателя вернут 1, то слово принадлежит <tex> L_1 L_2 </tex> , иначе не принадлежит.}} {{Теорема|statement= <tex> L_1, L_2 </tex> –- перечислимы, тогда  <tex>\left. \begin{array}{lll} L_1 \cup L_2 \\ L_1 \cap L_2 \\ L_1^* \\ L_1 L_2 \end{array} \right\} </tex> перечислимы<tex>\left. \begin{array}{lll} \bar{L_1} \\ L_1 \backslash L_2 \end{array} \right\} </tex> могут быть не перечислимы|proof=Для <tex> L_1 \cup L_2 </tex> перечислитель будет по очереди на один шаг запускать перечислители <tex> L_1 </tex> и <tex> L_2 </tex> и выдавать по очереди слова из <tex> L_1 </tex> и <tex> L_2 </tex>. Дальше воспользуемся возможностью построить полувычислитель для перечислимого языка. Для языка <tex> L_1 \cap L_2 </tex> построим полувычислитель. Запустим по очереди полувычислители для <tex> L_1 </tex> и <tex> L_2 </tex>. Если слово принадлежит <tex> L_1 \cap L_2 </tex>, то оба полувычислителя выдадут 1, иначе один из полувычислителей зависнет, и полувычислитель для <tex> L_1 \cap L_2 </tex> тоже зависнет, что допустимо. Для <tex> L_1^* </tex> перечислитель строится следующим образом: запускаем перечислитель для <tex> L_1 </tex> в цикле и запоминаем выданные им слова. При выдаче каждого нового слова перебираем все возможные перестановки уже выданных слов и выдаем их. Перечислитель для <tex> L_1 L_2 </tex> строим следующим образом: запускаем одновременно перечислители для <tex> L_1 </tex> и <tex> L_2 </tex>, запоминая все выданные слова. При выдаче новых слов перебираем все возможные пары из запомненных слов и выдаем их.  Рассмотрим язык <tex> \bar{L_1} </tex>. Предположим, что он перечислим. Тогда имея какое-либо слово, мы можем одновременно запустить перечислители для <tex> L_1 </tex> и <tex> \bar{L_1} </tex>. В какой-то момент времени слово появится либо в выводе перечислителя для <tex> L_1 </tex>, либо в выводе перечислителя для <tex> \bar{L_1} </tex>. Тогда получится что <tex> L_1 </tex> разрешим, так как про любое слово мы можем узнать принадлежит оно <tex> L_1 </tex> или не принадлежит. Но мы знаем, что существуют перечислимые, но не разрешимые языки, следовательно, язык <tex> \bar{L_1} </tex> может быть не перечислим. Теперь рассмотрим <tex> L_1 \backslash L_2 </tex>. В качестве <tex> L_1 </tex> возьмем язык, состоящий из всех слов. Тогда получится, что язык <tex> L_1 \backslash L_2 </tex> это <tex> \bar{L_2} </tex>. Про язык <tex> \bar{L_2} </tex> мы знаем, что он перечислим не всегда, следовательно и язык <tex> L_1 \backslash L_2 </tex> также не всегда перечислим.