Теорема о рекурсии — различия между версиями
м |
м |
||
Строка 27: | Строка 27: | ||
</font></code> | </font></code> | ||
}} | }} | ||
− | '''Замечание:''' | + | '''Замечание:''' Если бы требовалось написать программу, выводящую свой код, это можно было бы сделать в соответствии со следующей неформальной инструкцией: |
Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:" | Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:" |
Версия 02:11, 10 декабря 2010
Теорема о рекурсии
Говоря неформально, теорема о рекурсии позволяет утверждать, что любая программа может использовать внутри себя свой исходный код (номер), который ей передали в качестве параметра.
Теорема (О рекурсии): |
Для вычислимой функции от двух аргументов вычислимая функция |
Доказательство: |
Пусть - любая вычислимая функция. Напишем программу для 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() */ } } |
Замечание: Если бы требовалось написать программу, выводящую свой код, это можно было бы сделать в соответствии со следующей неформальной инструкцией:
Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:"
Источники
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999