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

Функция Аккермана — всюду определённая вычислимая функция, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается $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+\dotsb +a$ , где число $a$ входит в выражение $b$ раз. Аналогично значение $a^{b}$ третьего оператора равно $\underbrace {a\cdot ...\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$ из предыдущего примера, получим ${\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$ не используется: ^[1]

{\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$ , неограниченно и обычно очень велико.

Применение в теоретической информатике[править | править код]

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

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

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

Доказательство[править | править код]

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

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

Сначала определим для каждой ПРФ $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)$ памяти^[3].

В функциональном языке программирования 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(m,n)$ [править | править код]

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


$n$ $\backslash 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$

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

Память, требуемая для хранения $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 ³² −1	33 бита	33 бита	34 бит	119,21 МБ
2 ⁶⁴ −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.

Внешние ссылки[править | править код]

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

Примечания[править | править код]

↑ Péter Rózsa: Konstruktion nichtrekursiver Funktionen. In: Mathematische Annalen, 111, 1935, S. 42–60
↑ Für Details zum Beweis sehe man z. B. im Buch von Uwe Schöning nach (siehe Literatur).
↑ Grossman, Jerrold W. (1988-05). “An inherently iterative computation of ackermann's function”. Theoretical Computer Science. 57 (2—3): 327—330. DOI:10.1016/0304-3975(88)90046-1. Проверьте дату в |date= (справка на английском)

Ссылки[править | править код]

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

[peter-1] Péter Rózsa: Konstruktion nichtrekursiver Funktionen. In: Mathematische Annalen, 111, 1935, S. 42–60

[2] Für Details zum Beweis sehe man z. B. im Buch von Uwe Schöning nach (siehe Literatur).

[3] Grossman, Jerrold W. (1988-05). “An inherently iterative computation of ackermann's function”. Theoretical Computer Science. 57 (2—3): 327—330. DOI:10.1016/0304-3975(88)90046-1. Проверьте дату в |date= (справка на английском)

[1]

[2]

[3]

Большие числа
Числа	Гугол Число Шеннона Гуголплекс Число Скьюза Число Мозера Число Грэма TREE(3) Число Райо
Функции	Функция Аккермана Функция Веблена Пси-функции Бухгольца Тетрация Пентация Гипероператор Быстрорастущая иерархия Медленнорастущая иерархия Иерархия Харди
Нотации	Обозначения Штейнгауза — Мозера Стрелочные обозначения Кнута Стрелочные обозначения Конвея Массивная нотация Бауэрса

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

Содержание

История[править | править код]

Идея построения[править | править код]

Определение и варианты[править | править код]

Определение Аккермана[править | править код]

Определение Петер[править | править код]

Применение в теоретической информатике[править | править код]

Доказательство[править | править код]

Приложения[править | править код]

Ориентир для рекурсивных вызовов[править | править код]

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

Реализация[править | править код]

Таблица значений $A(m,n)$ [править | править код]

Подробное описание[править | править код]

Литература[править | править код]

Внешние ссылки[править | править код]

Примечания[править | править код]

Ссылки[править | править код]

Навигация

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

История[править | править код]

Идея построения[править | править код]

Определение и варианты[править | править код]

Определение Аккермана[править | править код]

Определение Петер[править | править код]

Применение в теоретической информатике[править | править код]

Доказательство[править | править код]

Приложения[править | править код]

Ориентир для рекурсивных вызовов[править | править код]

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

Реализация[править | править код]

Таблица значений A ( m , n ) {\displaystyle A(m,n)} [править | править код]

Подробное описание[править | править код]

Литература[править | править код]

Внешние ссылки[править | править код]

Примечания[править | править код]

Ссылки[править | править код]

Навигация

Таблица значений $A(m,n)$ [править | править код]