Функція Акермана — у теорії складності обчислень є найпростішим прикладом обчислюваної функції, що не є (примітивно-рекурсивною).
Функція Акермана | |
Названо на честь | d |
---|---|
Досліджується в | теорія обчислюваності |
Формула | |
Позначення у формулі | і |
Підтримується Вікіпроєктом |
Функція Акермана визначається рекурсивно для невід'ємних цілих чисел та таким чином:
Рекурсія завжди закінчується, оскільки або зменшується значення , або значення зберігається, а зменшується значення . Тобто пара завжди зменшується з точки зору лексикографічного порядку.
Функція зростає дуже швидко (значно швидше за експоненту). Наприклад, , що перевищує кількість атомів у видимому Всесвіті.
Історія
Початковий варіант такої функції (у дещо різній формі) запропонували учні Девіда Гільберта — Габрієль Судан (нім. G. Sudan) (1927 року) і [en] (1928). Гільберт висловив гіпотезу, що функція не є примітивно-рекурсивною, і Вільгельм Акерман (що став секретарем Гільберта) цю гіпотезу довів. Оригінальна функція Аккермана мала три аргументи. Варіант із двома аргументами запропонували (Роза Петер) і і саме його зазвичай мають на увазі під назвою функція Акермана.
Таблиця
m\n | 0 | 1 | 2 | 3 | 4 | n |
---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | |
1 | 2 | 3 | 4 | 5 | 6 | |
2 | 3 | 5 | 7 | 9 | 11 | |
3 | 5 | 13 | 29 | 61 | 125 | |
4 | 13 | 65533 | 265536 − 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: .
- Raphael M. Robinson. Recursion and double recursion // . — 1948. — Vol. 54, no. 10. — P. 987—993. — DOI: .
Посилання
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет