Изменения

Перечисляющая '''Полуразрешимый язык''' <tex>-</tex> язык, для которого существует программа для языка <tex>Lp</tex> - программатакая, по очереди выводящая все слова языка что <tex>\forall x \in L\Leftrightarrow p(x)=1</tex>. Если слово принадлежит языку, то программа за конечное время выдаст его на выходе. Слова, не принадлежащие языку, программа выводить не будет.

Полуразрешающая программа для языка '''Перечислимый язык''' <tex>L-</tex> - язык, для которого существует программа, которая при подаче на вход слова из языка за конечное время завершится и вернет <tex>1g</tex>такая, а при подаче на вход слова не из языка может за конечное время вернуть что <tex>0g(i) = x_i, L = \{x_1, x_2, .., x_n, ..\}</tex>, а может и зависнуть.

Перечислимый язык Пусть имеется некоторая программа <tex>p</tex>, которая может либо завершиться за конечное время и что- языкто вернуть, для которого существует перечисляющая программалибо зависнуть.Тогда запуск программы <tex>p</tex> с тайм-лимитом <tex>TL</tex> будем обозначать как <tex>p|_{TL}} {{Определение|definition =Перечислимый язык </tex> и иметь в виду следующее: если за <tex>TL</tex> операций программа <tex>p</tex> корректно завершилась и что- языкто вернула, для которого существует полуразрешающая то <tex>p|_{TL}</tex> вернет то же самое; если же за <tex>TL</tex> операций программа<tex>p</tex> не успела завершиться, то <tex>p|_{TL}</tex> вернет <tex>\bot</tex> (специально зарезервированное значение).

Два определения перечислимого языка эквивалентны<tex>L-</tex> перечислимый <tex>\Leftrightarrow L-</tex> полуразрешимый.

Пусть имеется перечисляющая программа для языка <tex>L-</tex>, построим полуразрешающуюперечислимый. Сделаем это следующим образом. Получаем на вход некоторое слово :<tex>wp(x):</tex>, запускаем перечисляющую программу. Если в процессе вывода слов встретится :: <tex>wfor ~ i = 1 ~ .. ~ \infty</tex>, то завершаем работу, вернув ::: <tex>1if ~ g(i) = x</tex>. Таким образом при подаче на вход слова из языка построенная программа вернет :::: <tex>return ~ 1</tex> и завершится. Если же мы подадим на вход слово не из языка, то построенная программа будет работать бесконечно долго, что вполне устраивает. Таким образом полуразрешающая программа построена. Теперь пусть имеется полуразрешающая программа <tex>p</tex> для языка Пусть <tex>L-</tex>, построим перечисляющуюполуразрешимый. : for <tex>TLg_0(i):</tex> = ::<tex>1</tex> .. <tex>+\inftycnt = 0</tex> {:: for <tex>length</tex> for ~ k = <tex>1</tex> ~ .. <tex>TL~ \infty</tex> {::: for <tex>w for ~ x \in L</tex>\{x_1, x_2, .., <tex>|w| = lengthx_k\}</tex> { :::: if <tex>if ~ p|_{TL}_k(wi)=1</tex>::::: выводим <tex>wcnt++</tex>;:::}::}:} Если слово <tex>w</tex> принадлежит языку, то условие <tex>p|_{TL}(w)if ~ cnt =1i</tex> будет выполнено для какого-то ::::: <tex>TLreturn ~ x</tex>, а значит на выходе построенной программы рано или поздно появится <tex>w</tex>. Если же слово <tex>w</tex> не принадлежит языку, то <tex>p|_{TL}(w)=1</tex> ну будет выполнено ни для какого <tex>TL</tex>, а значит оно никогда не появится на выходе.

Таким образом мы построили перечисляющую программу:<tex>g(i):</tex>::<tex>U = \emptyset</tex>:: <tex>for ~ j = 1 ~ .. ~ \infty</tex>::: <tex>x \leftarrow g_0(j)</tex>:::: <tex>if ~ x \notin U</tex>::::: <tex>cnt++</tex>::::: <tex>if ~ cnt = i</tex>:::::: <tex>return ~ x</tex>::::: <tex>U.insert(x)</tex>В итоге теорема доказанаПриведённые программы доказывают эквивалентность определений.

|proof=Язык <tex>L</tex> резрешимый, значит существует программа <tex>p</tex>, которая за конечное время определит, принадлежит ли поданное на вход слово языку Любой разрешимый язык <tex>L</tex>является полуразрешимым. Таким образом перечисляющая программа будет иметь следующий вид. : for <tex>w \in L</tex> { :: if <tex>p(w)=1</tex>::: выводим <tex>w</tex>;:} Таким образомА так как любой полуразрешимый язык является перечислимым, на выходе появится слово то разрешимый язык <tex>w</tex> тогда и только тогда, когда <tex>w \in L</tex>, теорема доказана.}}  {{Теорема|id=th3|statement=Существуют перечислимые, но не разрешимые языкиявляется перечислимым.