Введение

Быстрорастущая функция, математическая функция.

В теории вычислимости функция Аккермана, названная в честь Вильгельма Аккермана, является одним из самых простых и ранних обнаруженных примеров тотальной вычислимой функции, которая не является примитивно рекурсивной. Все примитивно рекурсивные функции тотальны и вычислимы, но функция Аккермана демонстрирует, что не все тотальные вычислимые функции являются примитивно рекурсивными. После публикации Аккерманом своей функции (которая имела три неотрицательных целочисленных аргумента), многие авторы модифицировали её для различных целей, поэтому сегодня "функция Аккермана" может относиться к любому из многочисленных вариантов исходной функции. Одной из распространённых версий является двух аргументная функция Аккермана — Пете́ра, разработанная Ро́зой Пе́тером и Рафаэлем Робинсоном. Её значение растёт очень быстро; например, даёт , целое число, состоящее из 19 729 десятичных цифр.

Вычисления

Рекурсивное определение функции Аккермана может быть естественно преобразовано в систему переписывания термов (TRS).

Общие замечания

Может быть не сразу очевидно, что вычисление всегда завершается. Однако рекурсия ограничена, поскольку в каждом рекурсивном вызове либо уменьшается, либо остается неизменным, а уменьшается. Каждый раз, когда достигает нуля, уменьшается, поэтому в конечном итоге достигает нуля и тоже. (Выражаясь более технически, в каждом случае пара уменьшается в лексикографическом порядке на парах, что является хорошим порядком, как и порядок отдельных неотрицательных целых чисел; это означает, что нельзя бесконечное число раз подряд уменьшать значение в этом порядке.) Однако, когда уменьшается, нет верхней границы для того, насколько может увеличиться , и часто она увеличивается значительно. Для небольших значений m, таких как 1, 2 или 3, функция Аккермана растет относительно медленно по отношению к n (не более чем экспоненциально). Однако для она растет гораздо быстрее; даже составляет около 2,00353, а десятичное представление составляет около 2,12004, что очень велико по любым обычным меркам. Интересно, что единственная арифметическая операция, которую она использует, — это добавление 1. Ее быстрорастущая сила основана исключительно на вложенной рекурсии. Это также подразумевает, что время ее выполнения, по крайней мере, пропорционально ее результату, и, следовательно, также чрезвычайно велико. Фактически, в большинстве случаев время выполнения намного превышает результат; см. выше. Одноаргументная версия, которая одновременно увеличивает и , превосходит каждую примитивно рекурсивную функцию, включая очень быстрорастущие функции, такие как экспоненциальная функция, факториальная функция, мультифакториальная и суперфакториальная функции, и даже функции, определенные с использованием нотации стрелки Кнута (за исключением случаев, когда используется индексированная стрелка). Можно видеть, что примерно сопоставима с в быстрорастущей иерархии. Этот экстремальный рост можно использовать для доказательства того, что, что очевидно вычислимо на машине с бесконечной памятью, такой как машина Тьюринга, и, следовательно, является вычислимой функцией, растет быстрее, чем любая примитивно рекурсивная функция, и, следовательно, не является примитивно рекурсивной.

Использование в вычислительной сложности

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

Использование в качестве эталонного показателя

Функция Аккермана, благодаря своему определению, основанному на чрезвычайно глубокой рекурсии, может использоваться как эталон для оценки способности компилятора оптимизировать рекурсию. Первое опубликованное применение функции Аккермана в этом качестве было осуществлено в 1970 году Драгошем Вайдой и почти одновременно, в 1971 году, Ингве Сундбладом. Знаковая работа Сундблада была продолжена Брайаном Вичманом (соавтором эталонного теста Whetstone) в серии из трех статей, написанных в период с 1975 по 1982 год.