57
правок
Изменения
м
Нет описания правки
{{В разработке}}
==Теорема о рекурсии==
Говоря неформально, теорема о рекурсии позволяет утверждать, что любая программа может использовать внутри себя свой исходный код (номер), который ей передали в качестве параметра.
{{Теорема
|id=th1
|statement=Для <tex>\forall</tex> вычислимой функции от двух аргументов <tex>V(x, y)</tex> <tex>\exists</tex> вычислимая функция <tex>r(y) : r(y) = V(r, y).</tex>
|proof=
Пусть <tex>V(x,y)</tex> - любая вычислимая функция. Напишем программу для нее r(y).
<code><font size = "3em">
16: }
</font></code>
==Источники==
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
}}
