Теорема о рекурсии — различия между версиями
(Новая страница: «{{В разработке}} {{Теорема |id=th1 |about=О рекурсии |statement=Для <tex>\forall</tex> вычислимой функции от дву…») |
м |
||
| Строка 8: | Строка 8: | ||
<code><font size = "3em"> | <code><font size = "3em"> | ||
| − | 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: } | ||
</font></code> | </font></code> | ||
}} | }} | ||
Версия 05:39, 8 декабря 2010
Эта статья находится в разработке!
| Теорема (О рекурсии): |
Для вычислимой функции от двух аргументов вычислимая функция |
| Доказательство: |
|
Пусть - любая вычислимая функция. Напишем для нее 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: }
|
