Изменения

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

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

3 байта добавлено, 07:10, 24 января 2012
Нет описания правки
|proof=
Приведем конструктивное доказательство теоремы.
Пусть есть вычислимая <tex>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. Предположим что у нас в распоряжении есть функция <tex>getSrc()</tex> , которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
<code><font size = "3em">
string getSrc() {...}
</font></code>
Теперь нужно определить функцию <tex>getSrc()</tex>. Предположим , что внутри <tex>p(y)</tex> мы можем определить функцию <tex>getOtherSrc()</tex> состоящюю , состоящую из одного оператора <tex>return</tex>, которая вернет весь предшествующий ей код. Тогда <tex>p(y)</tex> перепишется так.
<code><font size = "3em">
p(y){
271
правка

Навигация