Рекурсивная функция (теория вычислимости): различия между версиями

Нет описания правки
(перенес императивную аналогию соответствующую примитивно-рекурсивным в соответствующий раздел)
Термин '''рекурсивная функция''' в [[Теория вычислимости|теории вычислимости]] используется для обозначения трёх классов функций
* [[#Примитивно рекурсивная функция|примитивно рекурсивные функции]];
* [[#ОбщерекурсивнаяЧастично рекурсивная функция|общерекурсивныечастично рекурсивные функции]];
* [[#Частично рекурсивнаяОбщерекурсивная функция|частично рекурсивныеобщерекурсивные функции]].
 
Последние совпадают с классом [[Вычислимые функции|вычислимых по Тьюрингу функций]]. Определения этих трёх классов сильно связаны. Они были введены [[Гёдель, Курт|Куртом Гёделем]] с целью формализации понятия вычислимости.
Анонимный участник