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

Рисунок аналитического продолжения функции Аккермана f=A(4,z) в комплексной плоскости z=. Показаны уровни, соответствующие целочисленным значениям действительной части f и мнимой части.

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

История

В 1926 году Давид Гильберт предположил, что каждая вычислимая функция примитивно-рекурсивна. Проще говоря, каждую вычислимую функцию можно построить из базового набора при помощи нескольких очень простых правил, причём продолжительность вычисления может быть оценена заранее. Функции, для которых это неверно, очень редки.

В том же 1926 году Аккерман построил функцию, опровергающую эту гипотезу, и опубликовал свой контрпример в 1928 году. Впоследствии эта функция получила название гипероператора. Он может быть оценён компьютером за конечное время, но не является примитивно-рекурсивным.

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

Построение

Для построения функции используется последовательность $a+b,a\cdot b,a^{b},\ldots$, в которой каждый следующий оператор определяется так, что предыдущий оператор применяется $b-1$ раз к числу $a$. Например, результат $a\cdot b$ применения второго оператора к числам $a$ и $b$ равен $a+a+\ldots +a$, где число $a$ входит в выражение $b$ раз. Аналогично значение $a^{b}$третьего оператора равно $\underbrace {a\cdot \ldots \cdot a} _{b{\text{ раз }}}$. Аккерманн предложил рассмотреть функцию $\varphi (a,b,n)$, возвращающую результат применения $n$-го оператора последовательности к числам $a$ и $b$.

Например, применив все операторы последовательности к числам $a=2$ и $b=4$, получатся следующие результаты: 6, 8, 16, 65536, $2^{2^{.^{.^{.^{2}}}}}$ (с 65536 двойками),… Пятый член последовательности настолько велик, что количество цифр в его десятичной записи намного больше числа атомов во Вселенной.

Таким образом, построенная Аккерманом функция $\varphi$ удовлетворяет следующим уравнениям:

$\varphi (a,b,0)=a+b$,

$\varphi (a,b,1)=a\cdot b$,

$\varphi (a,b,2)=a^{b}$,

$\ldots$.

Начиная с четвёртой строки функцию становится затруднительно описать с помощью обычных операторов.

Определение и варианты

Функция Аккермана обычно определяется рекурсивно, то есть явно задаётся для некоторых начальных значений, после чего описывается алгоритм получения дальнейших значений функции из уже рассчитанных.

Изначально Аккерман определил функцию довольно громоздко, но вскоре дал следующее эквивалентное определение:

$\varphi (a,b,0)=a+b$,

$\varphi (a,0,n+1)=\alpha (a,n)$,

$\varphi (a,b+1,n+1)=\varphi (a,\varphi (a,b,n+1),n)$.

Здесь $\alpha \left(a,n\right)$ — ещё одна функция, задающая начальные значения $a\cdot 0,a^{0},\ldots$:

$\alpha (a,n)={\begin{cases}0&{\text{при }}n=0\\1&{\text{при }}n=1\\a&{\text{при }}n>1\end{cases}}$

Например, при вычислении $\varphi (4,3,0)$ можно применить первую строку определения и получить $\varphi (4,3,0)=4+3=7$. При вычислении $\varphi (4,0,2)$ применяется вторая строка: $\varphi (4,0,2)=\alpha (4,1)=1$;

Если ни второй, ни третий аргумент не равен 0, используется третья строка определения, например, $\varphi (4,1,2)=\varphi (4,\varphi (4,0,2),1)$ . При подстановке $\varphi (4,0,2)=1$ из вычисления $\varphi (4,0,2)$ получается ${\displaystyle \varphi (4,1,2)=\varphi (4,\varphi (4,0,2),1)}=\varphi (4,1,1)$. Продолжая рекурсивно вычислять значения функции $\varphi ,$ получается $\varphi (4,1,2)$:

${\begin{aligned}\varphi (4,1,2)&=\varphi (4,\varphi (4,0,2),1)\\&=\varphi (4,1,1)\\&=\varphi (4,\varphi (4,0,1),0)\\&=\varphi (4,0,0)\\&=4\end{aligned}}$

При оценке скорости роста функции Аккермана обычно изучают функцию$f\left(n\right):=\varphi (n,n,n)$.

Определение Петер

В 1935 году Рожа Петер предложила более простое построение, в котором функция имеет только два параметра, а вспомогательная функция $\alpha$ не используется:

${\begin{array}{lcl}A(0,m)&=&m+1\\A(n+1,0)&=&A(n,1)\\A(n+1,m+1)&=&A(n,A(n+1,m))\end{array}}$

Говоря о скорости роста функции Аккермана, тоже имеют в виду скорость роста функции $f(n):=A(n,n)$.

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

Применение в теоретической информатике

Аккерман привёл эту функцию в качестве примера функции, которая не является примитивно-рекурсивной, но является вычислимой.

Некоторое время предполагалось, что все вычислимые функции примитивно-рекурсивны, то есть вычислимость любой функции можно доказать, построив алгоритм, или опровергнуть, убедившись, что она не является примитивно-рекурсивной. Однако функция Аккермана, будучи вычислимой, но не примитивно-рекурсивной (доказательство этого приведено ниже), опровергла это предположение.

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

Доказательство

Чтобы доказать, что функция Аккермана вычислима, но не является примитивно-рекурсивной, мы докажем, что каждая примитивно рекурсивная функция (далее- ПРФ) растёт медленнее функции Аккермана.

Набросок доказательства утверждения, что функция Аккермана не является примитивно-рекурсивной:

• Сначала определим для каждой ПРФ $g$ функцию

  $f_{g}(n):=\max \left\{g(n_{1},\ldots ,n_{k}):n_{i}\leq n\right\}$

  Эта функция возвращает наибольшее значение, которое можно получить при помощи функции $g$ , не используя аргументов выше $n$.

• Затем с помощью индукции по структуре ПРФ показывается, что для любой ПРФ $g$ существует натуральное число $k$, такое, что при всех $n\geq k$ $f_{g}(n)<A(k,n)$.
• Если бы функция Аккермана $A(k,n)$ была ПРФ, то функция $\Gamma (n):=A(n,n)$ сама оказалась бы примитивно рекурсивной, и для некоторого $k_{\Gamma }$ мы бы получили, что при всех $n\geq k_{\Gamma }$ $A(n,n)=\Gamma (n)\leq A(k_{\Gamma },n).$ Однако функция Аккермана монотонна по обоим аргументам. Противоречие.

Приложения

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

Ориентир для рекурсивных вызовов

При тестировании новых языков программирования, компиляторов и компьютеров важное место занимает проверка их производительности.

В качестве эталона для проверки рекурсивных вызовов процедур часто используется функция Аккермана, так как непосредственное вычисление этой функции состоит почти только из них. В определении Петер непосредственно заданы только значения $A(0,m)$. Все остальные значения вычисляются с помощью многократных глубоко вложенных вызовов, что легко может привести к переполнению стека, указывающему на то, что системе не хватает памяти. Таким образом, функция Аккермана является простым и безопасным методом провоцирования переполнения стека, например, для проверки того, обрабатывается ли этот случай ошибки и, если да, то как это делается. Преимущество функции Аккермана в том, что она невосприимчива к оптимизации компилятора, а статический анализ исходного кода практически не способен обнаружить (возможное) переполнение стека.

Эта идея восходит к Ингве Сундбладу, который в 1971 году начал использовать функцию $f(n):=A(3,n)$ для сравнения различных языков программирования. При вычислении $A(3,n)$ происходит около $4^{n+1}$ вложенных вызовов.

Компания Sundblad проверила, среди прочего, максимальное значение $n$, при котором вычисление $A(3,n)$ не вызывает переполнения. В то время максимально возможное значение $n$ было равно 1. Сейчас в языке Java 1.4.2 со стандартными настройками памяти максимальное допустимое значение $n=13$.

В ходе расчета множество одинаковых вызовов обсчитываются несколько раз. Умный компилятор может воспользоваться этим и кэшировать результаты, чтобы не вычислять одно и то же значение много раз. Уже в 1971 году таким способом было достигнуто число $n=20$. Другим способом оптимизации является вычисление $A(1,n)$ напрямую без рекурсивного раскрытия в $A(1,A(1,A(1,\dots ,A(1,0)\dots )))$. Прямой расчёт $A(1,n)$ требует линейного времени по $n$. Расчёт $A(2,n)$ требует квадратичного времени, потому что при этом происходят ${\mathcal {O}}(n)$ вложенных вызовов $A(1,i)$ для разных $i$. Расчёт $A(3,n)$ занимает ${\mathcal {O}}(4^{n+1})$ времени.

Оценки времени выполнения, содержащие обратную функцию Аккермана

Поскольку функция $f(n):=A(n,n)$ растёт очень быстро, её обратная функция $f^{-1}$ растет очень медленно. Поскольку для всех практически встречающихся значений $n$ значение $f^{-1}(n)$ меньше 5, при практическом анализе алгоритмов его можно считать постоянным.

Реализация

В псевдокоде функция Аккермана реализуется по определению:

функция ack(n, m)
   если n = 0
     вернуть m + 1
   иначе, если m = 0
     вернуть ack (n - 1, 1)
   еще
     вернуть ack(n - 1, ack (n, m - 1))

Следующая частично итерационная реализация несколько более эффективна:

функция ack(n, m)
   пока n ≠ 0
     если m = 0
       m:= 1
     иначе
       m:= ack(n, m - 1)
     n:= n - 1
   вернуть m + 1

Ещё более эффективные реализации используют динамическое программирование.

Grossman & Zeitman опубликовали алгоритм вычисления функции Аккермана без использования кэша, занимающий время ${\mathcal {O}}(nA(n,m))$ и использующий ${\mathcal {O}}(n)$ памяти.

В функциональном языке программирования Haskell, реализация напрямую отражает определение:

ack 0 n = n+1
ack n 0 = ack (n-1) 1
ack n m = ack (n-1) (ack n (m-1))

На Прологе реализация выглядит так:

ackermann(0,X,Y) :- X >= 0,!, Y = X + 1.
 ackermann(X,0,Z):- X > 0,!, X1 = X - 1, ackermann(X1,1,Z).
 ackermann(X,Y,Z):- X > 0, Y > 0, X1 = X-1, Y1 = Y-1, ackermann(X,Y1,W), ackermann(X1,W,Z).

Чисто итеративная реализация возможна даже в лямбда-исчислении:

ack ≡ λn. n (λf.λm.mf (f 1 )) succ

Таблица значений A(n, m)

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

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

Хотя в этой таблице возникают невообразимо большие числа, впоследствии были описаны рекуррентные построения, порождающие ещё бо́льшие числа, такие как число Грэма.

Память, требуемая для хранения $A(n,m)$ как целого числа без знака.

m\n	0	1	2	3	4	5
0	1 бит	2 бита	2 бита	3 бита	4 бита	16 бит
1	2 бита	2 бита	3 бита	4 бита	16 бит
2	2 бита	3 бита	3 бита	5 бит	8 КБ
3	2 бита	3 бита	4 бита	6 бит	более $10^{19703}$ йоттабайт
4	3 бита	3 бита	4 бита	7 бит
5	3 бита	3 бита	4 бита	8 бит
6	3 бита	3 бита	4 бита	9 бит
7	3 бита	3 бита	5 бит	10 бит
8-й	4 бита	4 бита	5 бит	11 бит
9	4 бита	4 бита	5 бит	12 бит
10	4 бита	4 бита	5 бит	13 бит
100	7 бит	7 бит	8 бит	103 бита
1000	10 бит	10 бит	11 бит	125 375 байт
10’000	14 бит	14 бит	15 бит	1221 КБ
100’000	17 бит	17 бит	18 бит	12 207 КБ
1 000 000	20 бит	20 бит	21 бит	122 071 КБ
10 000 000	24 бит	24 бит	25 бит	1192 МБ
100 000 000	27 бит	27 бит	28 бит	11 921 МБ
2 32 −1	33 бита	33 бита	34 бит	119,21 МБ
2 64 −1	65 бит	65 бит	66 бит	1164 ГБ

Подробное описание

Используя таблицу значений, можно вывести схему вычисления значений функции, которую легче понять, чем формальное рекурсивное определение. Легко заметить, что значения в первой строке — это просто список всех натуральных чисел: $A(0,m)=m+1$. Все последующие строки просто содержат инструкции для поиска значения в этой строке. При $n=1$ легко показать, что $A(1,m)=m+2:$

${\begin{aligned}A(1,m)&\rightarrow A(0,A(1,m-1))\\&\rightarrow A(0,A(0,A(1,m-2)))\\&\rightarrow A(0,A(0,m))\\&\rightarrow A(0,m+1)\\&\rightarrow m+2.\end{aligned}}$

Теперь рассмотрим более сложный случай вычисления функции $A(4,3)$, значение которой настолько велико, что записать его в десятичном виде невозможно.

${\begin{aligned}A(4,3)&\rightarrow A(3,A(4,2))\\&\rightarrow A(3,A(3,A(4,1)))\\&\rightarrow A(3,A(3,A(3,A(4,0))))\\&\rightarrow A(3,A(3,A(3,A(3,1))))\\&\rightarrow A(3,A(3,A(3,A(2,A(3,0)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(2,1)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(2,0))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(1,1))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,A(0,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(1,3)))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(1,2))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,A(0,2)))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,A(0,3))))))\\&\rightarrow A(3,A(3,A(3,A(2,A(0,4)))))\\&\rightarrow A(3,A(3,A(3,A(2,5))))\\&\qquad \vdots \\&\rightarrow A(3,A(3,A(3,13)))\\&\qquad \vdots \\&\rightarrow A(3,A(3,65533))\\&\qquad \vdots \\&\rightarrow A(3,2^{65536}-3)\\&\qquad \vdots \\&\rightarrow 2^{2^{65536}}-3.\\\end{aligned}}$

Вычислить напрямую подобные значения совершенно невозможно. Даже очень простые на вид выражения Аккермана практически не поддаются вычислению. Каждая строка в предыдущем примере — это отдельное применение одной из трёх частей определения функции Аккермана.

${\begin{aligned}A(4,3)&\rightarrow A(3,A(3,A(3,13)))\\&\qquad \vdots \\&\rightarrow A(3,A(3,65533))\\&\qquad \vdots \\&\rightarrow A(3,2^{65536}-3)\\&\qquad \vdots \\&\rightarrow 2^{2^{65536}}-3.\\\end{aligned}}$

Ещё одним аспектом функции Аккермана является то, что единственное вычисление, которое действительно появляется помимо рекурсивных вызовов, — это вычисление $A(0,m)=m+1.$

Литература

• Dexter C. Kozen: The Design and Analysis of Algorithms. Springer, Berlin 1992, ISBN 3-540-97687-6.
• Uwe Schöning: Theoretische Informatik — kurzgefasst. Spektrum Akademischer Verlag, Heidelberg 2001, ISBN 3-8274-1099-1.
• Yngve Sundblad: The Ackermann Function. A Theoretical, Computational, and Formula Manipulative Study. In: BIT — numerical mathematics. Springer, Dordrecht 11.1971, S. 107—119, ISSN 0006-3835.

Ссылки

• Пояснительное видео для функции Аккермана (на английском языке)

Ссылки

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