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

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

${displaystyle {egin{array}{lcl}operatorname {A} (0,n)&=&n+1operatorname {A} (m+1,0)&=&operatorname {A} (m,1)operatorname {A} (m+1,n+1)&=&operatorname {A} (m,operatorname {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+1operatorname {F} (1,n)=2[1]n=2+noperatorname {F} (2,n)=2[2]n=2 imes noperatorname {F} (3,n)=2[3]n=2^{n}operatorname {F} (4,n)=2[4]n=2^{2^{2^{{}^{.,^{.,^{.,^{2}}}}}}}...end{array}}}$

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

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

${displaystyle {egin{array}{lr}varphi (m,n,0)=m+nvarphi (m,0,1)=0varphi (m,0,2)=1varphi (m,0,p)=m{ ext{ for }}p>2varphi (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+1operatorname {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{cases}0[m]n&{ ext{, if }}m=02[m](n+3)-3&{ ext{, if }}m>0end{cases}}}$

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

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

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

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

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

${displaystyle {egin{array}{lcl}operatorname {Iter} (f)(0)&=&f(1)operatorname {Iter} (f)(n+1)&=&f(operatorname {Iter} (f)(n)).end{array}}}$

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

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

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

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

${displaystyle {egin{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 {egin{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))))&=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{aligned}}}$

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

Вычисление функции Аккермана можно переформулировать в терминах бесконечной таблицы. Сначала разместите натуральные числа в верхнем ряду. Чтобы определить число в таблице, возьмите число сразу слева. Затем используйте это число, чтобы найти необходимое число в столбце, заданном этим числом, и на одну строку вверх. Если слева от него нет числа, просто посмотрите на столбец с заголовком «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}$	2^65536 − 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}$

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

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

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

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

п м	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, п−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, п−1))
3	А(2, 1)	А(2, А(3, 0)) = А(2, 5)	А(2, А(3, 1)) = А(2, 13)	А(2, А(3, 2)) = А(2, 29)	А(2, А(3, 3)) = А(2, 61)	А(2, А(3, п−1))
4	А(3, 1)	А(3, А(4, 0)) = А(3, 13)	А(3, А(4, 1)) = А(3, 65533)	А(3, А(4, 2))	А(3, А(4, 3))	А(3, А(4, п−1))
5	А(4, 1)	А(4, А(5, 0))	А(4, А(5, 1))	А(4, А(5, 2))	А(4, А(5, 3))	А(4, А(5, п−1))
6	А(5, 1)	А(5, А(6, 0))	А(5, А(6, 1))	А(5, А(6, 2))	А(5, А(6, 3))	А(5, А(6, п−1))

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

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

В частности, показано, что каждой примитивной рекурсивной функции ${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{fmid exists t forall x_{1}cdots forall x_{n}: f(x_{1},ldots ,x_{n})<A(t,max _{i}x_{i})ight}}$

и показать, что ${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]

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

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

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

1. Монин и Хинчи 2003, п. 61.
2. Акерманн 1928 г..
3. "Десятичное разложение A (4,2)". kosara.net. 27 августа 2000 г. Архивировано с оригинал 20 января 2010 г.
4. Калуд, Маркус и Теви, 1979.
5. Гильберт 1926, п. 185.
6. ван Хейеноорт 1967.
7. Петер 1935.
8. Робинсон 1948.
9. Ричи 1965, п. 1028.
10. с обратным порядком параметров
11. Бак 1963.
12. Ву, Чи (17 декабря 2009 г.). «Функция Аккермана не является примитивно рекурсивной | planetmath.org». planetmath.org. Архивировано из оригинал на 2013-05-09.
13. Петти 2002.
14. Матос 2014.
15. Вайда 1970.
16. Сундблад 1971.
17. Wichmann 1976.
18. Wichmann 1977.
19. Wichmann 1982.

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

• Акерманн, Вильгельм (1928). "Zum Hilbertschen Aufbau der reellen Zahlen". Mathematische Annalen. 99: 118–133. Дои:10.1007 / BF01459088.
• Бак, Р. (1963). «Математическая индукция и рекурсивные определения». Американский математический ежемесячный журнал. 70 (2): 128–135. Дои:10.2307/2312881.
• Калуд, Кристиан; Маркус, Соломон; Теви, Ионел (ноябрь 1979 г.). «Первый пример рекурсивной функции, которая не является примитивно рекурсивной». Historia Math. 6 (4): 380–84. Дои:10.1016/0315-0860(79)90024-7.
• ван Хейеноорт, Жан (1967). От Фреге до Гёделя: Справочник по математической логике, 1879–1931 гг.. Издательство Гарвардского университета.
• Гильберт, Дэвид (1926). "Über das Unendliche". Mathematische Annalen. 95: 161–190. Дои:10.1007 / BF01206605.
• Матос, Армандо Б. (7 мая 2014 г.). «Обратная функция Аккермана примитивно рекурсивна» (PDF).
• Монен, Жан-Франсуа; Хинчи, М. Г. (2003). Понимание формальных методов. Springer. п. 61. ISBN  9781852332471.
• Петер, Рожа (1935). "Конструкция ничтрекурсивер Функционен". Mathematische Annalen. 111: 42–60. Дои:10.1007 / BF01472200.
• Петти, С. (2002). «Нижняя граница в стиле обратного Аккермана для онлайн-задачи проверки минимального остовного дерева». 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г. Материалы: 155–163. Дои:10.1109 / SFCS.2002.1181892.
• Ричи, Роберт Уэллс (ноябрь 1965 г.). «Классы рекурсивных функций на основе функции Аккермана». Тихоокеанский математический журнал. 15 (3): 1027–1044. Дои:10.2140 / pjm.1965.15.1027.
• Робинсон, Рафаэль М. (1948). «Рекурсия и двойная рекурсия». Бюллетень Американского математического общества. 54 (10): 987–93. Дои:10.1090 / S0002-9904-1948-09121-2.
• Сундблад, Ингве (март 1971 г.). «Функция Аккермана. Теоретические, вычислительные и манипулятивные исследования формул». BIT вычислительная математика. 11 (1): 107–119. Дои:10.1007 / BF01935330.
• Вайда, Драгонь (1970). «Проверка компилятора для языка, подобного алгоритму». Bulletin Mathématique de la Société des Sciences Mathématiques de la République Socialiste de Roumanie, Nouvelle Série. 14 (60) (4): 487–502. JSTOR  43679758.
• Вичманн, Брайан А. (март 1976 г.). «Функция Аккермана: исследование эффективности вызывающих процедур». BIT вычислительная математика. 16: 103–110. Дои:10.1007 / BF01940783.
• Вичманн, Брайан А. (июль 1977 г.). «Как вызывать процедуры, или размышления о функции Аккермана». BIT вычислительная математика. 16: 103–110. Дои:10.1002 / spe.4380070303.
• Вичманн, Брайан А. (июль 1982 г.). «Последние результаты теста вызова процедуры, функция Аккермана» (PDF).

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

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