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

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

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

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

История

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

${\ displaystyle {\ begin {align} \ varphi (m, n, 0) & = m + n \\\ varphi (m, n, 1) & = m \ times n \\\ varphi (m, n, 2 ) & = m ^ {n} \ end {выровнено}}}$

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

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

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

В О Infinite , Давид Гильберт выдвинул гипотезу о том , что функция Аккермана не примитивно рекурсивная, но это было Ackermann, Гильберта личный секретарь и бывший студент, который на самом деле доказал гипотезу в своей статье О построении Гильберта вещественных чисел .

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

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

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

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

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

${\ displaystyle {\ begin {align} \ OperatorName {F} (0, n) & = 2 [0] n = n + 1 \\\ Operatorname {F} (1, n) & = 2 [1] n = 2 + n \\\ имя оператора {F} (2, n) & = 2 [2] n = 2 \ times n \\\ имя оператора {F} (3, n) & = 2 [3] n = 2 ^ { n} \\\ имя оператора {F} (4, n) & = 2 [4] n = 2 ^ {2 ^ {2 ^ {{} ^ {. ^ {. ^ {{} _ {.} 2}} }}}} \\ & \ quad \ vdots \ end {align}}}$

Были исследованы многие другие версии функции Аккермана.

Определение

Как м-арная функция

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

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

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

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

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

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

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

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

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

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

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

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

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

Как итерированная 1-арная функция

Определим ф ^п как п -й итерации из F

${\ displaystyle {\ begin {array} {rll} f ^ {0} & = & \ operatorname {id} \\ f ^ {n + 1} & = & f \ circ f ^ {n}, \ end {array} }}$

где id - функция идентичности, а f ○ g обозначает композицию функции .

Представляя функцию Аккермана как последовательность унарных функций, можно установить . ${\ displaystyle \ operatorname {A} _ {m} (n) = \ operatorname {A} (m, n)}$

Затем функция становится последовательностью унарных функций, определенных на итерации : ${\ displaystyle \ operatorname {A} _ {0}, \ operatorname {A} _ {1}, \ operatorname {A} _ {2}, ...}$

${\ displaystyle {\ begin {array} {lcl} \ operatorname {A} _ {0} ^ {1} (n) & = & n + 1 \\\ operatorname {A} _ {m + 1} ^ {1} (n) & = & \ operatorname {A} _ {m} ^ {n + 1} (1) \\\ operatorname {A} _ {m} ^ {x + 2} (n) & = & \ operatorname { A} _ {m} ^ {1} (\ operatorname {A} _ {m} ^ {x + 1} (n)) \ end {array}}}$

В качестве функции состава ( е ○ г ) ( х ) = е ( г ( х )) является ассоциативной , последняя линия может также быть

${\ displaystyle {\ begin {array} {lcl} \ operatorname {A} _ {m} ^ {x + 2} (n) & = & \ operatorname {A} _ {m} ^ {x + 1} (\ имя оператора {A} _ {m} ^ {1} (n)) \ end {array}}}$

Вычисление

Рекурсивное определение функции Аккермана может быть естественно перенесено в систему переписывания терминов (TRS) .

TRS, основанный на 2-арной функции

Определение 2-арной (Петер-) функции Аккермана соответствует правилам редукции

${\ displaystyle {\ begin {array} {lll} {\ text {(r1)}} & A (0, n) & \ rightarrow & S (n) \\ {\ text {(r2)}} & A (S (m ), 0) & \ rightarrow & A (m, S (0)) \\ {\ text {(r3)}} & A (S (m), S (n)) & \ rightarrow & A (m, A (S ( m), n)) \ end {array}}}$

Пример

Вычислить ${\ Displaystyle А (1,2) \ rightarrow _ {*} 4}$

• Когда применяется стратегия крайнего левого угла (одношаговая) , последовательность сокращения имеет вид

${\ Displaystyle {\ begin {align} {\ underline {A (S (0), S (S (0)))}} & \ rightarrow _ {r3} {\ underline {A (0, A (S (0 ), S (0))}}) \\ & \ rightarrow _ {r1} S ({\ underline {A (S (0), S (0))}}) \\ & \ rightarrow _ {r3} S ({\ underline {A (0, A (S0,0))}}) \\ & \ rightarrow _ {r1} S (S ({\ underline {A (S (0), 0)}})) \ \ & \ rightarrow _ {r2} S (S ({\ underline {A (0, S (0))}})) \\ & \ rightarrow _ {r1} S (S (S (S (0))) ) \ конец {выровнено}}}$

• Когда применяется стратегия крайнего левого внутреннего (одношаговая) , последовательность сокращения имеет вид

${\ displaystyle {\ begin {align} {\ underline {A (S (0), S (S (0)))}} & \ rightarrow _ {r3} A (0, {\ underline {A (S (0) ), S (0))}}) \\ & \ rightarrow _ {r3} A (0, A (0, {\ underline {A (S (0), 0)}})) \\ & \ rightarrow _ {r2} A (0, A (0, {\ underline {A (0, S (0))}})) \\ & \ rightarrow _ {r1} A (0, {\ underline {A (0, S (S (0)))}}) \\ & \ rightarrow _ {r1} {\ underline {A (0, S (S (S (0))))}} \\ & \ rightarrow _ {r1} S (S (S (S (0)))) \ end {align}}}$

Для вычисления можно использовать стек , который изначально содержит элементы . ${\ Displaystyle \ OperatorName {A} (м, п)}$${\ Displaystyle \ langle м, п \ rangle}$

Затем повторно заменяют два верхних элемента согласно правилам

${\ displaystyle {\ begin {array} {lllllllll} {\ text {(r1)}} & 0 &, & n & \ rightarrow & (n + 1) \\ {\ text {(r2)}} & (m + 1) & , & 0 & \ rightarrow & m &, & 1 \\ {\ text {(r3)}} & (m + 1) &, & (n + 1) & \ rightarrow & m &, & (m + 1) &, & n \ end {array }}}$

Схематично, начиная с : ${\ Displaystyle \ langle м, п \ rangle}$

WHILE stackLength <> 1
{
   POP 2 elements;
   PUSH 1 to 3 elements in conformance with the rules r1, r2, r3
}

Псевдокод опубликован в Grossman & Zeitman (1988) .

Например, на входе последовательные конфигурации стека: ${\ Displaystyle \ langle 2,1 \ rangle}$

${\ displaystyle {\ begin {align} & {\ underline {2,1}} \ rightarrow 1, {\ underline {2,0}} \ rightarrow 1, {\ underline {1,1}} \ rightarrow 1,0 , {\ underline {1,0}} \ rightarrow 1,0, {\ underline {0,1}} \ rightarrow 1, {\ underline {0,2}} \ rightarrow \\ & {\ underline {1,3 }} \ rightarrow 0, {\ underline {1,2}} \ rightarrow 0,0, {\ underline {1,1}} \ rightarrow 0,0,0, {\ underline {1,0}} \ rightarrow 0 , 0,0, {\ underline {0,1}} \ rightarrow 0,0, {\ underline {0,2}} \ rightarrow \\ & 0, {\ underline {0,3}} \ rightarrow {\ underline { 0,4}} \ rightarrow 5. \ end {align}}}$

Это отражает последовательность редукции

${\ Displaystyle {\ begin {align} {\ underline {A (2,1)}} & \ rightarrow _ {r3} A (1, {\ underline {A (2,0)}}) \\ & \ rightarrow _ {r2} A (1, {\ underline {A (1,1)}}) \\ & \ rightarrow _ {r3} A (1, A (0, {\ underline {A (1,0)}} )) \\ & \ rightarrow _ {r2} A (1, A (0, {\ underline {A (0,1)}})) \\ & \ rightarrow _ {r1} A (1, {\ underline { A (0,2)}}) \\ & \ rightarrow _ {r1} {\ underline {A (1,3)}} \\ & \ rightarrow _ {r3} A (0, {\ underline {A (1 , 2)}}) \\ & \ rightarrow _ {r3} A (0, A (0, {\ underline {A (1,1)}})) \\ & \ rightarrow _ {r3} A (0, A (0, A (0, {\ underline {A (1,0)}}))) \\ & \ rightarrow _ {r2} A (0, A (0, A (0, {\ underline {A ( 0,1)}}))) \\ & \ rightarrow _ {r1} A (0, A (0, {\ underline {A (0,2)}})) \\ & \ rightarrow _ {r1} A (0, {\ underline {A (0,3)}}) \\ & \ rightarrow _ {r1} {\ underline {A (0,4)}} \\ & \ rightarrow _ {r1} 5 \ end { выровнено}}}$

Замечания

• Самая левая-самая внутренняя стратегия реализована на 225 компьютерных языках в Rosetta Code .
• Гроссман и Zeitman (1988) указывал, что при вычислении длины максимальной из стека , пока .${\ Displaystyle \ OperatorName {A} (я, п)}$${\ Displaystyle \ OperatorName {A} (я, п)}$${\ displaystyle i> 0}$

TRS, основанный на повторяющейся 1-арной функции

Определение повторяющихся одномерных функций Аккермана приводит к различным правилам редукции

${\ displaystyle {\ begin {array} {lll} {\ text {(r4)}} & A (S (0), 0, n) & \ rightarrow & S (n) \\ {\ text {(r5)}} & A (S (0), S (m), n) & \ rightarrow & A (S (n), m, S (0)) \\ {\ text {(r6)}} & A (S (S (x) ), m, n) & \ rightarrow & A (S (0), m, A (S (x), m, n)) \ end {array}}}$

Поскольку композиция функций ассоциативна, вместо правила r6 можно определить

${\ displaystyle {\ begin {array} {lll} {\ text {(r7)}} & A (S (S (x)), m, n) & \ rightarrow & A (S (x), m, A (S (0), m, n)) \ end {array}}}$

Как и в предыдущем разделе, вычисление может быть реализовано с помощью стека, который поддерживает текущий член. ${\ displaystyle \ operatorname {A} _ {m} ^ {1} (n)}$

Первоначально стек содержит три элемента . ${\ Displaystyle \ langle 1, м, п \ rangle}$

Затем повторно три верхних элемента заменяются согласно правилам

${\ displaystyle {\ begin {array} {lllllllll} {\ text {(r4)}} & 1 &, 0 &, n & \ rightarrow & (n + 1) \\ {\ text {(r5)}} & 1 &, (m + 1) &, n & \ rightarrow & (n + 1) &, m &, 1 \\ {\ text {(r6)}} & (x + 2) &, m &, n & \ rightarrow & 1 &, m &, (x + 1 ) &, m &, n \\\ end {массив}}}$

Схематично, начиная с : ${\ Displaystyle \ langle 1, м, п \ rangle}$

WHILE stackLength <> 1
{
   POP 3 elements;
   PUSH 1 or 3 or 5 elements in conformance with the rules r4, r5, r6;
}

Пример

На входе последовательные конфигурации стека ${\ Displaystyle \ langle 1,2,1 \ rangle}$

${\ displaystyle {\ begin {align} & {\ underline {1,2,1}} \ rightarrow _ {r5} {\ underline {2,1,1}} \ rightarrow _ {r6} 1,1, {\ подчеркивание {1,1,1}} \ rightarrow _ {r5} 1,1, {\ underline {2,0,1}} \ rightarrow _ {r6} 1,1,1,0, {\ underline {1, 0,1}} \\ & \ rightarrow _ {r4} 1,1, {\ underline {1,0,2}} \ rightarrow _ {r4} {\ underline {1,1,3}} \ rightarrow _ { r5} {\ underline {4,0,1}} \ rightarrow _ {r6} 1,0, {\ underline {3,0,1}} \ rightarrow _ {r6} 1,0,1,0, {\ подчеркивание {2,0,1}} \\ & \ rightarrow _ {r6} 1,0,1,0,1,0, {\ underline {1,0,1}} \ rightarrow _ {r4} 1,0 , 1,0, {\ underline {1,0,2}} \ rightarrow _ {r4} 1,0, {\ underline {1,0,3}} \ rightarrow _ {r4} {\ underline {1,0 , 4}} \ rightarrow _ {r4} 5 \ end {align}}}$

Соответствующие равенства имеют вид

${\ displaystyle {\ begin {align} & A_ {2} ^ {1} (1) = A_ {1} ^ {2} (1) = A_ {1} ^ {1} (A_ {1} ^ {1} (1)) = A_ {1} ^ {1} (A_ {0} ^ {2} (1)) = A_ {1} ^ {1} (A_ {0} ^ {1} (A_ {0} ^ {1} (1))) \\ & = A_ {1} ^ {1} (A_ {0} ^ {1} (2)) = A_ {1} ^ {1} (3) = A_ {0} ^ {4} (1) = A_ {0} ^ {1} (A_ {0} ^ {3} (1)) = A_ {0} ^ {1} (A_ {0} ^ {1} (A_ { 0} ^ {2} (1))) \\ & = A_ {0} ^ {1} (A_ {0} ^ {1} (A_ {0} ^ {1} (A_ {0} ^ {1}) (1)))) = A_ {0} ^ {1} (A_ {0} ^ {1} (A_ {0} ^ {1} (2))) = A_ {0} ^ {1} (A_ { 0} ^ {1} (3)) = A_ {0} ^ {1} (4) = 5 \ end {выровнено}}}$

При использовании правила сокращения r7 вместо r6, замены в стеке будут следовать

${\ displaystyle {\ begin {array} {lllllllll} {\ text {(r7)}} & (x + 2) &, m &, n & \ rightarrow & (x + 1) &, m &, 1 &, m &, n \ конец {массив}}}$

Последовательные конфигурации стека будут

${\ displaystyle {\ begin {align} & {\ underline {1,2,1}} \ rightarrow _ {r5} {\ underline {2,1,1}} \ rightarrow _ {r7} 1,1, {\ подчеркивание {1,1,1}} \ rightarrow _ {r5} 1,1, {\ underline {2,0,1}} \ rightarrow _ {r7} 1,1,1,0, {\ underline {1, 0,1}} \\ & \ rightarrow _ {r4} 1,1, {\ underline {1,0,2}} \ rightarrow _ {r4} {\ underline {1,1,3}} \ rightarrow _ { r5} {\ underline {4,0,1}} \ rightarrow _ {r7} 3,0, {\ underline {1,0,1}} \ rightarrow _ {r4} {\ underline {3,0,2} } \\ & \ rightarrow _ {r7} 2,0, {\ underline {1,0,2}} \ rightarrow _ {r4} {\ underline {2,0,3}} \ rightarrow _ {r7} 1, 0, {\ underline {1,0,3}} \ rightarrow _ {r4} {\ underline {1,0,4}} \ rightarrow _ {r4} 5 \ end {align}}}$

Соответствующие равенства имеют вид

${\ displaystyle {\ begin {align} & A_ {2} ^ {1} (1) = A_ {1} ^ {2} (1) = A_ {1} ^ {1} (A_ {1} ^ {1} (1)) = A_ {1} ^ {1} (A_ {0} ^ {2} (1)) = A_ {1} ^ {1} (A_ {0} ^ {1} (A_ {0} ^ {1} (1))) \\ & = A_ {1} ^ {1} (A_ {0} ^ {1} (2)) = A_ {1} ^ {1} (3) = A_ {0} ^ {4} (1) = A_ {0} ^ {3} (A_ {0} ^ {1} (1)) = A_ {0} ^ {3} (2) \\ & = A_ {0} ^ {2} (A_ {0} ^ {1} (2)) = A_ {0} ^ {2} (3) = A_ {0} ^ {1} (A_ {0} ^ {1} (3)) = A_ {0} ^ {1} (4) = 5 \ end {выровнено}}}$

Замечания

• На любом заданном входе все TRS, представленные выше, сходятся за одинаковое количество шагов. Они также используют те же правила редукции (в этом сравнении правила r1, r2, r3 считаются «такими же, как» правила r4, r5, r6 / 7 соответственно). Например, редукция сходится за 14 шагов: 6 X r1, 3 X r2, 5 X r3. Уменьшение также сходится в 14 шагов: 6 X r4, 3 X r5, 5 X r6 / 7. TRS различаются порядком применения правил сокращения.${\ Displaystyle А (2,1)}$${\ Displaystyle A_ {2} ^ {1} (1)}$

• При вычислении по правилам r4, r5, r6 максимальная длина стека остается ниже 2 * . Когда вместо правила r6 используется правило сокращения r7, максимальная длина стека становится меньше 2 (i + 2). Длина стека отражает глубину рекурсии. Поскольку вычисление в соответствии с правилами r4, r5, r7 включает наименьшую максимальную глубину рекурсии, наблюдаемую до сих пор, это эффективно в этом отношении.${\ displaystyle \ operatorname {A} _ {i} ^ {1} (n)}$${\ Displaystyle \ OperatorName {A} (я, п)}$

• Гроссман и Зейтман (1988) опубликовали по своей сути итеративный алгоритм, который работает быстрее.

Огромные числа

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

${\ Displaystyle {\ begin {align} A (4,3) & \ rightarrow A (3, A (4,2)) \\ & \ rightarrow A (3, A (3, A (4,1))) \\ & \ rightarrow A (3, A (3, A (3, A (4,0)))) \\ & \ rightarrow A (3, A (3, A (3, A (3,1)) )) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (3,0))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (2,1))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (1, A (2,0)))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (1, A (1,1)))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (1, A (0, A (1,0))))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A ( 1, A (0, A (0,1))))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (1, A (0,2))) )))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (1,3))))) \\ & \ rightarrow A (3, A (3, A ( 3, A (2, A (0, A (1,2)))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (0, A (0, A (1,1))))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A) (0, A (0, A (0, A (1,0 )))))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (0, A (0, 0, A (0, A (0,1)))) )))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (0, A (0, A (0,2))))))) \\ & \ rightarrow A (3, A (3, A (3, A (2, A (0, A (0,3)))))) \\ & \ rightarrow A (3, A (3, A (3, A ( 2, A (0,4))))) \\ & \ rightarrow A (3, A (3, A (3, A (2,5)))) \\ & \ qquad \ vdots \\ & \ rightarrow A (3, A (3, A (3,13))) \\ & \ qquad \ vdots \\ & \ rightarrow A (3, A (3,6 5533)) \\ & \ qquad \ vdots \\ & \ rightarrow A (3,2 ^ {65536} -3) \\ & \ qquad \ vdots \\ & \ rightarrow 2 ^ {2 ^ {65536}} - 3 . \\\ конец {выровнен}}}$

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

Вычисление функции Аккермана можно переформулировать в терминах бесконечной таблицы. Сначала разместите натуральные числа в верхнем ряду. Чтобы определить число в таблице, возьмите число сразу слева. Затем используйте это число, чтобы найти необходимое число в столбце, заданном этим числом, и на одну строку вверх. Если слева от него нет числа, просто посмотрите на столбец с заголовком «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 п + 2 = 2 + (п + 3) -3}$
2	3	5	7	9	11	${\ Displaystyle 2n + 3 = 2 \ cdot (п + 3) -3}$
3	5	13	29	61	125	${\ Displaystyle 2 ^ {(п + 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 \ вверх \ вверх \ вверх \ вверх (п + 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 \ вверх \ вверх \ вверх \ вверх \ вверх (п + 3) -3}$
м	${\ Displaystyle (2 \ к 3 \ к (м-2)) - 3}$	${\ Displaystyle (2 \ к 4 \ к (м-2)) - 3}$	${\ Displaystyle (от 2 \ до 5 \ к (м-2)) - 3}$	${\ Displaystyle (от 2 \ до 6 \ к (м-2)) - 3}$	${\ Displaystyle (от 2 \ до 7 \ к (м-2)) - 3}$	${\ Displaystyle (2 \ к (п + 3) \ к (м-2)) - 3}$

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

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

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

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

п м	0	1	2	3	4	п
0	0 + 1	1 + 1	2 + 1	3 + 1	4 + 1	п + 1
1	А (0, 1)	А (0, А (1, 0)) = А (0, 2)	А (0, А (1, 1)) = А (0, 3)	А (0, А (1, 2)) = А (0, 4)	А (0, А (1, 3)) = А (0, 5)	А (0, А (1, n −1))
2	А (1, 1)	А (1, А (2, 0)) = А (1, 3)	А (1, А (2, 1)) = А (1, 5)	А (1, А (2, 2)) = А (1, 7)	А (1, А (2, 3)) = А (1, 9)	А (1, А (2, n −1))
3	А (2, 1)	А (2, А (3, 0)) = А (2, 5)	А (2, А (3, 1)) = А (2, 13)	А (2, А (3, 2)) = А (2, 29)	А (2, А (3, 3)) = А (2, 61)	A (2, A (3, n −1))
4	А (3, 1)	А (3, А (4, 0)) = А (3, 13)	А (3, А (4, 1)) = А (3, 65533)	А (3, А (4, 2))	А (3, А (4, 3))	A (3, A (4, n −1))
5	А (4, 1)	А (4, А (5, 0))	А (4, А (5, 1))	А (4, А (5, 2))	А (4, А (5, 3))	А (4, А (5, n −1))
6	А (5, 1)	А (5, А (6, 0))	А (5, А (6, 1))	А (5, А (6, 2))	А (5, А (6, 3))	А (5, А (6, n −1))

Характеристики

Основные пометки

• Может быть не сразу очевидно, что оценка всегда завершается. Однако рекурсия ограничена, потому что в каждом рекурсивном приложении либо уменьшается, либо остается прежним и уменьшается. Каждый раз, когда он достигает нуля, уменьшается, так что в конечном итоге тоже достигает нуля. (Выражаясь более технически, в каждом случае пара уменьшается в лексикографическом порядке по парам, что является хорошим упорядочением , точно так же, как упорядочение отдельных неотрицательных целых чисел; это означает, что нельзя идти вниз в упорядочении бесконечно много раз подряд. .) Однако при уменьшении нет верхней границы того, насколько может увеличиться - и он часто будет значительно увеличиваться.${\ Displaystyle А (м, п)}$${\ displaystyle m}$${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle m}$${\ Displaystyle (м, п)}$${\ displaystyle m}$${\ displaystyle n}$
• Для малых значений m, таких как 1, 2 или 3, функция Аккермана растет относительно медленно по отношению к n (не более чем экспоненциально ). Для , однако, он растет гораздо быстрее; даже составляет примерно 2 × 10 ^{19 728} , а десятичное разложение A (4, 3) очень велико по любым типичным меркам.${\ displaystyle m \ geq 4}$${\ Displaystyle А (4,2)}$
• Интересный аспект заключается в том, что единственная арифметическая операция, которую он когда-либо использует, - это сложение 1. Его быстрорастущие возможности основаны исключительно на вложенной рекурсии. Это также означает, что время его работы, по крайней мере, пропорционально его производительности, и поэтому оно также чрезвычайно велико. На самом деле, в большинстве случаев время работы намного больше, чем результат; см. ниже.
• Версия с одним аргументом, которая увеличивает обе и в то же время затмевает каждую примитивную рекурсивную функцию, включая очень быстрорастущие функции, такие как экспоненциальная функция , факториальная функция, много- и сверхфакторные функции и даже функции, определенные с помощью стрелки Кнута вверх обозначение (кроме случаев, когда используется индексированная стрелка вверх). Можно видеть , что примерно сопоставимо с в быстро растущей иерархии . Этот экстремальный рост может быть использован для демонстрации того, что очевидно вычислимо на машине с бесконечной памятью, такой как машина Тьюринга, и, следовательно, является вычислимой функцией , растет быстрее, чем любая примитивно рекурсивная функция, и, следовательно, не является примитивно рекурсивной.${\ Displaystyle е (п) = А (п, п)}$${\ displaystyle m}$${\ displaystyle n}$${\ Displaystyle f (п)}$${\ displaystyle f _ {\ omega} (п)}$${\ displaystyle f}$

Не примитивно рекурсивный

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

В частности, один показывает , что для каждой примитивно рекурсивной функции существует неотрицательное целое число , такое , что для всех неотрицательных целых чисел , ${\ 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 А (т, т) <А (т, т).}$

Доказательство проводится следующим образом: определите класс всех функций, которые растут медленнее, чем функция Аккермана. ${\ 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 установлено на константу, так что обратная функция применяется к конкретной строке.

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

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

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

Основополагающая статья Сандблада была подхвачена Брайаном Вичманном (соавтором теста Whetstone ) в трилогии статей, написанных между 1975 и 1982 годами.

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

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

Примечания

использованная литература

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

внешние ссылки

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