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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

\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\}, обозначаемая \alpha, растёт очень медленно. Эта функция встречается при исследовании сложности некоторых алгоритмов, например, системы непересекающихся множеств или алгоритма Чазелла для построения минимального остовного дерева[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) пропорционально 4n+1.

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

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

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

Ссылки[править | править вики-текст]