Приклад рекурсивної функції Акермана

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

Функція Акермана визначається рекурсивно для невід'ємних цілих чисел ${\displaystyle \ m}$ та ${\displaystyle \ n}$ таким чином:

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

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

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

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

Нотація

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

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

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

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

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

  ${\displaystyle A(m,n)={\Big (}2\rightarrow (n+3)\rightarrow (m-2){\Big )}-3}$