Просмотр исходного текста страницы Теорема о рекурсии

{{В разработке}}
==Теорема о рекурсии==
Говоря неформально, теорема о рекурсии позволяет утверждать, что любая программа может использовать внутри себя свой исходный код (номер), который ей передали в качестве параметра.
{{Теорема
|id=th1
|about=О рекурсии
|statement=Для <tex>\forall</tex> вычислимой функции от двух аргументов <tex>V(x, y)</tex> <tex>\exists</tex> вычислимая функция <tex>r(y) : r(y) = V(r, y).</tex>
|proof=
Пусть <tex>V(x,y)</tex> - любая вычислимая функция. Напишем программу для r(y).

<code><font size = "3em">
 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: }
</font></code>
}}
'''Замечание:''' программа r(y) печатает свой текст. Она написана в соответствии со следующей неформальной инструкцией:

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