- Функция Аккермана
-
Функция Аккермана — простой пример вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается . Эта функция растёт очень быстро, например, число настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной.
Содержание
История
В конце 20-х годов XX века математики-ученики Давида Гильберта Габриэль Судан и Вильгельм Аккерман изучали основы вычислений. Судан и Аккерман известны[1] за открытие всюду определенной вычислимой (иногда называемой просто "рекурсивной"), не являющейся примитивно рекурсивной. Судан открыл менее известную функцию Судана, после чего, независимо от него, в 1928 Аккерман опубликовал его функцию . Функция трех аргументов Аккермана определялась так, что для p = 0, 1, 2, она проводила операцию сложения, умножения или возведения в степень:
а для p > 2 она доопределяется с помощью стрелочной нотации Кнута:
- .
(Помимо её исторической роли как первой всюду определенной не примитивно рекурсивной вычислимой функции, оригинальная функция Аккермана расширяла основные арифметические операции за возведение в степень, хотя и не так хорошо, как специально предназначенные для этого функции вроде последовательности гипероператоров Гудстейна.)
В статье On the Infinite Гильберт высказал гипотезу, что функция Аккермана не является примитивно рекурсивной, и Аккерман (личный секретарь и бывший студент Гильберта) доказал эту гипотезу в статье On Hilbert’s Construction of the Real Numbers. Роза Петер и Рафаэль Робинсон позже представили двухаргументную версию функции Аккермана, которую теперь многие авторы предпочитают оригинальной.[2]
Определение
Функция Аккермана определяется рекурсивно для неотрицательных целых чисел и следующим образом:
Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение , или значение сохраняется, но уменьшается значение . Это означает, что каждый раз пара уменьшается с точки зрения лексикографического порядка, значит, значение в итоге достигнет нуля: для одного значения существует конечное число возможных значений (так как первый вызов с данным был произведён с каким-то определённым значением , а в дальнейшем, если значение сохраняется, значение может только уменьшаться), а количество возможных значений , в свою очередь, тоже конечно. Однако, при уменьшении значение, на которое увеличивается , неограничено и обычно очень велико.
Таблица значений
- Подробнее о hyper см Гипероператор
\ (всего блоков ) Обратная функция
Так как функция растёт очень быстро, обратная функция , обозначаемая α, растёт очень медленно. Эта функция встречается при исследовании сложности некоторых алгоритмов, например, системы непересекающихся множеств или алгоритма Чазелла для построения минимального остовного дерева[3]. При анализе асимптотики можно считать, что для всех практически встречающихся чисел значение этой функции меньше пяти, так как A(4, 4) одного порядка с .
Использование в бенчмарках
Функция Аккермана в силу своего определения имеет очень глубокий уровень рекурсии, что можно использовать для проверки способности компилятора оптимизировать рекурсию. Первым функцию Аккермана для этого использовал Ингви Сандблад [4].
Брайан Вичман (соавтор бенчмарка Whetstone) учел эту статью при написании серии статей о тестировании оптимизации вызовов [5][6][7].
Например, компилятор, который анализируя вычисление A(3, 30) способен сохранять промежуточные значения вроде A(3, n) и A(2, n), может ускорить вычисление A(3, 30) в сотни и тысячи раз. Также вычисление A(2, n) напрямую вместо рекурсивного раскрытия в A(1, A(1, A(1,...A(1, 0)...))) прилично ускорит вычисление. Вычисление A(1, n) занимает линейное время n. Вычисленние A(2, n) требует квадратичное время, т.к. оно раскрывается в O(n) вложенных вызовов A(1, i) для различных i. Вычисление A(3, n) требует времени пропорционально 4n+1.
A(4, 2) невозможно посчитать с помощью простого рекурсивного применения за разумное время. Вместо этого для оптимизации рекурсивных вызовов используются сокращенные формулы вроде A(3, n) = 8×2n−3. (источник?)
Один из практичных способов вычисления значений функции Аккермана - Мемоизация промежуточных результатов. Компилятор может применить эту технику к функции автоматически, используя memo functions [8][9] Дональда Мичи.
Примечания
- ↑ Cristian Calude, Solomon Marcus and Ionel Tevy (November 1979). «The first example of a recursive function which is not primitive recursive». Historia Math. 6 (4): 380–84. DOI:10.1016/0315-0860(79)90024-7.
- ↑ Raphael M. Robinson (1948). «Recursion and Double Recursion». Bulletin of the American Mathematical Society 54 (10): 987-993. DOI:10.1090/S0002-9904-1948-09121-2.
- ↑ Дискретная математика: алгоритмы. Минимальные остовные деревья
- ↑ Y. Sundblad (1971). «The Ackermann function, A theoretical, computational and formula manipulative study». BIT 11: 107–119. DOI:10.1007/BF01935330.
- ↑ Ackermann's Function: A Study In The Efficiency Of Calling Procedures (1975). Архивировано из первоисточника 24 февраля 2012.
- ↑ How to Call Procedures, or Second Thoughts on Ackermann's Function (1977). Архивировано из первоисточника 24 февраля 2012.
- ↑ Latest results from the procedure calling test, Ackermann's function (1982). Архивировано из первоисточника 24 февраля 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.
Категории:- Арифметические функции
- Большие числа
- Теория сложности вычислений
Wikimedia Foundation. 2010.