Изменения

Пусть <tex>L</tex> {{---}} перечислимый язык, тогда . Тогда для него существует программа <tex>g</tex> , которая по номеру <tex>i</tex> выводит слово из <tex>L</tex>. Значит , для всех <tex>\forall x \in </tex> из <tex>L </tex>, путем перебора значений функции <tex>g</tex>, мы можем найти такое <tex>i</tex>, что <tex> g(i) </tex> равно <tex> = x</tex>. Следовательно , существует программа <tex>p</tex> , такая, что <tex>\forall x: x \in L \Leftrightarrow p(x)=1</tex>. Тогда <tex>L</tex> является полуразрешимым языком.

Пусть <tex>L</tex> {{---}} полуразрешимый язык, тогда . Тогда для него существует программа <tex>p</tex>, результат которой равен <tex>1</tex> для любого слова из <tex>L</tex>. Чтобы программа <tex>p</tex> не зависала на словах , которые не принадлежат <tex>L</tex>, будем запускать ее с тайм-лимитом. Для поиска <tex>i</tex> -го слова из языка <tex>L</tex> будем перебирать <tex>k</tex> {{---}} тайм-лимит с которым будем запускать программу <tex>p</tex>. Таким образом существует программа <tex>g_0</tex>, которая выводит <tex>i</tex> слово языка <tex>L</tex> с повторениями. Для того, чтобы выводить слова без повторений , заведем множество <tex>U</tex>, в котором будем хранить уже выведенные слова. Программа <tex>g</tex> доказывает, что <tex>L</tex> является перечислимым языком.