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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Функция Аккермана — простой пример всюду определённой вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается A(m,\;n). Эта функция растёт очень быстро, например, число A(4,\;4) настолько велико, что количество цифр в порядке этого числа многократно превосходит количество атомов в наблюдаемой части Вселенной.

История[править | править исходный текст]

В конце 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]

Определение[править | править исходный текст]

Функция Аккермана определяется рекурсивно для неотрицательных целых чисел 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, неограничено и обычно очень велико.

Таблица значений[править | править исходный текст]

Подробнее о hyper см Гипероператор
n|m 0 1 2 3 4 5 m
0 1 2 3 5 13 65533 \mathrm{hyper}(2,\;m,\;3)-3
1 2 3 5 13 65533 \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}-3 \mathrm{hyper}(2,\;m,\;4)-3
2 3 4 7 29 2^{65536}-3 \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}-3 \mathrm{hyper}(2,\;m,\;5)-3
3 4 5 9 61 2^{2^{65536}}-3 A(4,\;\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}-3) \mathrm{hyper}(2,\;m,\;6)-3
4 5 6 11 125 2^{2^{2^{65536}}}-3 A(4,\;A(5,\;3)) \mathrm{hyper}(2,\;m,\;7)-3
5 6 7 13 253 2^{2^{2^{2^{65536}}}}-3 A(4,\;A(5,\;4)) \mathrm{hyper}(2,\;m,\;8)-3
n n+1 n+2 2n+3 2^{n+3}-3 \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{n+3}-3 \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underset{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}{\vdots}}-3 (всего n блоков 2^{2^{\cdot^{\cdot^{\cdot^2}}}}) \mathrm{hyper}(2,\;m,\;n+3)-3

Обратная функция[править | править исходный текст]

Так как функция 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}}}.

Использование в тестах производительности[править | править исходный текст]

Функция Аккермана в силу своего определения имеет очень глубокий уровень рекурсии, что можно использовать для проверки способности компилятора оптимизировать рекурсию. Первым функцию Аккермана для этого использовал Ингви Сандблад [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) требует времени пропорционально 4n+1.

A(4, 2) невозможно посчитать с помощью простого рекурсивного применения за разумное время. Вместо этого для оптимизации рекурсивных вызовов используются сокращенные формулы вроде A(3, n) = 8×2n−3.[источник не указан 424 дня]

Один из практичных способов вычисления значений функции Аккермана - Мемоизация промежуточных результатов. Компилятор может применить эту технику к функции автоматически, используя 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.
  2. Raphael M. Robinson (1948). «Recursion and Double Recursion». Bulletin of the American Mathematical Society 54 (10): 987-993. DOI:10.1090/S0002-9904-1948-09121-2.
  3. Дискретная математика: алгоритмы. Минимальные остовные деревья
  4. Y. Sundblad (1971). «The Ackermann function, A theoretical, computational and formula manipulative study». BIT 11: 107–119. DOI:10.1007/BF01935330.
  5. Ackermann's Function: A Study In The Efficiency Of Calling Procedures (1975). Архивировано из первоисточника 24 февраля 2012.
  6. How to Call Procedures, or Second Thoughts on Ackermann's Function (1977). Архивировано из первоисточника 24 февраля 2012.
  7. Latest results from the procedure calling test, Ackermann's function (1982). Архивировано из первоисточника 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 implemented in PL/SQL

Ссылки[править | править исходный текст]