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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 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> - любая вычислимая функция. Напишем для нее r(y).
+
Пусть <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

Эта статья находится в разработке!

Теорема о рекурсии

Говоря неформально, теорема о рекурсии позволяет утверждать, что любая программа может использовать внутри себя свой исходный код (номер), который ей передали в качестве параметра.

Теорема (О рекурсии):
Для [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:
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
[math]\triangleleft[/math]