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


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

Функция Аккермана — простой пример вычислимой функции, которая не является примитивно рекурсивной. Она принимает два неотрицательных целых числа в качестве параметров и возвращает натуральное число, обозначается 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. (источник?)

Один из практичных способов вычисления значений функции Аккермана - Мемоизация промежуточных результатов. Компилятор может применить эту технику к функции автоматически, используя 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

Ссылки




Wikimedia Foundation. 2010.

Смотреть что такое "Функция Аккермана" в других словарях:

  • Рекурсивная функция (теория вычислимости) — У этого термина существуют и другие значения, см. Рекурсивная функция (значения). Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций примитивно рекурсивные функции; общерекурсивные функции; …   Википедия

  • Числовая функция — В математике числовая функция  это функция, области определения и значений которой являются подмножествами числовых множеств  как правило, множества вещественных чисел или множества комплексных чисел . Содержание 1 График функции …   Википедия

  • Примитивно рекурсивная функция — Термин рекурсивные функции в теории вычислимости используют для обозначения трёх множеств функций примитивно рекурсивные функции; общерекурсивные функции; частично рекурсивные функции. Последние совпадают с множеством вычислимых по Тьюрингу… …   Википедия

  • Частично рекурсивная функция — Термин рекурсивные функции в теории вычислимости используют для обозначения трёх множеств функций примитивно рекурсивные функции; общерекурсивные функции; частично рекурсивные функции. Последние совпадают с множеством вычислимых по Тьюрингу… …   Википедия

  • Общерекурсивная функция — Термин рекурсивные функции в теории вычислимости используют для обозначения трёх множеств функций примитивно рекурсивные функции; общерекурсивные функции; частично рекурсивные функции. Последние совпадают с множеством вычислимых по Тьюрингу… …   Википедия

  • Тетрация — (гипероператор 4) в математике  итерационная функция экспоненты, следующий гипероператор после возведения в степень. Тетрация используется для описания больших чисел. Термин «тетрация», состоящий из слов «тетра » (четыре) и «итерация»… …   Википедия

  • Список математических функций — Эта страница информационный список. В математике, многие функции и группы функций настолько важны, что заслужили право на собственные имена. Ниже приведён список статей, которые содержат подробные описания некоторых из таких функций …   Википедия

  • Стрелочная нотация Кнута — В математике стрелочная нотация Кнута  это метод для записи больших чисел, предложенный Дональдом Кнутом в 1976 году.[1] Стрелочная нотация Кнута тесно связана с функцией Аккермана и особенно с последовательностью гипероператоров. Её идея… …   Википедия

  • Аккерман, Вильгельм — Вильгельм Аккерман Wilhelm Ackermann Дата рождения …   Википедия

  • Число Грехема — Число Грехема, названное в честь Рональда Грехема, это большое число которое является верхней границей для решения некоторой проблемы в теории Рамсея. Оно стало известно широкой публике после того, как Мартин Гарднер описал его в своей колонке… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.