Изменения
→Теорема о рекурсии
|about=о рекурсии / ''Kleene's recursion theorem''
|statement= Пусть <tex>V(n, x)</tex> {{---}} [[Вычислимые функции|вычислимая функция]]. Тогда найдётся такая вычислимая <tex>p</tex>, что <tex>\forall y:</tex> <tex>p(y) = V(p, y)</tex>.
|proof=Приведем конструктивное доказательство теоремы. Введем новые обозначения для псевдокода. Внутри блока '''function''' располагаются функции, среди которых есть функция <tex>\mathrm{main}</tex>:
'''function''' p('''int''' x):
...
Тогда вызов <tex>\mathrm{p(x)}</tex> — вызов функции <tex>\mathrm{main}</tex> от соответствующего аргумента.
Пусть есть вычислимая <tex>V(x,y)</tex>. Будем поэтапно строить функцию <tex>p(y)</tex>. <br> Предположим, что у нас в распоряжении есть функция <tex>\mathrm{getSrc()}</tex>, которая вернет код <tex>p(y)</tex>. Тогда саму <tex>p(y)</tex> можно переписать так:
'''function''' p('''int''' y):
