Перечислимые языки

Определение:

Перечисляющая программа для языка [math]L[/math] - программа, по очереди выводящая все слова языка [math]L[/math]. Если слово принадлежит языку, то программа за конечное время выдаст его на выходе. Слова, не принадлежащие языку, программа выводить не будет.

Определение:

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

Определение:

Перечислимый язык - язык, для которого существует перечисляющая программа.

Определение:

Перечислимый язык - язык, для которого существует полуразрешающая программа.

Теорема:

Два определения перечислимого языка эквивалентны.

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]