Функция Аккермана
Функция Аккермана — простой пример всюду определённой вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается . Эта функция растёт очень быстро, например, число настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной.
История
В конце 20-х годов XX века математики-ученики Давида Гильберта, Габриэль Судан и Вильгельм Аккерман, изучали основы вычислений. Судан и Аккерман известны[1] открытием всюду определённой вычислимой функции (иногда называемой просто «рекурсивной»), не являющейся примитивно рекурсивной. Судан открыл менее известную функцию Судана, после чего, независимо от него, в 1928 году Аккерман опубликовал свою функцию . Функция трёх аргументов Аккермана определялась так, что для она проводила операцию сложения, умножения или возведения в степень:
а для она доопределяется с помощью стрелочной нотации Кнута, опубликованной в 1976 году:
- .
(Помимо её исторической роли как первой всюду определённой не примитивно рекурсивной вычислимой функции, оригинальная функция Аккермана расширяла основные арифметические операции за возведение в степень, хотя и не так хорошо, как специально предназначенные для этого функции вроде последовательности гипероператоров Гудстейна.)
В статье «On the Infinite» Гильберт высказал гипотезу о том, что функция Аккермана не является примитивно рекурсивной, а Аккерман (личный секретарь и бывший студент Гильберта) доказал эту гипотезу в статье «On Hilbert’s Construction of the Real Numbers». Роза Петер и Рафаэль Робинсон позже представили двухаргументную версию функции Аккермана, которую теперь многие авторы предпочитают оригинальной[2].
Определение
Функция Аккермана определяется рекурсивно для неотрицательных целых чисел и следующим образом:
Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение , или значение сохраняется, но уменьшается значение . Это означает, что каждый раз пара уменьшается с точки зрения лексикографического порядка, значит, значение в итоге достигнет нуля: для одного значения существует конечное число возможных значений (так как первый вызов с данным был произведён с каким-то определённым значением , а в дальнейшем, если значение сохраняется, значение может только уменьшаться), а количество возможных значений , в свою очередь, тоже конечно. Однако, при уменьшении значение, на которое увеличивается , неограниченно и обычно очень велико.
Обратная функция
Так как функция растёт очень быстро, обратная функция , обозначаемая , растёт очень медленно. Эта функция встречается при исследовании сложности некоторых алгоритмов, например, системы непересекающихся множеств или алгоритма Чазелла для построения минимального остовного дерева[3]. При анализе асимптотики можно считать, что для всех практически встречающихся чисел значение этой функции меньше пяти, так как не меньше .
Использование в тестах производительности
Функция Аккермана в силу своего определения имеет очень глубокий уровень рекурсии, что можно использовать для проверки способности компилятора оптимизировать рекурсию. Первым функцию Аккермана для этого использовал Ингви Сандблад[4].
Брайан Вичман (соавтор теста производительности Whetstone) учёл эту статью при написании серии статей о тестировании оптимизации вызовов[5][6][7].
Например, компилятор, который анализируя вычисление способен сохранять промежуточные значения, например, и , может ускорить вычисление в сотни и тысячи раз. Также вычисление напрямую вместо рекурсивного раскрытия в прилично ускорит вычисление. Вычисление занимает линейное время . Вычисление требует квадратичное время, так как оно раскрывается в O() вложенных вызовов для различных . Время вычисления пропорционально .
Значение невозможно посчитать с помощью простого рекурсивного применения за разумное время. Вместо этого для оптимизации рекурсивных вызовов используются сокращённые формулы, например, .
Один из практичных способов вычисления значений функции Аккермана — мемоизация промежуточных результатов. Компилятор может применить эту технику к функции автоматически, используя memo functions[8][9] Дональда Мичи.
Примечания
- Cristian Calude, Solomon Marcus and Ionel Tevy. The first example of a recursive function which is not primitive recursive (англ.) // Historia Math. : journal. — 1979. — November (vol. 6, no. 4). — P. 380—384. — doi:10.1016/0315-0860(79)90024-7.
- Raphael M. Robinson. Recursion and double recursion (неопр.) // Bulletin of the American mathematical society. — 1948. — Т. 54, № 10. — С. 987—993. — doi:10.1090/S0002-9904-1948-09121-2.
- Дискретная математика: алгоритмы. Минимальные остовные деревья (недоступная ссылка). Дата обращения: 13 августа 2011. Архивировано 2 июня 2010 года.
- Y. Sundblad. The Ackermann function. A theoretical, computational and formula manipulative study (англ.) // BIT : journal. — 1971. — Vol. 11. — P. 107—119. — doi:10.1007/BF01935330. (недоступная ссылка)
- Ackermann's function: A study in the efficiency of calling procedures (1975). Дата обращения: 13 августа 2011. Архивировано 23 февраля 2012 года.
- How to call procedures, or second thoughts on Ackermann's function (1977). Дата обращения: 13 августа 2011. Архивировано 23 февраля 2012 года.
- Latest results from the procedure calling test. Ackermann's function (1982). Дата обращения: 13 августа 2011. Архивировано 23 февраля 2012 года.
- Michie, Donald Memo functions and machine learning, Nature, No. 218, pp. 19—22, 1968.
- Example: explicit memo function version of Ackermann’s function implemented in PL/SQL.
Ссылки
- Weisstein, Eric W. Ackermann Function (англ.) на сайте Wolfram MathWorld.