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

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

История

В конце 20-х годов XX века математики-ученики Давида Гильберта Габриэль Судан и Вильгельм Аккерман изучали основы вычислений. Судан и Аккерман известны за открытие всюду определенной вычислимой (иногда называемой просто "рекурсивной"), не являющейся примитивно рекурсивной. Судан открыл менее известную функцию Судана, после чего, независимо от него, в 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. Роза Петер и Рафаэль Робинсон позже представили двухаргументную версию функции Аккермана, которую теперь многие авторы предпочитают оригинальной.

Определение

Функция Аккермана определяется рекурсивно для неотрицательных целых чисел $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\}$, обозначаемая α, растёт очень медленно. Эта функция встречается при исследовании сложности некоторых алгоритмов, например, системы непересекающихся множеств или алгоритма Чазелла для построения минимального остовного дерева. При анализе асимптотики можно считать, что для всех практически встречающихся чисел значение этой функции меньше пяти, так как A(4, 4) одного порядка с $2^{2^{10^{19729}}}$.

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

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

Брайан Вичман (соавтор бенчмарка Whetstone) учел эту статью при написании серии статей о тестировании оптимизации вызовов .

Например, компилятор, который анализируя вычисление 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 Дональда Мичи.

Ссылки

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