Рекурсивная функция (теория вычислимости)
Материал из Википедии — свободной encyclopedia
Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций:
Эту страницу предлагается объединить со страницей Вычислимая функция. |
У этого термина существуют и другие значения, см. Рекурсивная функция (значения).
Последние совпадают с классом вычислимых по Тьюрингу функций. Определения этих трёх классов сильно связаны. Они были введены Куртом Гёделем с целью формализации понятия вычислимости.
Множество частично рекурсивных функций включает в себя множество общерекурсивных функций, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями.