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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Функція Акермана — в теорії складності обчислень є найпростішим прикладом обчислювальної функції, що не є примітивно-рекурсивною. Названа на честь автора — Вільгельма Акермана, студента Гільберта.

Функція Акермана визначається рекурсивно для невід'ємних цілих чисел та таким чином:

Рекурсія завжди закінчується, оскільки або зменшується значення , або значення зберігається, а зменшується значення . Тобто пара завжди зменшується з точки зору лексикографічного порядку.

Значення A(m, n)
m\n 0 1 2 3 4 n
0 1 2 3 4 5
1 2 3 4 5 6
2 3 5 7 9 11
3 5 13 29 61 125
4 13 65533 265536 − 3

Нотація[ред.ред. код]

  • Через гіпероператор:
  • В нотації Конвея: