Функция Акермана: различия между версиями

'''Функция Акермана''' (''[[Ackermann's function]]'') —

Функция <math>\,A,</math> индуктивно заданная на парах неотрицательнх целых чисел

:::::<math>

:::::<math>

Высокая рекурсивность этой функции используется для проверки способности компиляторов выполнять рекурсию. Эта функция, названная в честь У. Акермана, является примером функции, которая вообще

рекурсивна, а не примитивно рекурсивна вследствие очень быстрого возрастания ее значения по мере увеличения <math>\,m.</math> Функцию Акермана можно также рассматривать как функцию Ack одной переменной:

:::::<math>\,\mbox{Ack}(n) = A(n,n),</math>

где <math>\,A</math> определено, как показано выше. Для нее имеем

:::::<math>

Определим теперь функцию <math>\,G(n)</math> как наименьшее целое число <math>\,k,</math> для

которого <math>\mbox{Ack}(k) \geq n.</math> Функция <math>\,G</math> растет очень медленно.

Действительно, <math>G(n) \leq 5</math> для всех "практических" значений <math>\,n,</math> а

именно для всех <math>n \leq 2^{65536}.</math> Функция <math>\,G(n)</math> используется при