Теорема о рекурсии

Материал из Викиконспекты
Перейти к: навигация, поиск

Теорема о рекурсии

Теорема (О рекурсии):
Пусть [math]U[/math] - универсальная функция, [math]h[/math] - всюду определенная вычислимая функция. Тогда найдется такое [math]n[/math], что [math]U_n=U_{h(n)}[/math]


Источники

Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999