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

м
→‎Свойства: оформление
м (отмена правки 64131717 участника 5.206.116.219 (обс))
м (→‎Свойства: оформление)
 
Как было показано [[Гёдель, Курт|Гёделем]], частично рекурсивные функции совпадают с множеством [[Вычислимые функции|вычислимых функций]].{{нет АИ|1|02|2012}}<!-- Это же тезис Чёрча — Тьюринга. Что именно доказал Гёдель? -->
 
<!-- Гедель и Эрбран доказали, что всякая частично-рекурсивная функция ЭГ-вычислима, мендельсон «Введение в математическую логику», стр.263 -->