Изменения
Нет описания правки
{{Определение
|definition =
Пусть имеется некоторая программа <tex>p</tex>, которая может либо завершиться за конечное время и что-то вернуть, либо зависнуть. Тогда запуск программы <tex>p</tex> с тайм-лимитом <tex>TL</tex> будем обозначать как <tex>p|_{TL}</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> полуразрешимый.
|proof=
Пусть <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>g_0(i):</tex>
<tex>cnt = 0</tex>
for <tex> k = 1 ~ .. ~ \infty</tex>
for <tex> x \in \{x_1, x_2, .., x_k\}</tex>
if <tex> p|_k(ix) == 1</tex>
<tex>cnt</tex>++
if <tex> cnt == i</tex>
return <tex> x</tex>
<tex>U.insert(x)</tex>
На каждой итерации цикла программы <tex>g</tex>, в множестве <tex>U</tex>, хранятся все выведенные на данный момент слова языка <tex>L</tex>.
Приведённые программы доказывают эквивалентность определений.
}}
|id=th2
|statement=
Любой [[Разрешимые_(рекурсивные)_языки | разрешимый язык ]] <tex>L</tex> является перечислимым.
|proof=
Любой разрешимый язык <tex>L</tex> является полуразрешимым. А так как любой полуразрешимый язык является перечислимым, то разрешимый язык <tex>L</tex> является перечислимым.
}}
== Литература ==
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
