4635
правок
Функция Акермана: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Функция Акермана''' (''[[Ackermann's function]]'') | '''Функция Акермана''' (''[[Ackermann's function]]'') — | ||
Функция <math>A</math> | Функция <math>\,A,</math> индуктивно заданная на парах неотрицательнх целых чисел | ||
<math> | :::::<math> | ||
\begin{array}{c} | \begin{array}{c} | ||
A(0,n) = n + 1; \\ | A(0,n) = n + 1; \\ | ||
| Строка 15: | Строка 15: | ||
<math> | :::::<math> | ||
\begin{array}{c} | \begin{array}{c} | ||
A(1,n) = n+2; \\ | A(1,n) = n+2; \\ | ||
| Строка 24: | Строка 24: | ||
Высокая рекурсивность этой функции используется для проверки | Высокая рекурсивность этой функции используется для проверки способности компиляторов выполнять рекурсию. Эта функция, названная в честь У. Акермана, является примером функции, которая вообще | ||
способности компиляторов выполнять рекурсию. Эта функция, названная в | рекурсивна, а не примитивно рекурсивна вследствие очень быстрого возрастания ее значения по мере увеличения <math>\,m.</math> Функцию Акермана можно также рассматривать как функцию Ack одной переменной: | ||
честь У.Акермана, является примером функции, которая вообще | :::::<math>\,\mbox{Ack}(n) = A(n,n),</math> | ||
рекурсивна, а не примитивно рекурсивна вследствие очень быстрого | |||
возрастания ее значения по мере увеличения <math>m</math> | |||
также рассматривать как функцию Ack одной переменной: | |||
<math>\mbox{Ack}(n) = A(n,n),</math> | |||
где <math>A</math> определено, как показано выше. Для нее имеем | где <math>\,A</math> определено, как показано выше. Для нее имеем | ||
<math> | :::::<math> | ||
\begin{array}{c} | \begin{array}{c} | ||
\mbox{Ack}(0) = 1, \\ | \mbox{Ack}(0) = 1, \\ | ||
| Строка 43: | Строка 39: | ||
Определим теперь функцию <math>G(n)</math> как наименьшее целое число <math>k</math> | Определим теперь функцию <math>\,G(n)</math> как наименьшее целое число <math>\,k,</math> для | ||
которого <math>\mbox{Ack}(k) \geq n</math> | которого <math>\mbox{Ack}(k) \geq n.</math> Функция <math>\,G</math> растет очень медленно. | ||
Действительно, <math>G(n) \leq 5</math> для всех "практических" значений <math>n</math> | Действительно, <math>G(n) \leq 5</math> для всех "практических" значений <math>\,n,</math> а | ||
именно для всех <math>n \leq 2^{65536}</math> | именно для всех <math>n \leq 2^{65536}.</math> Функция <math>\,G(n)</math> используется при | ||
оценке трудоемкости [[алгоритм|алгоритмов]]. | оценке трудоемкости [[алгоритм|алгоритмов]]. | ||
==Литература== | ==Литература== | ||
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991. | |||