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

Шаблон:UniboxФункція Акермана — у теорії складності обчислень є найпростішим прикладом обчислюваної функції, що не є примітивно-рекурсивною. Функція Акермана визначається рекурсивно для невід'ємних цілих чисел $m$ та $n$ таким чином:

$A(m,n)=\{\begin{array}{cc}n+1,& m=0;\\ A(m-1,1),& m>0,n=0;\\ A(m-1,A(m,n-1)),& m>0,n>0.\end{array}$

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

Функція зростає дуже швидко (значно швидше за експоненту). Наприклад, $A(4,4)=2^{2^{2^{65536}}}-3$, що перевищує кількість атомів у видимому Всесвіті.

Історія

Початковий варіант такої функції (у дещо різній формі) запропонували учні Девіда Гільберта — Габрієль Судан (Шаблон:Lang-de) (1927 року) і Шаблон:Нп (1928). Гільберт висловив гіпотезу, що функція не є примітивно-рекурсивною, і Вільгельм Акерман (що став секретарем Гільберта) цю гіпотезу довів. Оригінальна функція Аккермана мала три аргументи. Варіант із двома аргументами запропонували Роза Петер і Рафаєль Робінсон і саме його зазвичай мають на увазі під назвою функція Акермана.

Таблиця

Значення A(m, n)

m\n	0	1	2	3	4	n
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2=2+(n+3)-3$
2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13	65533	265536 − 3	$2^{2^{65536}}-3$	$2^{2^{2^{65536}}}-3$	$\begin{array}{c}\underbrace{{2^2}^{{\cdot }^{{\cdot }^{{\cdot }^2}}}}-3\\ n\text{ + 3}\end{array}$

Нотація

• Через гіпероператор:

  $A(m,n)=\mathrm{hyper}(2,m,n+3)-3$

• В нотації Кнута:

  $A(m,n)=2{\uparrow }^{m-2}(n+3)-3$

• В нотації Конвея:

  $A(m,n)=(2\to (n+3)\to (m-2))-3$