1679
правок
Изменения
merge
{{Определение
|definition =
'''Перечислимый язык''' {{---}} язык, для которого существует программа <tex>g</tex> такая, что <tex>g(i) = x_i, L = \{x_1, x_2, .., x_n, ..\}</tex>. Язык <tex>L</tex> называется '''коперечислимым''', если <tex>\overline L</tex> {{---}}перечислимый.
}}
{{Определение
|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>L</tex> является перечислимым.
}}
{{Теорема
|statement=
<tex>L</tex> {{---}} перечислим и коперечислим <tex>\Rightarrow</tex> <tex>L</tex> {{---}} [[Разрешимые_(рекурсивные)_языки|разрешим]].
|proof=
Рассмотрим полуразрешители для <tex>L</tex> и <tex>\overline L</tex> и одновременно запустим их для одного и того же элемента <tex>x</tex>. <tex>x</tex> принадлежит либо <tex> L </tex>, либо <tex>\overline{L}</tex>, поэтому один из полуразрешителей успешно отработает и не зависнет. Значит, мы за конечное время узнаем, лежит ли <tex>x</tex> в <tex>L</tex> или нет. Таким образом, мы построили разрешитель для <tex>L</tex>, то есть <tex>L</tex> {{---}} разрешимый.
}}
== Литература ==
* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. {{---}} М.: МЦНМО, 1999. С. 134. ISBN 5-900916-36-7
