Функція Аккермана - простий приклад обчислюваною функції, яка не є примітивно рекурсивною. Вона приймає два невід'ємних цілих числа в якості параметрів і повертає натуральне число, позначається A (m, \; n) . Ця функція зростає дуже швидко, наприклад, число A (4, \; 4) настільки велике, що кількість цифр у порядку цього числа багаторазово перевершує кількість атомів в спостерігається частини Всесвіту.


1. Історія

В кінці 20-х років XX століття математики-учні Давида Гільберта Габріель Судан і Вільгельм Аккерман вивчали основи обчислень. Судан і Аккерман відомі [1] за відкриття усюди певної обчислюваною (іноді званої просто "рекурсивної"), що не є примітивно рекурсивною. Судан відкрив менш відому функцію Судану, після чого, незалежно від нього, в 1928 Аккерман опублікував його функцію \ Varphi \, \! . Функція трьох аргументів Аккермана \ Varphi (m, n, p) \, \! визначалася так, що для p = 0, 1, 2, вона проводила операцію додавання, множення або зведення в ступінь:

\ Varphi (m, n, 0) = m + n, \, \!
\ Varphi (m, n, 1) = m \ cdot n, \, \!
\ Varphi (m, n, 2) = m ^ n, \, \!

а для p> 2 вона доопределяется за допомогою стрілочної нотації Кнута :

\ Varphi (m, n, p) = m \ uparrow ^ {p - 1} (n + 1) \, \! .

(Крім її історичної ролі як першої всюди визначеною не примітивно рекурсивною обчислюваною функції, оригінальна функція Аккермана розширювала основні арифметичні операції за зведення в ступінь, хоча і не так добре, як спеціально призначені для цього функції начебто послідовності гіпероператоров Гудстейн.)

У статті On the Infinite Гільберт висловив гіпотезу, що функція Аккермана не є примітивно рекурсивною, і Аккерман (особистий секретар і колишній студент Гільберта) довів цю гіпотезу в статті On Hilbert's Construction of the Real Numbers. Роза Петер і Рафаель Робінсон пізніше представили двухаргументную версію функції Аккермана, яку тепер багато авторів віддають перевагу оригінальній. [2]


2. Визначення

Функція Аккермана визначається рекурсивно для невід'ємних цілих чисел 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) зменшується з точки зору лексикографічного порядку, значить, значення m в підсумку досягне нуля: для одного значення m існує кінцеве число можливих значень n (Так як перший виклик з даними m був проведений з якимось певним значенням n , А в подальшому, якщо значення m зберігається, значення n може тільки зменшуватися), а кількість можливих значень m , В свою чергу, теж звичайно. Однак, при зменшенні m значення, на яке збільшується n , Необмежена і зазвичай дуже велике.


3. Таблиця значень

Докладніше про hyper см Гіпероператор
n \ m012345m
012351365533\ Mathrm {hyper} (2, \; m, \; 3) -3
12351365533\ Underbrace {2 ^ {2 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ 2}}}}} _ {65536} -3\ Mathrm {hyper} (2, \; m, \; 4) -3
2347292 ^ {65536} -3\ Mathrm {hyper} (2, \; m, \; 5) -3
3459612 ^ {2 ^ {65536}} -3\ Mathrm {hyper} (2, \; m, \; 6) -3
456111252 ^ {2 ^ {2 ^ {65536}}} -3A (4, \; A (5, \; 3))\ Mathrm {hyper} (2, \; m, \; 7) -3
567132532 ^ {2 ^ {2 ^ {2 ^ {65536}}}} -3A (4, \; A (5, \; 4))\ Mathrm {hyper} (2, \; m, \; 8) -3
nn +1n +22n +32 ^ {n +3} -3\ Underbrace {2 ^ {2 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ 2}}}}} _ {n +3} -3 (Всього n блоків 2 ^ {2 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ 2}}}} ) \ Mathrm {hyper} (2, \; m, \; n +3) -3

4. Зворотній функція

Так як функція f (n) = A (n, \; n) росте дуже швидко, зворотна функція f ^ {-1} (n) = \ min \ {k \ geqslant 1: A (k, \; k) \ geqslant n \} , Що позначається α, росте дуже повільно. Ця функція зустрічається при дослідженні складності деяких алгоритмів, наприклад, системи непересічних множин або алгоритму Чазелла для побудови мінімального остовного дерева [3]. При аналізі асимптотики можна вважати, що для всіх практично зустрічаються чисел значення цієї функції менше п'яти, так як A (4, 4) одного порядку з 2 ^ {2 ^ {10 ^ {19729}}} .


5. Використання в бенчмарках

Функція Аккермана в силу свого визначення має дуже глибокий рівень рекурсії, що можна використовувати для перевірки здатності компілятора оптимізувати рекурсію. Першим функцію Аккермана для цього використовував Інгві Сандблад [4].

Брайан Вічман (співавтор бенчмарка Whetstone) врахував цю статтю при написанні серії статей про тестування оптимізації викликів [5] [6] [7].

Наприклад, компілятор, який аналізуючи обчислення A (3, 30) здатний зберігати проміжні значення зразок A (3, n) і A (2, n), може прискорити обчислення A (3, 30) в сотні і тисячі разів. Також обчислення A (2, n) безпосередньо замість рекурсивного розкриття в A (1, A (1, A (1, ... A (1, 0) ...))) пристойно прискорить обчислення. Обчислення A (1, n) займає лінійний час n. Обчислення A (2, n) вимагає квадратичне час, тому воно розкривається в O (n) вкладених викликів A (1, i) для різних i. Обчислення A (3, n) вимагає часу пропорційно 4 n +1.

A (4, 2) неможливо порахувати за допомогою простого рекурсивного застосування за розумний час. Замість цього для оптимізації рекурсивних викликів використовуються скорочені формули на зразок A (3, n) = 8 2 n -3. (Джерело?)

Один з практичних способів обчислення значень функції Аккермана - Мемоізація проміжних результатів. Компілятор може застосувати цю техніку до функції автоматично, використовуючи memo functions [8] [9] Дональда Мічі.


Примітки

  1. Cristian Calude, Solomon Marcus and Ionel Tevy (November 1979). "The first example of a recursive function which is not primitive recursive". Historia Math. 6 (4): 380-84. DOI : 10.1016/0315-0860 (79) 90024-7 - dx.doi.org/10.1016/0315-0860 (79) 90024-7.
  2. Raphael M. Robinson (1948). " Recursion and Double Recursion - of the American Mathematical Society 54 (10): 987-993. DOI : 10.1090/S0002-9904-1948-09121-2 - dx.doi.org/10.1090/S0002-9904-1948-09121-2.
  3. Дискретна математика: алгоритми. Мінімальні остовного дерева - rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-2006
  4. Y. Sundblad (1971). " The Ackermann function, A theoretical, computational and formula manipulative study - www.springerlink.com/content/t0701h82385w7718/ ". BIT 11: 107-119. DOI : 10.1007/BF01935330 - dx.doi.org/10.1007/BF01935330.
  5. Ackermann's Function: A Study In The Efficiency Of Calling Procedures - history.dcs.ed.ac.uk / archive / docs / Imp_Benchmarks / ack.pdf (1975). Читальний - www.webcitation.org/65g0I9HTY з першоджерела 24 лютого 2012.
  6. How to Call Procedures, or Second Thoughts on Ackermann's Function - history.dcs.ed.ac.uk / archive / docs / Imp_Benchmarks / ackpe.pdf (1977). Читальний - www.webcitation.org/65g0Ic03P з першоджерела 24 лютого 2012.
  7. Latest results from the procedure calling test, Ackermann's function - history.dcs.ed.ac.uk / archive / docs / Imp_Benchmarks / acklt.pdf (1982). Читальний - www.webcitation.org/65g0J3VJV з першоджерела 24 лютого 2012.
  8. Michie, Donald, "Memo Functions and Machine Learning," Nature, No. 218, pp. 19-22, 1968.
  9. Example: Explicit memo function version of Ackermann's function - www.gtoal.com / plsql / ackerman-memo.pls.html implemented in PL / SQL