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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

История

В конце 20-х годов XX века математики-ученики Давида Гильберта, Габриэль Судан и Вильгельм Аккерман, изучали основы вычислений. Судан и Аккерман известны[1] открытием всюду определённой вычислимой функции (иногда называемой просто «рекурсивной»), не являющейся примитивно рекурсивной. Судан открыл менее известную функцию Судана, после чего, независимо от него, в 1928 году Аккерман опубликовал свою функцию [math]\displaystyle{ \varphi }[/math]. Функция трёх аргументов Аккермана [math]\displaystyle{ \varphi(m,\,n,\,p) }[/math] определялась так, что для [math]\displaystyle{ p=0,\;1,\;2 }[/math] она проводила операцию сложения, умножения или возведения в степень:

[math]\displaystyle{ \varphi(m,\,n,\,0) = m+n, }[/math]
[math]\displaystyle{ \varphi(m,\,n,\,1) = m\cdot n, }[/math]
[math]\displaystyle{ \varphi(m,\,n,\,2) = m^n, }[/math]

а для [math]\displaystyle{ p\gt 2 }[/math] она доопределяется с помощью стрелочной нотации Кнута, опубликованной в 1976 году:

[math]\displaystyle{ \varphi(m,\,n,\,p) = m\uparrow^{p - 1}(n + 1) }[/math].

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

В статье «On the Infinite» Гильберт высказал гипотезу о том, что функция Аккермана не является примитивно рекурсивной, а Аккерман (личный секретарь и бывший студент Гильберта) доказал эту гипотезу в статье «On Hilbert’s Construction of the Real Numbers». Роза Петер и Рафаэль Робинсон позже представили двухаргументную версию функции Аккермана, которую теперь многие авторы предпочитают оригинальной[2].

Определение

Функция Аккермана определяется рекурсивно для неотрицательных целых чисел [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] следующим образом:

[math]\displaystyle{ A(m,\;n)=\begin{cases}n+1,&m=0;\\A(m-1,\;1),&m\gt 0,\;n=0;\\A(m-1,\;A(m,\;n-1)),&m\gt 0,\;n\gt 0.\end{cases} }[/math]

Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение [math]\displaystyle{ m }[/math], или значение [math]\displaystyle{ m }[/math] сохраняется, но уменьшается значение [math]\displaystyle{ n }[/math]. Это означает, что каждый раз пара [math]\displaystyle{ (m,\;n) }[/math] уменьшается с точки зрения лексикографического порядка, значит, значение [math]\displaystyle{ m }[/math] в итоге достигнет нуля: для одного значения [math]\displaystyle{ m }[/math] существует конечное число возможных значений [math]\displaystyle{ n }[/math] (так как первый вызов с данным [math]\displaystyle{ m }[/math] был произведён с каким-то определённым значением [math]\displaystyle{ n }[/math], а в дальнейшем, если значение [math]\displaystyle{ m }[/math] сохраняется, значение [math]\displaystyle{ n }[/math] может только уменьшаться), а количество возможных значений [math]\displaystyle{ m }[/math], в свою очередь, тоже конечно. Однако, при уменьшении [math]\displaystyle{ m }[/math] значение, на которое увеличивается [math]\displaystyle{ n }[/math], неограниченно и обычно очень велико.

Таблица значений

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

Обратная функция

Так как функция [math]\displaystyle{ f(n)=A(n,\;n) }[/math]растёт очень быстро, обратная функция [math]\displaystyle{ f^{-1}(n)=\min\{k\geqslant 1:A(k,\;k)\geqslant n\} }[/math], обозначаемая [math]\displaystyle{ \alpha }[/math], растёт очень медленно. Эта функция встречается при исследовании сложности некоторых алгоритмов, например, системы непересекающихся множеств или алгоритма Чазелла для построения минимального остовного дерева[3]. При анализе асимптотики можно считать, что для всех практически встречающихся чисел значение этой функции меньше пяти, так как [math]\displaystyle{ A(4,\,4) }[/math] не меньше [math]\displaystyle{ 10^{10^{10^{19500}}} }[/math].

Использование в тестах производительности

Функция Аккермана в силу своего определения имеет очень глубокий уровень рекурсии, что можно использовать для проверки способности компилятора оптимизировать рекурсию. Первым функцию Аккермана для этого использовал Ингви Сандблад[4].

Брайан Вичман (соавтор теста производительности Whetstone) учёл эту статью при написании серии статей о тестировании оптимизации вызовов[5][6][7].

Например, компилятор, который анализируя вычисление [math]\displaystyle{ A(3,\,30) }[/math] способен сохранять промежуточные значения, например, [math]\displaystyle{ A(3,\,n) }[/math] и [math]\displaystyle{ A(2,\,n) }[/math], может ускорить вычисление [math]\displaystyle{ A(3,\,30) }[/math] в сотни и тысячи раз. Также вычисление [math]\displaystyle{ A(2,\,n) }[/math] напрямую вместо рекурсивного раскрытия в [math]\displaystyle{ A(1,\,A(1,\,A(1,\,\ldots A(1,\,0)\ldots))) }[/math] прилично ускорит вычисление. Вычисление [math]\displaystyle{ A(1,\,n) }[/math] занимает линейное время [math]\displaystyle{ n }[/math]. Вычисление [math]\displaystyle{ A(2,\,n) }[/math] требует квадратичное время, так как оно раскрывается в O([math]\displaystyle{ n }[/math]) вложенных вызовов [math]\displaystyle{ A(1,\,i) }[/math] для различных [math]\displaystyle{ i }[/math]. Время вычисления [math]\displaystyle{ A(3,\,n) }[/math] пропорционально [math]\displaystyle{ 4^{n+1} }[/math].

Значение [math]\displaystyle{ A(4,\,n) }[/math] невозможно посчитать с помощью простого рекурсивного применения за разумное время. Вместо этого для оптимизации рекурсивных вызовов используются сокращённые формулы, например, [math]\displaystyle{ A(3,\,n)=8\cdot 2^n-3 }[/math].[источник не указан 4345 дней]

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

Примечания

  1. ↑ Cristian Calude, Solomon Marcus and Ionel Tevy. The first example of a recursive function which is not primitive recursive (англ.) // Historia Math.[англ.] : journal. — 1979. — November (vol. 6, no. 4). — P. 380—384. — doi:10.1016/0315-0860(79)90024-7.
  2. ↑ Raphael M. Robinson. Recursion and double recursion (неопр.) // Bulletin of the American mathematical society. — 1948. — Т. 54, № 10. — С. 987—993. — doi:10.1090/S0002-9904-1948-09121-2. Архивировано 7 июня 2011 года.
  3. ↑ Дискретная математика: алгоритмы. Минимальные остовные деревья (недоступная ссылка). Дата обращения: 13 августа 2011. Архивировано 2 июня 2010 года.
  4. ↑ Y. Sundblad. The Ackermann function. A theoretical, computational and formula manipulative study (англ.) // BIT : journal. — 1971. — Vol. 11. — P. 107—119. — doi:10.1007/BF01935330. (недоступная ссылка)
  5. ↑ Ackermann's function: A study in the efficiency of calling procedures (1975). Дата обращения: 13 августа 2011. Архивировано 23 февраля 2012 года.
  6. ↑ How to call procedures, or second thoughts on Ackermann's function (1977). Дата обращения: 13 августа 2011. Архивировано 23 февраля 2012 года.
  7. ↑ Latest results from the procedure calling test. Ackermann's function (1982). Дата обращения: 13 августа 2011. Архивировано 23 февраля 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 Архивная копия от 17 июля 2011 на Wayback Machine implemented in PL/SQL.

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Функция_Аккермана&oldid=5868029