Изменения

Полуразрешающая программа для языка <tex>L</tex> - программа, которая при подаче на вход слова из языка за конечное время завершится и вернет <tex>1</tex>, а при подаче на вход слова не из языка может за конечное время вернуть <tex>0</tex>, а может и зависнуть.

Пусть имеется перечисляющая программа для языка<tex>L</tex>, построим полуразрешающую. Сделаем это следующим образом. Получаем на вход некоторое слово <tex>w</tex>, запускаем перечисляющую программу. Если в процессе вывода слов встретится <tex>w</tex>, то завершаем работу, вернув <tex>1</tex>. Таким образом при подаче на вход слова из языка построенная программа вернет <tex>1 </tex> и завершится. Если же мы подадим на вход слово не из языка, то построенная программа будет работать бесконечно долго, что вполне устраивает. Таким образом полуразрешающая программа построена.

Теперь пусть имеется полуразрешающая программа <tex>p</tex> для языка<tex>L</tex>, построим перечисляющую. : for <tex>TL</tex> = <tex>1</tex> .. <tex>+\infty</tex> {:: for <tex>length</tex> = <tex>1</tex> .. <tex>TL</tex> {::: for <tex>w \in L</tex>, <tex>|w| = length</tex> { :::: if <tex>p|_{TL}(w)=1</tex>::::: выводим <tex>w</tex>;:::}::}:} Если слово <tex>w</tex> принадлежит языку, то условие <tex>p|_{TL}(w)=1</tex> будет выполнено для какого-то <tex>TL</tex>, а значит на выходе построенной программы рано или поздно появится <tex>w</tex>. Если же слово <tex>w</tex> не принадлежит языку, то <tex>p|_{TL}(w)=1</tex> ну будет выполнено ни для какого <tex>TL</tex>, а значит оно никогда не появится на выходе. Таким образом мы построили перечисляющую программу. В итоге теорема доказана.