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

Эта статья находится в разработке!

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

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

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

Для [math]\forall[/math] вычислимой функции от двух аргументов [math]V(x, y)[/math] [math]\exists[/math] вычислимая функция [math]r(y) : r(y) = V(r, y).[/math]

Доказательство:

[math]\triangleright[/math]

Пусть [math]V(x,y)[/math] - любая вычислимая функция. Напишем программу для r(y). 01: r(y){ 02: V(x,y); 03: 04: main() { 05: return V(getSrc(), y) 06: } 07: 08: string getSrc() { 09: string tmp = getOtherSrc(); 10: return (tmp + "string getOtherSrc() {" + "\n" + "return" + tmp + "\n" + "}"; 11: } 12: 13: string getOtherSrc() { 14: return /* весь код до функции getOtherSrc() */ 15: } 16: }

[math]\triangleleft[/math]

Замечание: программа r(y) печатает свой текст. Она написана в соответствии со следующей неформальной инструкцией:

Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:"

Источники

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