271
правка
Изменения
Нет описания правки
{{Определение
|definition =
'''Полуразрешимый язык''' <tex>{{-</tex> --}} язык, для которого существует программа <tex>p</tex> такая, что <tex>\forall x \in L \Leftrightarrow p(x)=1</tex>.
}}
{{Определение
|definition =
'''Перечислимый язык''' <tex>{{-</tex> --}} язык, для которого существует программа <tex>g</tex> такая, что <tex>g(i) = x_i, L = \{x_1, x_2, .., x_n, ..\}</tex>.
}}
|id=th1
|statement=
<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>
return <tex> x</tex>
<tex>U.insert(x)</tex>
На каждой итерации цикла программы <tex>g</tex>, в множестве <tex>U</tex>, хранятся все выведенные на данный момент слова языка <tex>L</tex>.
Приведённые программы доказывают эквивалентность определений.
Любой [[Разрешимые_(рекурсивные)_языки | разрешимый язык]] <tex>L</tex> является перечислимым.
|proof=
Любой разрешимый язык <tex>L</tex> является полуразрешимым. А так Так как любой полуразрешимый язык является перечислимым, то разрешимый язык <tex>L</tex> является перечислимым.
}}
== Литература ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
