5
правок
Изменения
м
Нет описания правки
В итоге теорема доказана.
}}
{{Теорема
|id=th2
|statement=
Любой разрешимый язык <tex>L</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=
Существуют перечислимые, но не разрешимые языки.
}}
