Изменения

Перейти к: навигация, поиск

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

983 байта убрано, 09:27, 29 декабря 2011
Нет описания правки
|id=th1
|about=О рекурсии
|statement=Для Пусть <tex>\forallU</tex> - [[Вычислимые функцииДиагональный_метод|вычислимой функцииуниверсальная функция]] от двух аргументов <tex>V(x, y)</tex> <tex>\existsh</tex> - всюду определенная [[Вычислимые функцииВычислимые_функции|вычислимая функция]] . Тогда найдется такое <tex>r(y) : r(y) n</tex>, что <tex>U_n= VU_{h(r, yn).}</tex>
|proof=
Пусть <tex>V(x,y)</tex> - любая вычислимая функция. Напишем программу для r(y).
<code><font size = "3em">
r(y){
V(x,y) {...}
main() {
return V(getSrc(), y)
}
string getSrc() {
string tmp = getOtherSrc();
return (tmp + "string getOtherSrc() {" + "\n" + "return" + tmp + "\n" + "}";
}
string getOtherSrc() {
return /* весь код до функции getOtherSrc() */
}
}
</font></code>
}}
'''Замечание:''' Если бы требовалось написать программу, выводящую свой код, это можно было бы сделать в соответствии со следующей неформальной инструкцией:
Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:"
==Источники==
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
Grechko
69
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/15334»

Навигация