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

Функция Аккермана — простой пример вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается $A(m,\;n)$. Эта функция растёт очень быстро, например, число $A(4,\;4)$ настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной.

История

В конце 20-х годов XX века математики-ученики Давида Гильберта Габриэль Судан и Вильгельм Аккерман изучали основы вычислений. Судан и Аккерман известны^[1] за открытие всюду определенной вычислимой (иногда называемой просто "рекурсивной"), не являющейся примитивно рекурсивной. Судан открыл менее известную функцию Судана, после чего, независимо от него, в 1928 Аккерман опубликовал его функцию $\varphi\,\!$. Функция трех аргументов Аккермана $\varphi(m, n, p)\,\!$ определялась так, что для p = 0, 1, 2, она проводила операцию сложения, умножения или возведения в степень:

$\varphi(m, n, 0) = m+n,\,\!$

$\varphi(m, n, 1) = m\cdot n,\,\!$

$\varphi(m, n, 2) = m^n,\,\!$

а для p > 2 она доопределяется с помощью стрелочной нотации Кнута:

$\varphi(m, n, p) = m\uparrow^{p - 1}(n + 1)\,\!$.

(Помимо её исторической роли как первой всюду определенной не примитивно рекурсивной вычислимой функции, оригинальная функция Аккермана расширяла основные арифметические операции за возведение в степень, хотя и не так хорошо, как специально предназначенные для этого функции вроде последовательности гипероператоров Гудстейна.)

В статье On the Infinite Гильберт высказал гипотезу, что функция Аккермана не является примитивно рекурсивной, и Аккерман (личный секретарь и бывший студент Гильберта) доказал эту гипотезу в статье On Hilbert’s Construction of the Real Numbers. Роза Петер и Рафаэль Робинсон позже представили двухаргументную версию функции Аккермана, которую теперь многие авторы предпочитают оригинальной.^[2]

Определение

Функция Аккермана определяется рекурсивно для неотрицательных целых чисел $m$ и $n$ следующим образом:

$A(m,\;n)=\begin{cases}n+1,&m=0;\\A(m-1,\;1),&m>0,\;n=0;\\A(m-1,\;A(m,\;n-1)),&m>0,\;n>0.\end{cases}$

Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение $m$, или значение $m$ сохраняется, но уменьшается значение $n$. Это означает, что каждый раз пара $(m,\;n)$ уменьшается с точки зрения лексикографического порядка, значит, значение $m$ в итоге достигнет нуля: для одного значения $m$ существует конечное число возможных значений $n$ (так как первый вызов с данным $m$ был произведён с каким-то определённым значением $n$, а в дальнейшем, если значение $m$ сохраняется, значение $n$ может только уменьшаться), а количество возможных значений $m$, в свою очередь, тоже конечно. Однако, при уменьшении $m$ значение, на которое увеличивается $n$, неограничено и обычно очень велико.

Таблица значений

Подробнее о hyper см Гипероператор

$n$\$m$	$0$	$1$	$2$	$3$	$4$	$5$	$m$
$0$	$1$	$2$	$3$	$5$	$13$	$65533$	$\mathrm{hyper}(2,\;m,\;3)-3$
$1$	$2$	$3$	$5$	$13$	$65533$	$\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}-3$	$\mathrm{hyper}(2,\;m,\;4)-3$
$2$	$3$	$4$	$7$	$29$	$2^{65536}-3$	$\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}-3$	$\mathrm{hyper}(2,\;m,\;5)-3$
$3$	$4$	$5$	$9$	$61$	$2^{2^{65536}}-3$	$A(4,\;\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}-3)$	$\mathrm{hyper}(2,\;m,\;6)-3$
$4$	$5$	$6$	$11$	$125$	$2^{2^{2^{65536}}}-3$	$A(4,\;A(5,\;3))$	$\mathrm{hyper}(2,\;m,\;7)-3$
$5$	$6$	$7$	$13$	$253$	$2^{2^{2^{2^{65536}}}}-3$	$A(4,\;A(5,\;4))$	$\mathrm{hyper}(2,\;m,\;8)-3$
$n$	$n+1$	$n+2$	$2n+3$	$2^{n+3}-3$	$\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{n+3}-3$	$\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underset{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}{\vdots}}-3$ (всего $n$ блоков $2^{2^{\cdot^{\cdot^{\cdot^2}}}}$)	$\mathrm{hyper}(2,\;m,\;n+3)-3$

Обратная функция

Так как функция $f(n)=A(n,\;n)$ растёт очень быстро, обратная функция $f^{-1}(n)=\min\{k\geqslant 1:A(k,\;k)\geqslant n\}$, обозначаемая α, растёт очень медленно. Эта функция встречается при исследовании сложности некоторых алгоритмов, например, системы непересекающихся множеств или алгоритма Чазелла для построения минимального остовного дерева^[3]. При анализе асимптотики можно считать, что для всех практически встречающихся чисел значение этой функции меньше пяти, так как A(4, 4) одного порядка с $2^{2^{10^{19729}}}$.

Использование в бенчмарках

Функция Аккермана в силу своего определения имеет очень глубокий уровень рекурсии, что можно использовать для проверки способности компилятора оптимизировать рекурсию. Первым функцию Аккермана для этого использовал Ингви Сандблад ^[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) требует времени пропорционально 4ⁿ⁺¹.

A(4, 2) невозможно посчитать с помощью простого рекурсивного применения за разумное время. Вместо этого для оптимизации рекурсивных вызовов используются сокращенные формулы вроде A(3, n) = 8×2ⁿ−3. (источник?)

Один из практичных способов вычисления значений функции Аккермана - Мемоизация промежуточных результатов. Компилятор может применить эту технику к функции автоматически, используя memo functions ^[8][9] Дональда Мичи.

Примечания

1. ↑ 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.
2. ↑ 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.
3. ↑ Дискретная математика: алгоритмы. Минимальные остовные деревья
4. ↑ Y. Sundblad (1971). «The Ackermann function, A theoretical, computational and formula manipulative study». BIT 11: 107–119. DOI:10.1007/BF01935330.
5. ↑ Ackermann's Function: A Study In The Efficiency Of Calling Procedures (1975). Архивировано из первоисточника 24 февраля 2012.
6. ↑ How to Call Procedures, or Second Thoughts on Ackermann's Function (1977). Архивировано из первоисточника 24 февраля 2012.
7. ↑ Latest results from the procedure calling test, Ackermann's function (1982). Архивировано из первоисточника 24 февраля 2012.
8. ↑ Michie, Donald, "Memo Functions and Machine Learning," Nature, No. 218, pp. 19–22, 1968.
9. ↑ Example: Explicit memo function version of Ackermann's function implemented in PL/SQL

Ссылки

• Weisstein, Eric W. Ackermann Function (англ.) на сайте Wolfram MathWorld.