Функция Акермана
Функция Акермана (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] используется при
оценке трудоемкости алгоритмов.
Литература
[Словарь]
