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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Функція Акермана визначається рекурсивно для невід'ємних цілих чисел \ 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(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}

Нотація[ред.ред. код]