WikiSort.ru - Не сортированное

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

История

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

${\displaystyle \varphi (m,\,n,\,0)=m+n,}$

${\displaystyle \varphi (m,\,n,\,1)=m\cdot n,}$

${\displaystyle \varphi (m,\,n,\,2)=m^{n},}$

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

${\displaystyle \varphi (m,\,n,\,p)=m\uparrow ^{p-1}(n+1)}$ .

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

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

Определение

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

${\displaystyle 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}}}$

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

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

Подробнее о hyper см. гипероператор.

${\displaystyle n}$ ${\displaystyle |m}$	${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle 3}$	${\displaystyle 4}$	${\displaystyle 5}$	${\displaystyle m}$
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle 3}$	${\displaystyle 5}$	${\displaystyle 13}$	${\displaystyle 65533}$	${\displaystyle \mathrm {hyper} (2,\;m,\;3)-3}$
${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle 3}$	${\displaystyle 5}$	${\displaystyle 13}$	${\displaystyle 65533}$	${\displaystyle \underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{65536}-3}$	${\displaystyle \mathrm {hyper} (2,\;m,\;4)-3}$
${\displaystyle 2}$	${\displaystyle 3}$	${\displaystyle 4}$	${\displaystyle 7}$	${\displaystyle 29}$	${\displaystyle 2^{65536}-3}$	${\displaystyle \underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{\underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{65536}}-3}$	${\displaystyle \mathrm {hyper} (2,\;m,\;5)-3}$
${\displaystyle 3}$	${\displaystyle 4}$	${\displaystyle 5}$	${\displaystyle 9}$	${\displaystyle 61}$	${\displaystyle 2^{2^{65536}}-3}$	${\displaystyle A(4,\;\underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{\underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{65536}}-3)}$	${\displaystyle \mathrm {hyper} (2,\;m,\;6)-3}$
${\displaystyle 4}$	${\displaystyle 5}$	${\displaystyle 6}$	${\displaystyle 11}$	${\displaystyle 125}$	${\displaystyle 2^{2^{2^{65536}}}-3}$	${\displaystyle A(4,\;A(5,\;3))}$	${\displaystyle \mathrm {hyper} (2,\;m,\;7)-3}$
${\displaystyle 5}$	${\displaystyle 6}$	${\displaystyle 7}$	${\displaystyle 13}$	${\displaystyle 253}$	${\displaystyle 2^{2^{2^{2^{65536}}}}-3}$	${\displaystyle A(4,\;A(5,\;4))}$	${\displaystyle \mathrm {hyper} (2,\;m,\;8)-3}$
${\displaystyle n}$	${\displaystyle n+1}$	${\displaystyle n+2}$	${\displaystyle 2n+3}$	${\displaystyle 2^{n+3}-3}$	${\displaystyle \underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{n+3}-3}$	${\displaystyle \underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{\underset {\underbrace {2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}} _{65536}}{\vdots }}-3}$ (всего ${\displaystyle n}$ блоков ${\displaystyle 2^{2^{\cdot ^{\cdot ^{\cdot ^{2}}}}}}$ )	${\displaystyle \mathrm {hyper} (2,\;m,\;n+3)-3}$

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

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

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

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

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

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

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

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

Примечания

Ссылки

• Weisstein, Eric W. Ackermann Function (англ.) на сайте Wolfram MathWorld.

В другом языковом разделе есть более полная статья Ackermannfunktion (нем.). Вы можете помочь проекту, расширив текущую статью с помощью перевода. При этом, для соблюдения правил атрибуции, следует установить шаблон {{переведённая статья}} на страницу обсуждения, либо указать ссылку на статью-источник в комментарии к правке.