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

Функция Аккермана — простой пример всюду определённой вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается $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$ она доопределяется с помощью стрелочной нотации Кнута, опубликованной в 1976 году:

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

Использование в тестах производительности

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

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

Например, компилятор, который анализируя вычисление $A(3,\,30)$ способен сохранять промежуточные значения, например, $A(3,\,n)$ и $A(2,\,n)$, может ускорить вычисление $A(3,\,30)$ в сотни и тысячи раз. Также вычисление $A(2,\,n)$ напрямую вместо рекурсивного раскрытия в $A(1,\,A(1,\,A(1,\,\ldots A(1,\,0)\ldots )))$ прилично ускорит вычисление. Вычисление $A(1,\,n)$ занимает линейное время $n$. Вычисление $A(2,\,n)$ требует квадратичное время, так как оно раскрывается в O($n$) вложенных вызовов $A(1,\,i)$ для различных $i$. Время вычисления $A(3,\,n)$ пропорционально $4^{n+1}$.

Значение $A(4,\,n)$ невозможно посчитать с помощью простого рекурсивного применения за разумное время. Вместо этого для оптимизации рекурсивных вызовов используются сокращённые формулы, например, $A(3,\,n)=8\cdot 2^{n}-3$.

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

Ссылки

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