69
правок
Изменения
Нет описания правки
Значит, для нашего отношения эквивалентности второе утверждение леммы не верно, то есть для любого вычислимого всюду определенного <tex>h</tex> <tex> \exists n</tex> такое что <tex>U_{h(n)} = U_n</tex>
}}
Теорему о рекурсии можно переформулировать следущим образом.
{{Теорема
|id=th2
|about=О рекурсии
|statement= Пусть <tex>V(n, x)</tex> - вычислимая функция.Тогда найдется такая вычислимая <tex>p</tex>, что <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>
|proof=
}}
==Источники==
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
