Функция Аккермана растёт быстрее любой примитивно-рекурсивной функции.

Функция Аккермана была введена немецким математиком Вильгельмом Аккерманом в 1928 году как пример функции, которая является вычислимой, но не примитивно-рекурсивной. Это открытие стало важной вехой в теории вычислимости, так как показало границы класса функций, определяемых через простую рекурсию. Функция демонстрирует рост, кажущийся невозможно быстрым: уже значение Аккермана(4, 2) представляет собой число с 19 729 цифрами — число столь огромное, что его невозможно записать в видимой Вселенной, даже если каждый атом будет одной цифрой. Примитивно-рекурсивные функции включают в себя основные арифметические операции и циклы с заранее известным числом повторений. Функция Аккермана выходит за эти рамки, требуя более мощной формы рекурсии, где глубина вложенности вызовов зависит от предыдущих вычислений. Это демонстрирует, что даже в области вычислимых функций существует строгая иерархия: есть функции, которые принципиально быстрее растут, чем любая комбинация сложения, умножения и возведения в степень. Значение функции Аккермана выходит далеко за пределы чистой математики. Она служит инструментом для классификации алгоритмов по скорости их роста и используется в анализе сложности вычислений. В информатике родственный концепт — стрелочная нотация Кнута — позволяет записывать числа, которые невозможно выразить традиционными способами.