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

Історія

Таблиця

Нотація

Джерела

Посилання

Функція Акермана — у теорії складності обчислень є найпростішим прикладом обчислюваної функції, що не є примітивно-рекурсивною. Функція Акермана визначається рекурсивно для невід'ємних цілих чисел $\ 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). Гільберт висловив гіпотезу, що функція не є примітивно-рекурсивною, і Вільгельм Акерман (що став секретарем Гільберта) цю гіпотезу довів. Оригінальна функція Аккермана мала три аргументи[1]. Варіант із двома аргументами запропонували Роза Петер і Рафаєль Робінсон[2] і саме його зазвичай мають на увазі під назвою функція Акермана.

Через гіпероператор:
$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$

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.
Raphael M. Robinson. Recursion and double recursion // Bull. Amer. Math. Soc.. — 1948. — Vol. 54, no. 10. — P. 987—993. — DOI:10.1090/S0002-9904-1948-09121-2.

$n+2=2+(n+3)-3$

$2n+3=2\cdot (n+3)-3$

$2^{(n+3)}-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}}$

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[0315-0860(79)90024-7-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 // Bull. Amer. Math. Soc.. — 1948. — Vol. 54, no. 10. — P. 987—993. — DOI:10.1090/S0002-9904-1948-09121-2.