Відкрити головне меню

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

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

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

Значення 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

НотаціяРедагувати

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

ПосиланняРедагувати