Теорема о рекурсии — различия между версиями
м |
м (→Теорема о рекурсии) |
||
| Строка 5: | Строка 5: | ||
|id=th1 | |id=th1 | ||
|about=О рекурсии | |about=О рекурсии | ||
| − | |statement=Для <tex>\forall</tex> вычислимой функции от двух аргументов <tex>V(x, y)</tex> <tex>\exists</tex> вычислимая функция <tex>r(y) : r(y) = V(r, y).</tex> | + | |statement=Для <tex>\forall</tex> [[Вычислимые функции|вычислимой функции]] от двух аргументов <tex>V(x, y)</tex> <tex>\exists</tex> [[Вычислимые функции|вычислимая функция]] <tex>r(y) : r(y) = V(r, y).</tex> |
|proof= | |proof= | ||
Пусть <tex>V(x,y)</tex> - любая вычислимая функция. Напишем программу для r(y). | Пусть <tex>V(x,y)</tex> - любая вычислимая функция. Напишем программу для r(y). | ||
| Строка 31: | Строка 31: | ||
Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:" | Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:" | ||
| + | |||
==Источники== | ==Источники== | ||
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999 | Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999 | ||
Версия 07:36, 9 декабря 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() */
}
}
|
Замечание: программа r(y) печатает свой текст. Она написана в соответствии со следующей неформальной инструкцией:
Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:"
Источники
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
