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

В теории вычислимости , то функция Аккермана , названная в честь Вильгельма Аккермана , является одним из самых простых ^[1] и ранних обнаруженных примеров полной вычислимой функции , которая не является примитивно рекурсивным . Все примитивно-рекурсивные функции являются тотальными и вычислимыми, но функция Аккермана показывает, что не все итоговые вычислимые функции являются примитивно рекурсивными. После публикации Аккермана ^[2]его функции (у которой было три неотрицательных целочисленных аргумента) многие авторы модифицировали ее для различных целей, так что сегодня «функция Аккермана» может относиться к любому из многочисленных вариантов исходной функции. Одна из распространенных версий, функция Аккермана – Петера с двумя аргументами , определяется следующим образом для неотрицательных целых чисел m и n :

${\displaystyle {\begin{aligned}\operatorname {A} (0,n)&=n+1\\\operatorname {A} (m,0)&=\operatorname {A} (m-1,1)\\\operatorname {A} (m,n)&=\operatorname {A} (m-1,\operatorname {A} (m,n-1))\end{aligned}}}$

Его ценность быстро растет даже при небольших затратах. Например, A (4, 2) представляет собой целое число из 19729 десятичных цифр ^[3] (эквивалент 2 ⁶⁵⁵³⁶ −3 или 2 ^{2 2 2 2} −3).

История [ править ]

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

${\displaystyle {\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,n,1)&=m\times n\\\varphi (m,n,2)&=m^{n}\end{aligned}}}$

а для p > 2 он расширяет эти базовые операции способом, который можно сравнить с гипероперациями :

${\displaystyle {\begin{aligned}\varphi (m,n,3)&=m[4](n+1)\\\varphi (m,n,p)&\gtrapprox m[p+1](n+1)&&{\text{for }}p>3\end{aligned}}}$

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

В На Бесконечного , ^[5] Давид Гильберт выдвинул гипотезу о том , что функция Аккермана не примитивно рекурсивная, но это было Ackermann, Гильберта личный секретарь и бывший студент, который на самом деле доказал гипотезу в своей статье О построении Гильберта вещественных чисел . ^{[2] [6]}

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

Обобщенная последовательность гиперопераций , например , также является версией функции Аккермана. ^[9]${\displaystyle \operatorname {G} (m,a,b)=a[m]b}$

В 1963 году Р. К. Бак основал интуитивно понятный вариант с двумя переменными ( ^[10] ) на последовательности гиперопераций : ^[11]${\displaystyle \operatorname {F} }$

${\displaystyle \operatorname {F} (m,n)=2[m]n.}$

По сравнению с большинством других версий функция Бака не имеет несущественных смещений:

${\displaystyle {\begin{aligned}\operatorname {F} (0,n)&=2[0]n=n+1\\\operatorname {F} (1,n)&=2[1]n=2+n\\\operatorname {F} (2,n)&=2[2]n=2\times n\\\operatorname {F} (3,n)&=2[3]n=2^{n}\\\operatorname {F} (4,n)&=2[4]n=2^{2^{2^{{}^{.^{.^{{}_{.}2}}}}}}\\&\quad \vdots \end{aligned}}}$

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

Исходная функция Аккермана с тремя аргументами рекурсивно определяется следующим образом для неотрицательных целых чисел и :${\displaystyle \varphi (m,n,p)}$${\displaystyle m,n,}$${\displaystyle p}$

${\displaystyle {\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,0,1)&=0\\\varphi (m,0,2)&=1\\\varphi (m,0,p)&=m&&{\text{for }}p>2\\\varphi (m,n,p)&=\varphi (m,\varphi (m,n-1,p),p-1)&&{\text{for }}n,p>0\end{aligned}}}$

Из различных версий с двумя аргументами вариант, разработанный Петером и Робинсоном (называемый некоторыми авторами «функцией Аккермана»), определен для неотрицательных целых чисел и выглядит следующим образом:${\displaystyle m}$${\displaystyle n}$

${\displaystyle {\begin{aligned}\operatorname {A} (0,n)&=n+1\\\operatorname {A} (m,0)&=\operatorname {A} (m-1,1)\\\operatorname {A} (m,n)&=\operatorname {A} (m-1,\operatorname {A} (m,n-1))\end{aligned}}}$

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

Функция Петера-Аккермана также может быть выражена по отношению к различным другим версиям функции Аккермана:

• гипероперация :

${\displaystyle A(m,n)={\begin{cases}0[m]n&m=0\\2[m](n+3)-3&m>0\\\end{cases}}}$

• гипероперация , представленная стрелкой вверх Кнута (расширенная до целочисленных индексов ):${\displaystyle \geq -2}$

${\displaystyle A(m,n)={\begin{cases}0\uparrow ^{m-2}n&m=0\\2\uparrow ^{m-2}(n+3)-3&m>0\\\end{cases}}}$

• гипероперация , представленная в нотации стрелок Конвея :

${\displaystyle {\begin{aligned}A(m,n)=(2\to (n+3)\to (m-2))-3&&m\geq 3.\end{aligned}}}$

Следовательно

${\displaystyle {\begin{aligned}2\to n\to m=A(m+2,n-3)+3&&n>2.\end{aligned}}}$

( и будет соответствовать и , которые можно было бы логически добавить.)${\displaystyle n=1}$${\displaystyle n=2}$${\displaystyle A(m,-2)=-1}$${\displaystyle A(m,-1)=1}$

Для малых значений m, таких как 1, 2 или 3, функция Аккермана растет относительно медленно по отношению к n (не более чем экспоненциально ). Для , однако, он растет гораздо быстрее; даже около 2 × 10 ^{19 728} , а также расширение десятичного из A (4, 3) очень велико по любой типичной мере.${\displaystyle m\geq 4}$${\displaystyle A(4,2)}$

Интересным аспектом функции (Петера-) Аккермана является то, что единственная арифметическая операция, которую она когда-либо использует, - это сложение 1. Ее быстрорастущие возможности основаны исключительно на вложенной рекурсии. Это также означает, что время его работы, по крайней мере, пропорционально его производительности, и поэтому оно также чрезвычайно велико. На самом деле, в большинстве случаев время работы намного больше, чем результат; см. ниже.

Версия с одним аргументом, которая увеличивает обе и в то же время затмевает каждую примитивную рекурсивную функцию, включая очень быстрорастущие функции, такие как экспоненциальная функция , факториальная функция, много- и сверхфакторные функции и даже функции, определенные с помощью стрелки Кнута вверх обозначение (кроме случаев, когда используется индексированная стрелка вверх). Можно видеть , что примерно сопоставимо с в быстро растущей иерархии . Этот экстремальный рост может быть использован для демонстрации того, что очевидно вычислимо на машине с бесконечной памятью, такой как машина Тьюринга, и, следовательно, является вычислимой функцией.${\displaystyle f(n)=A(n,n)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle f(n)}$${\displaystyle f_{\omega }(n)}$${\displaystyle f}$, растет быстрее, чем любая примитивно-рекурсивная функция, и поэтому не является примитивно-рекурсивной.

В категории с экспонентами , используя изоморфизм (в информатике это называется каррированием ), функция Аккермана может быть определена с помощью примитивной рекурсии по функционалам более высокого порядка следующим образом:${\displaystyle ((X\times Y)\to Z)\cong (X\to (Y\to Z))}$

${\displaystyle {\begin{aligned}\operatorname {Ack} (0)&=\operatorname {S} \\\operatorname {Ack} (m+1)&=\operatorname {Iter} (\operatorname {Ack} (m))\end{aligned}}}$

где S ( n ) = n + 1 - обычная функция-последователь, а Iter обозначает функциональный оператор мощности , также определяемый примитивной рекурсией:

${\displaystyle {\begin{aligned}\operatorname {Iter} (f)(0)&=f(1)\\\operatorname {Iter} (f)(n+1)&=f(\operatorname {Iter} (f)(n))\end{aligned}}}$

Функция , определенная таким образом согласуется с функцией Ackermann , определенной выше: .${\displaystyle \mathrm {Ack} }$${\displaystyle A}$${\displaystyle \mathrm {Ack} (m)(n)=A(m,n)}$

Примеры расширений [ править ]

Чтобы увидеть, как функция Аккермана так быстро растет, полезно расширить некоторые простые выражения, используя правила из исходного определения. Например, полностью оценить можно так:${\displaystyle A(1,2)}$

${\displaystyle {\begin{aligned}A(1,2)&=A(0,A(1,1))\\&=A(0,A(0,A(1,0)))\\&=A(0,A(0,A(0,1)))\\&=A(0,A(0,2))\\&=A(0,3)\\&=4.\end{aligned}}}$

Чтобы продемонстрировать, как вычисления выполняются за много шагов и в большом количестве:${\displaystyle A(4,3)}$

${\displaystyle {\begin{aligned}A(4,3)&=A(3,A(4,2))\\&=A(3,A(3,A(4,1)))\\&=A(3,A(3,A(3,A(4,0))))\\&=A(3,A(3,A(3,A(3,1))))\\&=A(3,A(3,A(3,A(2,A(3,0)))))\\&=A(3,A(3,A(3,A(2,A(2,1)))))\\&=A(3,A(3,A(3,A(2,A(1,A(2,0))))))\\&=A(3,A(3,A(3,A(2,A(1,A(1,1))))))\\&=A(3,A(3,A(3,A(2,A(1,A(0,A(1,0)))))))\\&=A(3,A(3,A(3,A(2,A(1,A(0,A(0,1)))))))\\&=A(3,A(3,A(3,A(2,A(1,A(0,2))))))\\&=A(3,A(3,A(3,A(2,A(1,3)))))\\&=A(3,A(3,A(3,A(2,A(0,A(1,2))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(1,1)))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(1,0))))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(0,A(0,1))))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,A(0,2)))))))\\&=A(3,A(3,A(3,A(2,A(0,A(0,3))))))\\&=A(3,A(3,A(3,A(2,A(0,4)))))\\&=A(3,A(3,A(3,A(2,5))))\\&\qquad \vdots \\&=A(3,A(3,A(3,13)))\\&\qquad \vdots \\&=A(3,A(3,65533))\\&\qquad \vdots \\&=A(3,2^{65536}-3)\\&\qquad \vdots \\&=2^{2^{65536}}-3.\\\end{aligned}}}$

Таблица значений [ править ]

Вычисление функции Аккермана можно переформулировать в терминах бесконечной таблицы. Сначала разместите натуральные числа в верхнем ряду. Чтобы определить число в таблице, возьмите число сразу слева. Затем используйте это число, чтобы найти необходимое число в столбце, заданном этим числом, и на одну строку вверх. Если слева от него нет числа, просто посмотрите на столбец с заголовком «1» в предыдущей строке. Вот небольшая верхняя левая часть таблицы:

Значения A ( m ,  n )

п м	0	1	2	3	4	п
0	1	2	3	4	5	${\displaystyle n+1}$
1	2	3	4	5	6	${\displaystyle n+2=2+(n+3)-3}$
2	3	5	7	9	11	${\displaystyle 2n+3=2\cdot (n+3)-3}$
3	5	13	29	61	125	${\displaystyle 2^{(n+3)}-3}$
4	13 ${\displaystyle ={2^{2^{2}}}-3}$ ${\displaystyle =2\uparrow \uparrow 3-3}$	65533 ${\displaystyle ={2^{2^{2^{2}}}}-3}$ ${\displaystyle =2\uparrow \uparrow 4-3}$	2 65536  - 3 ${\displaystyle ={2^{2^{2^{2^{2}}}}}-3}$ ${\displaystyle =2\uparrow \uparrow 5-3}$	${\displaystyle {2^{2^{65536}}}-3}$ ${\displaystyle ={2^{2^{2^{2^{2^{2}}}}}}-3}$ ${\displaystyle =2\uparrow \uparrow 6-3}$	${\displaystyle {2^{2^{2^{65536}}}}-3}$ ${\displaystyle ={2^{2^{2^{2^{2^{2^{2}}}}}}}-3}$ ${\displaystyle =2\uparrow \uparrow 7-3}$	${\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} _{n+3}-3\end{matrix}}}$ ${\displaystyle =2\uparrow \uparrow (n+3)-3}$
5	65533 ${\displaystyle =2\uparrow \uparrow (2\uparrow \uparrow 2)-3}$ ${\displaystyle =2\uparrow \uparrow \uparrow 3-3}$	${\displaystyle 2\uparrow \uparrow \uparrow 4-3}$	${\displaystyle 2\uparrow \uparrow \uparrow 5-3}$	${\displaystyle 2\uparrow \uparrow \uparrow 6-3}$	${\displaystyle 2\uparrow \uparrow \uparrow 7-3}$	${\displaystyle 2\uparrow \uparrow \uparrow (n+3)-3}$
6	${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 3-3}$	${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 4-3}$	${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 5-3}$	${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 6-3}$	${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 7-3}$	${\displaystyle 2\uparrow \uparrow \uparrow \uparrow (n+3)-3}$
м	${\displaystyle (2\to 3\to (m-2))-3}$	${\displaystyle (2\to 4\to (m-2))-3}$	${\displaystyle (2\to 5\to (m-2))-3}$	${\displaystyle (2\to 6\to (m-2))-3}$	${\displaystyle (2\to 7\to (m-2))-3}$	${\displaystyle (2\to (n+3)\to (m-2))-3}$

Числа здесь, которые выражаются только с помощью рекурсивного возведения в степень или стрелок Кнута , очень большие и занимают слишком много места для записи в виде простых десятичных цифр.

Несмотря на большие значения, встречающиеся в этом раннем разделе таблицы, были определены некоторые даже большие числа, такие как число Грэма , которое нельзя записать с помощью небольшого количества стрелок Кнута. Это число строится с помощью техники, аналогичной рекурсивному применению функции Аккермана к самому себе.

Это повторение приведенной выше таблицы, но значения заменены соответствующим выражением из определения функции, чтобы четко показать шаблон:

Доказательство того, что функция Аккермана не является примитивно рекурсивной [ править ]

В некотором смысле функция Аккермана растет быстрее, чем любая примитивно рекурсивная функция, и поэтому сама по себе не является примитивно рекурсивной.

В частности, один показывает , что для каждой примитивно рекурсивной функции существует неотрицательное целое число , такое , что для всех неотрицательных целых чисел ,${\displaystyle f(x_{1},\ldots ,x_{n})}$${\displaystyle t}$${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle f(x_{1},\ldots ,x_{n})<A(t,\max _{i}x_{i}).}$

Как только это установлено, следует, что само по себе не является примитивно рекурсивным, поскольку в противном случае установка привела бы к противоречию${\displaystyle A}$${\displaystyle x_{1}=x_{2}=t}$${\displaystyle A(t,t)<A(t,t).}$

Доказательство ^[12] проводится следующим образом: определить класс всех функций, которые растут медленнее, чем функция Аккермана${\displaystyle {\mathcal {A}}}$

${\displaystyle {\mathcal {A}}=\left\{f\,{\bigg |}\,\exists t\ \forall x_{1}\cdots \forall x_{n}:\ f(x_{1},\ldots ,x_{n})<A(t,\max _{i}x_{i})\right\}}$

и показать, что содержит все примитивные рекурсивные функции. Последнее достигается путем демонстрации того, что он содержит постоянные функции, функцию-последователь, функции проекции и что он закрыт при операциях композиции функций и примитивной рекурсии.${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$

Обратите внимание, что отсутствие примитивной рекурсии не означает, что ее нельзя вычислить с помощью цикла for. ^[13]

Обратный [ править ]

Поскольку рассмотренная выше функция f ( n ) = A ( n , n ) растет очень быстро, ее обратная функция , f ⁻¹ , растет очень медленно. Эта обратная функция Аккермана f ⁻¹ обычно обозначается через α . Фактически, α ( n ) меньше 5 для любого практического входного размера n , поскольку A (4, 4) имеет порядок .  ${\displaystyle 2^{2^{2^{2^{16}}}}}$

Эта инверсия проявляется во временной сложности некоторых алгоритмов , таких как структура данных с непересекающимся набором данных и алгоритм Шазеля для минимальных остовных деревьев . Иногда в этих настройках используются исходная функция Аккермана или другие варианты, но все они растут с одинаково высокими темпами. В частности, некоторые модифицированные функции упрощают выражение, удаляя −3 и аналогичные члены.

Двухпараметрическая вариация обратной функции Аккермана может быть определена следующим образом, где - минимальная функция :${\displaystyle \lfloor x\rfloor }$

${\displaystyle \alpha (m,n)=\min\{i\geq 1:A(i,\lfloor m/n\rfloor )\geq \log _{2}n\}.}$

Эта функция возникает при более точном анализе упомянутых выше алгоритмов и дает более точные временные рамки. В структуре данных с непересекающимся набором m представляет количество операций, а n представляет количество элементов; в алгоритме минимального остовного дерева m представляет количество ребер, а n - количество вершин. Существует несколько немного разных определений α ( m , n ) ; например, log ₂ n иногда заменяется на n , а функция пола иногда заменяется потолком .

В других исследованиях может быть определена функция, обратная той, где m установлено на константу, так что обратная функция применяется к конкретной строке. ^[14]

Функция, обратная функции Аккермана, является примитивно рекурсивной. ^[15]

Использовать в качестве эталона [ править ]

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

Основополагающая статья Сандблада была подхвачена Брайаном Вичманном (соавтором теста Уетстона ) в трилогии статей, написанных между 1975 и 1982 годами ^{[18] [19] [20].}

См. Также [ править ]

• Теория вычислимости
• Двойная рекурсия
• Быстрорастущая иерархия
• Функция Гудштейна
• Примитивная рекурсивная функция
• Рекурсия (информатика)

Ссылки [ править ]

Библиография [ править ]

Внешние ссылки [ править ]

• «Функция Аккермана» . Энциклопедия математики . EMS Press . 2001 [1994].
• Вайсштейн, Эрик В. «Функция Аккермана» . MathWorld .
•  Эта статья включает материалы, являющиеся общественным достоянием  из  документа NIST :  Блэк, Пол Э. «Функция Аккермана» . Словарь алгоритмов и структур данных .
• Анимированный калькулятор функции Аккермана
• Функция Акермана, реализованная с помощью цикла for
• Скотт Ааронсон , кто может назвать самое большое число? (1999)
• Функции Аккермана . Включает таблицу некоторых значений.
• Гипероперации: функция Аккермана и новая арифметическая операция
• Большие номера Роберта Munafo в описывает несколько вариаций на определение A .
• Габриэль Ниваш, Обратный Аккерман без боли об обратной функции Аккермана.
• Раймунд Зайдель, Понимание обратной функции Аккермана (презентация в формате PDF).
• Функция Аккермана, написанная на разных языках программирования (на Rosetta Code )
• Функция Аккермана ( Архивировано 24 октября 2009 г.) - Некоторое исследование и программирование Гарри Дж. Смита.