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

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

Говоря неформально, теорема о рекурсии позволяет утверждать, что любая программа может использовать внутри себя свой исходный код (номер), который ей передали в качестве параметра.

Теорема (О рекурсии):

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

Источники

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