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

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