Функция Аккермана растёт так быстро, что A(4,4) больше числа атомов во Вселенной.

Функция Аккермана, введённая немецким математиком Вильгельмом Аккерманом в 1928 году, стала классическим примером рекурсивной функции с экстремально быстрым ростом. Аккерман определил её как функцию двух переменных A(m, n), где каждый уровень по m добавляет новую операцию: сложение, умножение, возведение в степень и затем операции, выходящие за пределы стандартной арифметики. Значения этой функции растут настолько быстро, что уже при небольших аргументах результаты становятся астрономическими. A(4, 4) содержит настолько много цифр, что количество знаков в его десятичной записи сопоставимо с числом атомов во Вселенной (примерно 10 в степени 80). Для сравнения: A(3, 3) равно 61, A(4, 2) уже превышает 65 тысяч, а A(4, 3) содержит более 19 тысяч цифр. Функция Аккермана имеет фундаментальное значение в теории алгоритмов и вычислимости. Она служит доказательством существования функций, которые являются вычислимыми в классическом смысле, но не могут быть вычислены ни на одной машине Тьюринга за разумное время. Это помогает математикам различать между функциями, которые теоретически можно вычислить, и функциями, которые практически невычислимы. С функцией Аккермана связана иерархия быстрорастущих функций, включая функции Харди и трансконечные ординалы. В информатике она используется при анализе сложности алгоритмов и в теории вычислительных ресурсов. Её изучение показало глубокую связь между логикой, теорией множеств и практическими границами компьютерных вычислений.