57
правок
Изменения
м
→Теорема о рекурсии
|id=th1
|about=О рекурсии
|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).
Напечатать два раза, второй раз в кавычках, такой текст: "Напечатать два раза, второй раз в кавычках, такой текст:"
==Источники==
Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. -- М.: МЦНМО, 1999
