Теорема о рекурсии — различия между версиями
м |
м |
||
| Строка 10: | Строка 10: | ||
<code><font size = "3em"> | <code><font size = "3em"> | ||
| − | 01: r(y){ | + | 01: r(y){ |
02: V(x,y); | 02: V(x,y); | ||
03: | 03: | ||
| Строка 16: | Строка 16: | ||
05: return V(getSrc(), y) | 05: return V(getSrc(), y) | ||
06: } | 06: } | ||
| − | 07: | + | 07: |
08: string getSrc() { | 08: string getSrc() { | ||
09: string tmp = getOtherSrc(); | 09: string tmp = getOtherSrc(); | ||
| − | 10: return (tmp + "string getOtherSrc() {" + \n + "return | + | 10: return (tmp + "string getOtherSrc() {" + "\n" + "return" + tmp + "\n" + "}"; |
11: } | 11: } | ||
12: | 12: | ||
13: string getOtherSrc() { | 13: string getOtherSrc() { | ||
| − | 14: return /* | + | 14: return /* весь код до функции getOtherSrc() */ |
15: } | 15: } | ||
16: } | 16: } | ||
</font></code> | </font></code> | ||
| + | }} | ||
| + | '''Замечание:''' программа r(y) печатает свой текст. Она написана в соответствии со следующей неформальной инструкцией: | ||
| + | |||
| + | Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:" | ||
==Источники== | ==Источники== | ||
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999 | Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999 | ||
| − | |||
Версия 08:00, 8 декабря 2010
Эта статья находится в разработке!
Теорема о рекурсии
Говоря неформально, теорема о рекурсии позволяет утверждать, что любая программа может использовать внутри себя свой исходный код (номер), который ей передали в качестве параметра.
| Теорема (О рекурсии): |
Для вычислимой функции от двух аргументов вычислимая функция |
| Доказательство: |
|
Пусть - любая вычислимая функция. Напишем программу для 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: }
|
Замечание: программа r(y) печатает свой текст. Она написана в соответствии со следующей неформальной инструкцией:
Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:"
Источники
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
