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