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

Функция Акермана (Ackermann's function) — Функция [math]\displaystyle{ \,A, }[/math] индуктивно заданная на парах неотрицательнх целых чисел

[math]\displaystyle{ \begin{array}{c} A(0,n) = n + 1; \\ A(m+1,0) = A(m,1); \\ A(m+1, n+1) = A(m, A(m+1,n)), \end{array} }[/math]

где [math]\displaystyle{ m, n \geq 0 }[/math]. Следовательно,

[math]\displaystyle{ \begin{array}{c} A(1,n) = n+2; \\ A(2,n) = 2n+3; \\ A(3,n) = 2^{n+3} - 3. \end{array} }[/math]

Высокая рекурсивность этой функции используется для проверки способности компиляторов выполнять рекурсию. Эта функция, названная в честь У. Акермана, является примером функции, которая вообще рекурсивна, а не примитивно рекурсивна вследствие очень быстрого возрастания ее значения по мере увеличения [math]\displaystyle{ \,m. }[/math] Функцию Акермана можно также рассматривать как функцию Ack одной переменной:

[math]\displaystyle{ \,\mbox{Ack}(n) = A(n,n), }[/math]

где [math]\displaystyle{ \,A }[/math] определено, как показано выше. Для нее имеем

[math]\displaystyle{ \begin{array}{c} \mbox{Ack}(0) = 1, \\ \mbox{Ack}(i) = 2^{\mbox{Ack}(i-1)}\mbox{ для }i \gt 0. \end{array} }[/math]

Определим теперь функцию [math]\displaystyle{ \,G(n) }[/math] как наименьшее целое число [math]\displaystyle{ \,k, }[/math] для которого [math]\displaystyle{ \mbox{Ack}(k) \geq n. }[/math] Функция [math]\displaystyle{ \,G }[/math] растет очень медленно. Действительно, [math]\displaystyle{ G(n) \leq 5 }[/math] для всех "практических" значений [math]\displaystyle{ \,n, }[/math] а именно для всех [math]\displaystyle{ n \leq 2^{65536}. }[/math] Функция [math]\displaystyle{ \,G(n) }[/math] используется при оценке трудоемкости алгоритмов.

Литература

• Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.