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

В теории вычислимости , то функция Аккермана , названная в честь Вильгельма Аккермана , является одним из самых простых ^[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 году, Аккерман опубликовал свою функцию (греческая буква фи ). Функция трех аргументов Аккермана определена так, что для p${\displaystyle \varphi }$${\displaystyle \varphi (m,n,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 году Р. К. Бак основал интуитивно понятный вариант с двумя переменными (F ^[10] ) на последовательности гиперопераций : ^[11]

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

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

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

Из различных версий с двумя аргументами вариант, разработанный Петером и Робинсоном (называемый некоторыми авторами «функцией Аккермана»), определен для неотрицательных целых чисел 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}}}$

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

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

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

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

• гипероперация , представленная в нотации Кнута со стрелкой вверх (расширенная до целочисленных индексов ≥ −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}}}$

( n = 1 и n = 2 соответствовали бы A ( m , −2) = −1 и A ( m , −1) = 1 , которые можно было бы логически сложить.)

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

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

Версия с одним аргументом f ( n ) = A ( n , n ), которая увеличивает как m, так и n одновременно, затмевает любую примитивную рекурсивную функцию, включая очень быстрорастущие функции, такие как экспоненциальная функция , факториальная функция, многозначная функция. и суперфакторные функции, и даже функции, определенные с использованием нотации Кнута со стрелкой вверх (кроме случаев, когда используется индексированная стрелка вверх). Видно, что f ( n ) примерно сравнимо с f _ω ( n ) в быстрорастущей иерархии. Этот экстремальный рост можно использовать, чтобы показать, что 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}}}$

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

Поскольку рассмотренная выше функция 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 установлено на константу, так что обратная функция применяется к конкретной строке. ^[13]

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

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

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

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

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

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

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

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

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

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