Просмотр кода страницы Функция Аккермана

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

== История ==
В конце 20-х годов XX века математики-ученики [[Гильберт, Давид|Давида Гильберта]], [[Судан, Габриэль|Габриэль Судан]] и [[Аккерман, Вильгельм|Вильгельм Аккерман]], изучали основы вычислений. Судан и Аккерман известны<ref>{{статья |издание={{Нп3|Historia Mathematica|Historia Math.||Historia Mathematica}} |заглавие=The first example of a recursive function which is not primitive recursive |страницы=380—384 |том=6 |номер=4 |doi=10.1016/0315-0860(79)90024-7 |язык=en |тип=journal |автор=''Cristian Calude, Solomon Marcus and Ionel Tevy'' |месяц=11 |год=1979}}</ref> за открытие всюду определённой [[вычислимая функция|вычислимой функции]] (иногда называемой просто «рекурсивной»), не являющейся [[Примитивно рекурсивная функция|примитивно рекурсивной]]. Судан открыл менее известную [[функция Судана|функцию Судана]], после чего, независимо от него, в 1928 году Аккерман опубликовал свою функцию <math>\varphi</math>. Функция трёх аргументов Аккермана <math>\varphi(m,\,n,\,p)</math> определялась так, что для <math>p=0,\;1,\;2</math> она проводила операцию сложения, умножения или возведения в степень:

: <math>\varphi(m,\,n,\,0) = m+n,</math>
: <math>\varphi(m,\,n,\,1) = m\cdot n,</math>
: <math>\varphi(m,\,n,\,2) = m^n,</math>
а для <math>p>2</math> она доопределяется с помощью [[Стрелочная нотация Кнута|стрелочной нотации Кнута]], опубликованной в 1976 году:
: <math>\varphi(m,\,n,\,p) = m\uparrow^{p - 1}(n + 1)</math>.
(Помимо её исторической роли как первой всюду определённой не примитивно рекурсивной вычислимой функции, оригинальная функция Аккермана расширяла основные арифметические операции за возведение в степень, хотя и не так хорошо, как специально предназначенные для этого функции вроде последовательности [[гипероператор]]ов [[Гудстейн, Рубен|Гудстейна]].)

В статье «On the Infinite» Гильберт высказал гипотезу о том, что функция Аккермана не является примитивно рекурсивной, а Аккерман (личный секретарь и бывший студент Гильберта) доказал эту гипотезу в статье «On Hilbert’s Construction of the Real Numbers». [[Роза Петер]] и [[Рафаэль Робинсон]] позже представили двухаргументную версию функции Аккермана, которую теперь многие авторы предпочитают оригинальной<ref>{{статья |заглавие=Recursion and double recursion |издание=[[Bulletin of the American mathematical society]] |том=54 |страницы=987—993 |ссылка=http://projecteuclid.org/DPubS?verb=Display&version=1.0&service=UI&handle=euclid.bams/1183512393&page=record |doi=10.1090/S0002-9904-1948-09121-2 |номер=10 |язык=und |автор=''Raphael M. Robinson'' |год=1948}}</ref>.

== Определение ==
Функция Аккермана определяется [[Рекурсия|рекурсивно]] для неотрицательных целых чисел <math>m</math> и <math>n</math> следующим образом:
: <math>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}</math>
Может показаться неочевидным, что рекурсия всегда заканчивается. Это следует из того, что при рекурсивном вызове или уменьшается значение <math>m</math>, или значение <math>m</math> сохраняется, но уменьшается значение <math>n</math>. Это означает, что каждый раз пара <math>(m,\;n)</math> уменьшается с точки зрения [[Лексикографический порядок|лексикографического порядка]], значит, значение <math>m</math> в итоге достигнет нуля: для одного значения <math>m</math> существует конечное число возможных значений <math>n</math> (так как первый вызов с данным <math>m</math> был произведён с каким-то определённым значением <math>n</math>, а в дальнейшем, если значение <math>m</math> сохраняется, значение <math>n</math> может только уменьшаться), а количество возможных значений <math>m</math>, в свою очередь, тоже конечно. Однако, при уменьшении <math>m</math> значение, на которое увеличивается <math>n</math>, неограниченно и обычно очень велико.

== Таблица значений ==
: ''Подробнее о hyper см. [[гипероператор]]''.

{| align="center" class="standard"
|+
! |<math>n</math><math>|m</math>
! |<math>0</math>
! |<math>1</math>
! |<math>2</math>
! |<math>3</math>
! |<math>4</math>
! |<math>5</math>
! |<math>m</math>
|-
! |<math>0</math>
| <math>1</math>
| <math>2</math>
| <math>3</math>
| <math>5</math>
| <math>13</math>
| <math>65533</math>
| <math>\mathrm{hyper}(2,\;m,\;3)-3</math>
|-
! |<math>1</math>
| <math>2</math>
| <math>3</math>
| <math>5</math>
| <math>13</math>
| <math>65533</math>
| <math>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}-3</math>
| <math>\mathrm{hyper}(2,\;m,\;4)-3</math>
|-
! |<math>2</math>
| <math>3</math>
| <math>4</math>
| <math>7</math>
| <math>29</math>
| <math>2^{65536}-3</math>
| <math>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}-3</math>
| <math>\mathrm{hyper}(2,\;m,\;5)-3</math>
|-
! |<math>3</math>
| <math>4</math>
| <math>5</math>
| <math>9</math>
| <math>61</math>
| <math>2^{2^{65536}}-3</math>
| <math>A(4,\;\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}-3)</math>
| <math>\mathrm{hyper}(2,\;m,\;6)-3</math>
|-
! |<math>4</math>
| <math>5</math>
| <math>6</math>
| <math>11</math>
| <math>125</math>
| <math>2^{2^{2^{65536}}}-3</math>
| <math>A(4,\;A(5,\;3))</math>
| <math>\mathrm{hyper}(2,\;m,\;7)-3</math>
|-
! |<math>5</math>
| <math>6</math>
| <math>7</math>
| <math>13</math>
| <math>253</math>
| <math>2^{2^{2^{2^{65536}}}}-3</math>
| <math>A(4,\;A(5,\;4))</math>
| <math>\mathrm{hyper}(2,\;m,\;8)-3</math>
|-
! |<math>n</math>
| <math>n+1</math>
| <math>n+2</math>
| <math>2n+3</math>
| <math>2^{n+3}-3</math>
| <math>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{n+3}-3</math>
| <math>\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{\underset{\underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{65536}}{\vdots}}-3</math> (всего <math>n</math> блоков <math>2^{2^{\cdot^{\cdot^{\cdot^2}}}}</math>)
| <math>\mathrm{hyper}(2,\;m,\;n+3)-3</math>
|+
|}

== Обратная функция ==
Так как функция <math>f(n)=A(n,\;n)</math>растёт очень быстро, обратная функция <math>f^{-1}(n)=\min\{k\geqslant 1:A(k,\;k)\geqslant n\}</math>, обозначаемая <math>\alpha</math>, растёт очень медленно. Эта функция встречается при исследовании [[Теория сложности вычислений|сложности]] некоторых [[алгоритм]]ов, например, [[система непересекающихся множеств|системы непересекающихся множеств]] или алгоритма Чазелла для построения [[минимальное остовное дерево|минимального остовного дерева]]<ref>[http://rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-2006 Дискретная математика: алгоритмы. Минимальные остовные деревья]</ref>. При [[Анализ алгоритмов|анализе]] [[Асимптотическая оценка|асимптотики]] можно считать, что для всех практически встречающихся чисел значение этой функции меньше пяти, так как <math>A(4,\,4)</math> не меньше <math>10^{10^{10^{19500}}}</math>.

== Использование в [[Тест производительности|тестах производительности]] ==
Функция Аккермана в силу своего определения имеет очень глубокий уровень рекурсии, что можно использовать для проверки способности [[компилятор]]а оптимизировать рекурсию. Первым функцию Аккермана для этого использовал Ингви Сандблад<ref>{{статья |заглавие=The Ackermann function. A theoretical, computational and formula manipulative study |издание=BIT |том=11 |страницы=107—119 |ссылка=http://www.springerlink.com/content/t0701h82385w7718/ |doi=10.1007/BF01935330 |язык=en |тип=journal |автор=''Y. Sundblad'' |год=1971}}</ref>.

Брайан Вичман (соавтор [[Тест производительности|теста производительности]] [[Whetstone]]) учёл эту статью при написании серии статей о тестировании оптимизации вызовов<ref>{{cite web|title=Ackermann's function: A study in the efficiency of calling procedures | year=1975 | url=http://history.dcs.ed.ac.uk/archive/docs/Imp_Benchmarks/ack.pdf|archiveurl=https://www.webcitation.org/65g0I9HTY|archivedate=2012-02-24}}</ref><ref>{{cite web|title=How to call procedures, or second thoughts on Ackermann's function | year=1977 | url=http://history.dcs.ed.ac.uk/archive/docs/Imp_Benchmarks/ackpe.pdf|archiveurl=https://www.webcitation.org/65g0Ic03P|archivedate=2012-02-24}}</ref><ref>{{cite web|title=Latest results from the procedure calling test. Ackermann's function | year=1982 | url=http://history.dcs.ed.ac.uk/archive/docs/Imp_Benchmarks/acklt.pdf|archiveurl=https://www.webcitation.org/65g0J3VJV|archivedate=2012-02-24}}</ref>.

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

Значение <math>A(4,\,n)</math> невозможно посчитать с помощью простого рекурсивного применения за разумное время. Вместо этого для оптимизации рекурсивных вызовов используются сокращённые формулы, например, <math>A(3,\,n)=8\cdot 2^n-3</math>.{{Нет АИ|11|2|2013}}

Один из практичных способов вычисления значений функции Аккермана — [[мемоизация]] промежуточных результатов. Компилятор может применить эту технику к функции автоматически, используя memo functions<ref name="Michie1968">''Michie, Donald'' Memo functions and machine learning, ''Nature'', No. 218, pp. 19—22, 1968.</ref><ref>[http://www.gtoal.com/plsql/ackerman-memo.pls.html Example: explicit memo function version of Ackermann’s function] implemented in PL/SQL.</ref> {{iw|Мичи, Дональд|Дональда Мичи|en|Donald Michie}}.

== Примечания ==
{{примечания}}

== Ссылки ==
* {{MathWorld|AckermannFunction|Ackermann Function}}

{{Гугология}}

{{Перевести|de|Ackermannfunktion}}

[[Категория:Арифметические функции]]
[[Категория:Большие числа]]
[[Категория:Теория сложности вычислений]]