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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} {{Теорема |id=th1 |about=О рекурсии |statement=Для <tex>\forall</tex> вычислимой функции от дву…»)
 
м
Строка 8: Строка 8:
  
 
<code><font size = "3em">
 
<code><font size = "3em">
  r(y) {
+
  01: r(y) {
    V(x,y);
+
02:    V(x,y);
    main() {
+
03:    main() {
        return V(getSrc(), y)
+
04:        return V(getSrc(), y)
    }
+
05:    }
    string getSrc() {
+
06:    string getSrc() {
        string tmp = getOtherSrc();
+
07:        string tmp = getOtherSrc();
        return (tmp + "string getOtherSrc() {" + \n + "return ... " + tmp + "}";
+
08:        return (tmp + "string getOtherSrc() {" + \n + "return ... " + tmp + "}";
    }
+
09:    }
    string getOtherSrc() {
+
10:    string getOtherSrc() {
        return "..."
+
11:        return /* строки с 01 по 09 */
    }
+
12:    }
 +
13: }
 
</font></code>
 
</font></code>
 
}}
 
}}

Версия 05:39, 8 декабря 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).

01: r(y) {
02:    V(x,y);
03:    main() {
04:        return V(getSrc(), y)
05:    }
06:    string getSrc() {
07:        string tmp = getOtherSrc();
08:        return (tmp + "string getOtherSrc() {" + \n + "return ... " + tmp + "}";
09:    }
10:    string getOtherSrc() {
11:        return /* строки с 01 по 09 */
12:    } 
13: }
[math]\triangleleft[/math]