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

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