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

 
Довольно сложно доказать существование и привести пример общерекурсивной функции, не являющейся примитивно рекурсивной. Одним из популярных примеров является [[функция Аккермана]].
Есть попроще пример общерекурсивной функции, не являющийся примитивно рекурсивной - он строится диагональным методом Кантора из универсальной функции для множества одноместных примитивно рекурсивных функций.
 
Как было показано [[Гёдель, Курт|Гёделем]], частично рекурсивные функции совпадают с множеством [[Вычислимые функции|вычислимых функций]].