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

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

${displaystyle {egin {array} {lcl} operatorname {A} (0, n) & = & n + 1 operatorname {A} (m + 1,0) & = & operatorname {A} (m, 1) operatorname { A} (m + 1, n + 1) & = & имя оператора {A} (m, имя оператора {A} (m + 1, n)) end {array}}}$

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

История

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

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

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

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

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

${displaystyle varphi (m, n, 3) = m [4] (n + 1) ,,!}$

${displaystyle varphi (m, n, p) gtrapprox m [p + 1] (n + 1) {ext {, for}} p> 3.,!}$

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

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

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

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

В 1963 г. R.C. Бак основанный на интуитивно понятном варианте с двумя переменными (F^[10]) на последовательность гиперопераций:^[11]

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

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

${displaystyle {egin {array} {lr} 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 раза n operatorname {F} (3, n) = 2 [3] n = 2 ^ {n} operatorname {F} (4, n ) = 2 [4] n = 2 ^ {2 ^ {2 ^ {{} ^ {., ^ {., ^ {., ^ {2}}}}}}} ... конец {массив}} }$

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

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

${displaystyle {egin {array} {lr} varphi (m, n, 0) = m + n varphi (m, 0,1) = 0 varphi (m, 0,2) = 1 varphi (m, 0 , p) = m {ext {for}} p> 2 varphi (m, n, p) = varphi (m, varphi (m, n-1, p), p-1) {ext {for}} n > 0 {ext {and}} p> 0.end {array}}}$

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

${displaystyle {egin {array} {lcl} operatorname {A} (0, n) & = & n + 1 operatorname {A} (m + 1,0) & = & operatorname {A} (m, 1) operatorname { A} (m + 1, n + 1) & = & operatorname {A} (m, A (m + 1, n)) end {array}}}$

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

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

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

${displaystyle A (m, n) = {egin {case} 0 [m] n & {ext {, if}} m = 0 2 [m] (n + 3) -3 & {ext {, if}} m> 0 end {case}}}$

• гипероперация, представленные в Обозначение Кнута со стрелкой вверх (расширено до целочисленных индексов ≥ −2):

${displaystyle A (m, n) = {egin {cases} 0uparrow ^ {m-2} n & {ext {, if}} m = 0 2uparrow ^ {m-2} (n + 3) -3 & {ext { , если}} m> 0 end {case}}}$

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

${displaystyle A (m, n) = (2ightarrow (n + 3) ightarrow (m-2)) - 3}$ за ${displaystyle mgeq 3}$

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

${displaystyle 2ightarrow nightarrow m = A (m + 2, n-3) +3}$ за ${displaystyle n> 2}$.

(п = 1 и п = 2 будет соответствовать А(м, −2) = −1 и А(м, −1) = 1, которые логично можно было бы добавить.)

Для малых значений м как 1, 2 или 3, функция Аккермана растет относительно медленно относительно п (в большинстве экспоненциально). За м ≥ 4однако растет гораздо быстрее; четное А(4, 2) около 2×10¹⁹⁷²⁸, и десятичное разложение А(4, 3) очень велика по любым типичным меркам.

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

Версия с одним аргументом ж(п) = А(п, п) что увеличивает оба м и п в то же время затмевает каждую примитивную рекурсивную функцию, включая очень быстрорастущие функции, такие как экспоненциальная функция, факториальная функция, много- и сверхфакторный функции и даже функции, определенные с использованием нотации Кнута со стрелкой вверх (кроме случаев, когда используется индексированная стрелка вверх). Видно, что ж(п) примерно сопоставимо с ж_ω(п) в быстрорастущая иерархия. Этот экстремальный рост можно использовать, чтобы показать, что ж, который, очевидно, вычислим на машине с бесконечной памятью, такой как Машина Тьюринга и так вычислимая функция, растет быстрее, чем любая примитивно рекурсивная функция, и поэтому не является примитивно рекурсивной.

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

${displaystyle {egin {array} {lcl} operatorname {Ack} (0) & = & operatorname {S} operatorname {Ack} (m + 1) & = & operatorname {Iter} (operatorname {Ack} (m)) end { множество}}}$

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

${displaystyle {egin {array} {lcl} operatorname {Iter} (f) (0) & = & f (1) operatorname {Iter} (f) (n + 1) & = & f (operatorname {Iter} (f) (n)). конец {массив}}}$

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

Количество рекурсий до возвращения Аккермана (3,3)

Примеры расширений

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

${displaystyle {egin {выровнено} 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 {выровнено}}}$

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

${displaystyle {egin {выровнено} 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, А (0, А (0, А (0, А (1,0)))))))) & = А (3, А (3, А (3, А (2, А (0, А (0, А (0, А (0,1))))))) & = А (3, А (3, А (3, А (2, А (0, А (0, А ( 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)))) & = ldots & = A (3, A (3, A (3,13))) & = ldots & = A (3, A (3,65533)) & = ldots & = A (3,2 ^ {65536} -3) & = ldots & = 2 ^ {2 ^ {overset {65536} {}}} - 3. end {align}}}$

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

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

Ценности А(м, п)

п м	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 = 2cdot (n + 3) -3}$
3	5	13	29	61	125	${displaystyle 2 ^ {(n + 3)} - 3}$
4	13 ${displaystyle = {2 ^ {2 ^ {2}}} - 3}$ ${displaystyle = 2uparrow uparrow 3–3}$	65533 ${displaystyle = {2 ^ {2 ^ {2 ^ {2}}}} - 3}$ ${displaystyle = 2uparrow uparrow 4–3}$	265536 − 3 ${displaystyle = {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}} - 3}$ ${displaystyle = 2uparrow uparrow 5–3}$	${displaystyle {2 ^ {2 ^ {65536}}} - 3}$ ${displaystyle = {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}}} - 3}$ ${displaystyle = 2uparrow uparrow 6–3}$	${displaystyle {2 ^ {2 ^ {2 ^ {65536}}}} - 3}$ ${displaystyle = {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}}}} - 3}$ ${displaystyle = 2uparrow uparrow 7-3}$	${displaystyle {egin {matrix} underbrace {{2 ^ {2}} ^ {{cdot} ^ {{cdot} ^ {{cdot} ^ {2}}}}} _ {n + 3} -3end {matrix}) }}$ ${displaystyle = 2uparrow uparrow (n + 3) -3}$
5	65533 ${displaystyle = 2uparrow uparrow (2uparrow uparrow 2) -3}$ ${displaystyle = 2uparrow uparrow uparrow 3–3}$	${displaystyle 2uparrow uparrow uparrow 4-3}$	${displaystyle 2uparrow uparrow uparrow 5-3}$	${displaystyle 2uparrow uparrow uparrow 6-3}$	${displaystyle 2uparrow uparrow uparrow 7-3}$	${displaystyle 2uparrow uparrow uparrow (n + 3) -3}$
6	${displaystyle 2uparrow uparrow uparrow uparrow 3–3}$	${displaystyle 2uparrow uparrow uparrow uparrow 4–3}$	${displaystyle 2uparrow uparrow uparrow uparrow 5-3}$	${displaystyle 2uparrow uparrow uparrow uparrow 6-3}$	${displaystyle 2uparrow uparrow uparrow uparrow 7-3}$	${displaystyle 2uparrow uparrow uparrow uparrow (n + 3) -3}$
м	${displaystyle (2ightarrow (3) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (4) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (5) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (6) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (7) ightarrow (m-2)) - 3}$	${displaystyle (2ightarrow (n + 3) ightarrow (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})$

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

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

${displaystyle {mathcal {A}} = left {fmid exists t forall x_ {1} cdots forall x_ {n}: f (x_ {1}, ldots, x_ {n})$

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

Обратный

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

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

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

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

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

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

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

Использовать как эталон

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

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

Смотрите также

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

Рекомендации

Библиография

внешняя ссылка

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