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

Функція Акермана
Названо на честь	Вільгельм Аккерманd
Досліджується в	теорія обчислюваності
Формула	${\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 n}$
Підтримується Вікіпроєктом	Вікіпедія:Проєкт:Математика

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

Функція Акермана визначається рекурсивно для невід'ємних цілих чисел ${\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)}$ завжди зменшується з точки зору лексикографічного порядку.

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

Початковий варіант такої функції (у дещо різній формі) запропонували учні Девіда Гільберта — Габрієль Судан (нім. G. Sudan) (1927 року) і Вільгельм Акерман^[en] (1928). Гільберт висловив гіпотезу, що функція не є примітивно-рекурсивною, і Вільгельм Акерман (що став секретарем Гільберта) цю гіпотезу довів. Оригінальна функція Аккермана мала три аргументи^[1]. Варіант із двома аргументами запропонували Роза Петер і Рафаєль Робінсон^[2] і саме його зазвичай мають на увазі під назвою функція Акермана.

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