Теорема о рекурсии — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 27: Строка 27:
 
</font></code>
 
</font></code>
 
}}
 
}}
'''Замечание:''' программа r(y) печатает свой текст. Она написана в соответствии со следующей неформальной инструкцией:
+
'''Замечание:''' Если бы требовалось написать программу, выводящую свой код, это можно было бы сделать в соответствии со следующей неформальной инструкцией:
  
 
Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:"
 
Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:"

Версия 02:11, 10 декабря 2010

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

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

Теорема (О рекурсии):
Для [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).

 r(y){ 
     V(x,y) {...}

     main() {
         return V(getSrc(), y)
     }
 
     string getSrc() {
         string tmp = getOtherSrc();
         return (tmp + "string getOtherSrc() {" + "\n" + "return" + tmp + "\n" + "}";
     }
 
     string getOtherSrc() {
         return /* весь код до функции getOtherSrc() */
     } 
 }
[math]\triangleleft[/math]

Замечание: Если бы требовалось написать программу, выводящую свой код, это можно было бы сделать в соответствии со следующей неформальной инструкцией:

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

Источники

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