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

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

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

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

$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}}$

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

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

Історія

Початковий варіант такої функції (у дещо різній формі) запропонували учні Девіда Гільберта — Габрієль Судан (нім. G. Sudan) (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{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} -3\\n{\mbox{ + 3}}\end{matrix}}$

Нотація

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

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

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

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

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

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