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

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