Рекурсивная функция (теория вычислимости): различия между версиями
| [отпатрулированная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Addbot (обсуждение | вклад) м Перемещение 11 интервики на Викиданные, d:q1570472 |
источники |
||
Строка 5:
* [[#Частично рекурсивная функция|частично рекурсивные функции]].
Последние совпадают с классом [[Вычислимые функции|вычислимых по Тьюрингу функций]] {{достоверность}}. Определения этих трёх классов сильно связаны. Они были введены [[Гёдель, Курт|Куртом Гёделем]] с целью формализации понятия вычислимости.
Множество частично рекурсивных функций включает в себя множество общерекурсивных функций, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями.
| |||