271
правка
Изменения
Нет описания правки
|id=th1
|about=О рекурсии
|statement= Пусть <tex>V(n, x)</tex> {{---}} вычислимая функция.Тогда найдется найдётся такая вычислимая <tex>p</tex>, что <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>.
|proof=
Приведем конструктивное доказательство теоремы.
Пусть есть вычислимая <tex>V(x,y)</tex>. Введем Введём вспомогательную функцию <tex>getSrc()</tex> следующим образом: <br>
<code> <font size = "3em">
getSrc(){
}
</font> </code>
Заметим, что функция <tex>getSrc()</tex> возвращает код функции <tex>p(y)</tex>, значит поэтому <tex>p(y)</tex> удовлетворяет требованию <tex>\forall y</tex> <tex>p(y) = V(p, y)</tex>. <br>
}}
Если говорить неформально, теорема о рекурсии утверждает, что внутри программы можно использовать ее код. Это упрощает доказательство некоторых теорем.
Приведем так же альтернативую формулировку теоремы, и альтернативное (неконструктивное) доказательство.
{{Теорема
