Изменения
Нет описания правки
<tex>L</tex> {{---}} перечислимый <tex>\Leftrightarrow L</tex> {{---}} полуразрешимый.
|proof=
Пусть <tex>L</tex> {{---}} перечислимый язык, тогда для него существует программа <tex>g</tex> которая по номеру <tex>i</tex> выводит слово из <tex>L</tex>. ДокажемЗначит для <tex>\forall x \in L </tex>, путем перебора значений функции <tex>g</tex>, мы можем найти такое <tex>i</tex>, что он полуразрешим<tex> g(i) </tex> равно <tex> x</tex>. Следовательно существует программа <tex>p</tex> такая, приведя соответствующую программучто <tex>\forall x \in L \Leftrightarrow p(x)=1</tex>. Тогда <tex>L</tex> является полуразрешимым языком.
<tex>p(x):</tex>
for <tex> i = 1 ~ .. ~ \infty</tex>
if <tex> g(i) == x</tex>
return <tex> 1</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> является перечислимым языком.
<tex>g_0(i):</tex>
<tex>cnt = 0</tex>
return <tex> x</tex>
<tex>U.insert(x)</tex>
Приведённые программы доказывают эквивалентность определений.
