Processing math: 87%

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

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

История


 В конце 20-х годов XX века математики-ученики Давида Гильберта —Габриэль Судан и Вильгельм Аккерман изучали основы вычислений. Судан иАккерман известны за открытие всюду определённой вычислимой функции(иногда называемой просто «рекурсивной»), не являющейся примитивнорекурсивной. Судан открыл менее известную функцию Судана, после чего,независимо от него, в 1928 Аккерман опубликовал свою функцию φ.Функция трёх аргументов Аккермана φ(m,n,p) определялась так,что для p = 0, 1, 2, она проводила операцию сложения, умноженияили возведения в степень:

φ(m,n,0)=m+n,
φ(m,n,1)=mn,
φ(m,n,2)=mn,
 а для p \textgreater 2 она доопределяется с помощью стрелочнойнотации Кнута, опубликованной в 1976 году:

φ(m,n,p)=mp1(n+1).
 (Помимо её исторической роли как первой всюду определённой не примитивнорекурсивной вычислимой функции, оригинальная функция Аккермана расширялаосновные арифметические операции за возведение в степень, хотя и не такхорошо, как специально предназначенные для этого функции вродепоследовательности гипероператоров Гудстейна.)
 В статье «On the infinite» Гильберт высказал гипотезу о том, что функцияАккермана не является примитивно рекурсивной, а Аккерман (личныйсекретарь и бывший студент Гильберта) доказал эту гипотезу в статье «Onhilbert's construction of the real numbers». Роза Петер и РафаэльРобинсон позже представили двухаргументную версию функции Аккермана,которую теперь многие авторы предпочитают оригинальной.

Определение


 Функция Аккермана определяется рекурсивно для неотрицательных целыхчисел m и n следующим образом:

A(m,n)={n+1,m=0;A(m1,1),m>0,n=0;A(m1,A(m,n1)),m>0,n>0.
 Может показаться неочевидным, что рекурсия всегда заканчивается. Этоследует из того, что при рекурсивном вызове или уменьшается значениеm, или значение m сохраняется, но уменьшается значение n. Этоозначает, что каждый раз пара (m,n) уменьшается с точки зрениялексикографического порядка, значит, значение m в итоге достигнетнуля: для одного значения m существует конечное число возможныхзначений n (так как первый вызов с данным m был произведён скаким-то определённым значением n, а в дальнейшем, если значение mсохраняется, значение n может только уменьшаться), а количествовозможных значений m, в свою очередь, тоже конечно. Однако, приуменьшении m значение, на которое увеличивается n, неограниченно иобычно очень велико.

Таблицазначений



Подробнее о hyper см. гипероператор.
n|m$012345m
012351365533\mathrmhyper(2,m,3)3
12351365533\underbrace{2^2^\cdot^\cdot^\cdot^2_65536-3\mathrmhyper(2,m,4)3
2347292655363\underbrace{2^2^\cdot^\cdot^\cdot^2_\underbrace{2^2^\cdot^\cdot^\cdot^2_65536-3\mathrmhyper(2,m,5)3
3459612^2^65536-3A(4,  \underbrace{2^2^\cdot^\cdot^\cdot^2_\underbrace{2^2^\cdot^\cdot^\cdot^2_65536-3)\mathrmhyper(2,m,6)3
456111252^2^2^65536-3A(4,A(5,3))\mathrmhyper(2,m,7)3
567132532^2^2^2^65536-3A(4,A(5,4))\mathrmhyper(2,m,8)3
nn+1n+22n+32^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)\mathrmhyper(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) одного порядка с 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,\ldots{}A(1, 0)\ldots{})))прилично ускорит вычисление. Вычисление A(1, n) занимаетлинейное время n. Вычисление A(2, n) требуетквадратичное время, так как оно раскрывается в O(n) вложенныхвызовов A(1, i) для различных i. Время вычисленияA(3, n) пропорционально 4n+1.
 Значение A(4, n) невозможно посчитать с помощью простогорекурсивного применения за разумное время. Вместо этого для оптимизациирекурсивных вызовов используются сокращённые формулы, например,A(3, n) = 8×2n−3.
 Один из практичных способов вычисления значений функции Аккермана —мемоизация промежуточных результатов. Компилятор может применить этутехнику к функции автоматически, используя memo functions .