Функція Акермана — у теорії складності обчислень є найпростішим прикладом обчислюваної функції, що не є примітивно-рекурсивною. Функція Акермана визначається рекурсивно для невід'ємних цілих чисел та таким чином:
Рекурсія завжди закінчується, оскільки або зменшується значення , або значення зберігається, а зменшується значення . Тобто пара завжди зменшується з точки зору лексикографічного порядку.
Функція зростає дуже швидко (значно швидше за експоненту). Наприклад, , що перевищує кількість атомів у видимому Всесвіті.
Історія Початковий варіант такої функції (у дещо різній формі) запропонували учні Девіда Гільберта — Габрієль Судан () (1927 року) і Вільгельм Акерман (1928). Гільберт висловив гіпотезу, що функція не є примітивно-рекурсивною, і Вільгельм Акерман (що став секретарем Гільберта) цю гіпотезу довів. Оригінальна функція Аккермана мала три аргументи. Варіант із двома аргументами запропонували Роза Петер і Рафаєль Робінсон і саме його зазвичай мають на увазі під назвою функція Акермана.
Таблиця + Значення 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
Нотація Через гіпероператор:
В нотації Кнута:
В нотації Конвея:
Джерела
Посилання