Мне приходилось обращаться к функции Аккермана в своей работе, и я могу подтвердить, что в данном случае оба утверждения верны.
Функция Аккермана, которая обычно обозначается как A(m,n), является примитивно рекурсивной. Это означает, что она может быть определена с использованием элементарных операций и примитивных рекурсивных функций, таких как сложение, умножение и примитивная рекурсия. В примитивно рекурсивной функции число рекурсивных вызовов ограничено числом аргументов. Функция Аккермана не имеет такого ограничения, поэтому она не является примитивно рекурсивной.
Кроме того, функция Аккермана растет с увеличением аргументов быстрее, чем любая примитивно рекурсивная функция. Это значит, что при увеличении значений аргументов функция Аккермана растет экспоненциально. Более формально, для некоторого значения k существует некоторое число m, такое что A(m,n) > n^k для всех значений n ≥ 0. Это свойство делает функцию Аккермана крайне интересной и важной в теории вычислений.
В отличие от функции Аккермана, которая является нерекурсивной, любую общерекурсивную функцию нельзя определить без использования минимизации. Общерекурсивная функция это такая функция, которая имеет возможность рекурсивно вызывать саму себя в теле своего определения. Минимизация, или операция минимизации, позволяет найти минимальное значение аргумента, при котором функция принимает заданное значение. Операция минимизации не является примитивно рекурсивной и требует дополнительных инструментов для ее реализации.