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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{В разработке}} {{Теорема |id=th1 |about=О рекурсии |statement=Для <tex>\forall</tex> вычислимой функции от дву…»)
(нет различий)

Версия 05:34, 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).

r(y) {
   V(x,y);
   main() {
       return V(getSrc(), y)
   }
   string getSrc() {
       string tmp = getOtherSrc();
       return (tmp + "string getOtherSrc() {" + \n + "return ... " + tmp + "}";
   }
   string getOtherSrc() {
       return "..."
   }
[math]\triangleleft[/math]