Теорема о рекурсии — различия между версиями
м |
м |
||
| Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
| + | ==Теорема о рекурсии== | ||
| + | Говоря неформально, теорема о рекурсии позволяет утверждать, что любая программа может использовать внутри себя свой исходный код (номер), который ей передали в качестве параметра. | ||
{{Теорема | {{Теорема | ||
|id=th1 | |id=th1 | ||
| Строка 5: | Строка 7: | ||
|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> - любая вычислимая функция. Напишем для | + | Пусть <tex>V(x,y)</tex> - любая вычислимая функция. Напишем программу для r(y). |
<code><font size = "3em"> | <code><font size = "3em"> | ||
| Строка 25: | Строка 27: | ||
16: } | 16: } | ||
</font></code> | </font></code> | ||
| + | ==Источники== | ||
| + | Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999 | ||
}} | }} | ||
Версия 06:49, 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 + "}";
11: }
12:
13: string getOtherSrc() {
14: return /* строки с 01 по 12 */
15: }
16: }
ИсточникиН. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999 |
