65
правок
Изменения
Нет описания правки
Следует из второго свойства.
}}
== Применение ==
Этой леммой удобно пользоваться для доказательств неразрешимости различных задач. Например, [[Примеры неразрешимых задач: проблема соответствий Поста|проблемы соответствий Поста]], [[Примеры неразрешимых задач: однозначность грамматики|задачи однозначности КС-грамматики]] или проверки, выводится ли в КС-грамматике хотя бы один палиндром.
== Литература ==
* ''Верещагин Н., Шень А.'' — '''Вычислимые функции''', 2-е изд. МЦНМО, 2002. ISBN 5-900916-36-7
* ''P. Odifreddi'' — '''Classical recursion theory'''. Elsivier, 1992. ISBN 0-444-87295-7
{{Заголовок со строчной буквы}}
