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

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

Функція Акермана
Названо на честь	^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). Гільберт висловив гіпотезу, що функція не є примітивно-рекурсивною, і Вільгельм Акерман (що став секретарем Гільберта) цю гіпотезу довів. Оригінальна функція Аккермана мала три аргументи. Варіант із двома аргументами запропонували Роза Петер і і саме його зазвичай мають на увазі під назвою функція Акермана.

Таблиця

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

Джерела

1. Cristian Calude, Solomon Marcus, Ionel Tevy. The first example of a recursive function which is not primitive recursive // Historia Math. : journal. — 1979. — Vol. 6, no. 4 (11). — P. 380—384. — DOI:10.1016/0315-0860(79)90024-7.
2. Raphael M. Robinson. Recursion and double recursion // . — 1948. — Vol. 54, no. 10. — P. 987—993. — DOI:10.1090/S0002-9904-1948-09121-2.

Посилання