Функция Аккермана

Функция Аккермана — это одна из простейших по определению, но быстрорастущих вычислимых функций в теории рекурсии. Она является классическим примером всюду определённой рекурсивной функции, которая не является примитивно рекурсивной. Функция Аккермана демонстрирует, что не все вычислимые функции могут быть построены с помощью ограниченного набора операций примитивной рекурсии, и служит важным инструментом для изучения сложности вычислений и границ формальных систем.

История

Функция была впервые описана в 1928 году немецким математиком Вильгельмом Аккерманом (Wilhelm Ackermann) в контексте его работы по основаниям математики. Аккерман стремился доказать, что существуют вычислимые функции, которые не являются примитивно рекурсивными, то есть не могут быть получены из простейших функций (нуля, следования и проекции) с помощью конечного числа операций суперпозиции и примитивной рекурсии. Его первоначальная функция была определена для трёх аргументов и росла значительно быстрее, чем любая примитивно рекурсивная функция.

В 1935 году американский логик Рафаэль Робинсон (Raphael M. Robinson) упростил определение, сведя его к двум аргументам. В 1948 году Роза Петер (Rózsa Péter), венгерский математик, также независимо разработала аналогичную функцию. Впоследствии, в 1950-х годах, Ханс Радо (Hans Radó) и другие исследователи использовали функцию Аккермана для анализа сложности алгоритмов и теории вычислимости. В 1963 году Ричард Бак (Richard Buck) предложил её компактное представление через бинарную операцию «стрелочная нотация Кнута», что сделало её рост наглядным.

Определение

Существует несколько эквивалентных вариантов определения функции Аккермана. Наиболее распространённым является вариант для двух неотрицательных целых аргументов \( m \) и \( n \), обозначаемый как \( A(m, n) \). Определение задаётся рекурсивно:

\[ A(m, n) = \begin{cases} n + 1 & \text{если } m = 0 \\ A(m - 1, 1) & \text{если } m > 0 \text{ и } n = 0 \\ A(m - 1, A(m, n - 1)) & \text{если } m > 0 \text{ и } n > 0 \end{cases} \]

Это определение является рекурсивным, но не примитивно рекурсивным, так как в третьем случае функция вызывает саму себя с аргументом, который сам является результатом рекурсивного вызова. Такая двойная рекурсия приводит к экспоненциальному росту глубины вычислений.

Примеры вычислений

Для малых значений \( m \) и \( n \) функция Аккермана принимает следующие значения:

• \( A(0, n) = n + 1 \)
• \( A(1, n) = n + 2 \)
• \( A(2, n) = 2n + 3 \)
• \( A(3, n) = 2^{n+3} - 3 \)
• \( A(4, n) = 2^{2^{2^{\cdots^{2}}}} - 3 \) (степенная башня высотой \( n+3 \))

Таблица значений для малых \( m \) и \( n \):

Уже при \( A(4, 2) \) значение составляет \( 2^{65536} - 3 \), что является числом с более чем 19 729 десятичными цифрами. Для \( m = 5 \) и \( n = 1 \) функция Аккермана даёт число, которое невозможно записать в обычной десятичной системе из-за его колоссального размера.

Свойства

Функция Аккермана обладает рядом важных свойств:

1. Всюду определённость: Для любых неотрицательных целых \( m \) и \( n \) значение \( A(m, n) \) конечно и вычислимо за конечное число шагов.
2. Монотонность: Функция строго возрастает по каждому аргументу. То есть, если \( m_1 < m_2 \), то \( A(m_1, n) < A(m_2, n) \), и если \( n_1 < n_2 \), то \( A(m, n_1) < A(m, n_2) \).
3. Непримитивная рекурсивность: Функция Аккермана является вычислимой, но не является примитивно рекурсивной. Это означает, что её нельзя выразить через конечное число применений операций примитивной рекурсии и суперпозиции. Доказательство этого факта основано на том, что любая примитивно рекурсивная функция растёт медленнее, чем \( A(m, n) \) при фиксированном \( m \).
4. Сверхэкспоненциальный рост: Скорость роста функции Аккермана намного превосходит любую экспоненциальную функцию, факториал или даже степенную башню. Для \( m \ge 4 \) её рост становится астрономическим.
5. Рекурсивная, но не примитивно рекурсивная: Она является классическим примером, разделяющим классы примитивно рекурсивных и общерекурсивных функций.

Применение

Несмотря на свою абстрактность, функция Аккермана находит применение в нескольких областях:

Теория вычислимости

Функция Аккермана является стандартным контрпримером, демонстрирующим, что не всякая рекурсивная функция является примитивно рекурсивной. Она используется для иллюстрации границ формальных систем, таких как арифметика Пеано, и для изучения иерархий сложности.

Анализ алгоритмов

В информатике функция Аккермана используется для анализа сложности некоторых алгоритмов, особенно тех, которые работают с обратными функциями. Например, обратная функция Аккермана \( \alpha(n) \) растёт чрезвычайно медленно. Она встречается в анализе времени работы алгоритмов для задачи поиска минимального остовного дерева (алгоритм Борувки, алгоритм Крускала с оптимизацией по рангу), в алгоритмах для работы с непересекающимися множествами (Union-Find) и в некоторых алгоритмах сортировки. Для всех практически возможных значений \( n \) (вплоть до \( 10^{100} \)) обратная функция Аккермана не превышает 5.

Тестирование производительности компиляторов и интерпретаторов

Из-за своей глубокой рекурсии функция Аккермана используется как эталонный тест для оценки эффективности реализации рекурсии в языках программирования. Вычисление \( A(4, 1) \) или \( A(4, 2) \) требует огромного количества рекурсивных вызовов (миллиарды), что позволяет выявить узкие места в управлении стеком, оптимизации хвостовой рекурсии и производительности интерпретаторов.

Теория сложности

Функция Аккермана используется для построения иерархий сложности, таких как иерархия Гжегорчика, где она служит границей между классами функций. Она также применяется в теории рекурсивных функций для определения понятия «вычислимой функции» и для демонстрации того, что не все вычислимые функции являются примитивно рекурсивными.

Интересные факты

• Функция Аккермана является одной из первых функций, для которой было доказано, что она вычислима, но не является примитивно рекурсивной. Это стало важным шагом в развитии теории вычислимости.
• Для \( m = 4 \) и \( n = 2 \) значение функции настолько велико, что его невозможно записать в обычной десятичной системе счисления, используя все атомы во Вселенной в качестве цифр.
• Обратная функция Аккермана \( \alpha(n) \) растёт настолько медленно, что для всех практически возможных значений \( n \) она равна 4 или 5. Это делает её «почти константой» в анализе алгоритмов.
• Существуют различные варианты функции Аккермана, включая трёхаргументную версию, предложенную самим Аккерманом, и двухаргументную версию, которая стала стандартной.
• Функция Аккермана тесно связана с стрелочной нотацией Кнута: \( A(m, n) \) можно выразить как \( 2 \uparrow^{m-2} (n+3) - 3 \), где \( \uparrow^{k} \) обозначает \( k \)-ю стрелочную операцию.

Источники

• Аккерман, В. (1928). «Zum Hilbertschen Aufbau der reellen Zahlen». Mathematische Annalen.
• Робинсон, Р. М. (1935). «Recursion and double recursion». Bulletin of the American Mathematical Society.
• Петер, Р. (1967). Рекурсивные функции. Издательство «Мир».
• Бак, Р. (1963). «Mathematical Induction and Recursive Definitions». The American Mathematical Monthly.
• Кнут, Д. Э. (1976). «Mathematics and Computer Science: Coping with Finiteness». Science.
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. (2013). Алгоритмы: построение и анализ. Издательство «Вильямс».