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

Эта статья о математической функции. Чтобы узнать о других значениях, см. Акерманн (значения) .

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

После публикации Аккермана его функции (которая имела три неотрицательных целых аргумента) многие авторы модифицировали ее для различных целей, так что сегодня «функция Аккермана» может относиться к любому из многочисленных вариантов исходной функции. с двумя аргументами, Одной из распространенных версий является функция Аккермана–Петера разработанная Рожа Петер и Рафаэлем Робинсоном . Его стоимость растет очень быстро; например, $\operatorname {A} (4,2)$ приводит к $2^{65536}-3$, целое число из 19 729 десятичных цифр.

История

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

${\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 эти базовые операции расширяются таким образом, что их можно сравнить с гипероперациями :

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

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

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

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

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

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

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

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

${\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-арная функция

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

${\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$ следующее:

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

Функция Аккермана также была выражена в отношении последовательности гиперопераций :

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

или, записанное в обозначении Кнута, направленном вверх (расширенное до целочисленных индексов $\geq -2$):

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

или, что то же самое, через функцию Бака F:

$={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}$

Определение: как итерированная 1-арная функция

Определять $f^{n}$ как n -я итерация $f$:

${\begin{array}{rll}f^{0}(x)&=&x\\f^{n+1}(x)&=&f(f^{n}(x))\end{array}}$

Итерация — это процесс составления функции из самой себя определенное количество раз. Композиция функций является ассоциативной операцией, поэтому $f(f^{n}(x))=f^{n}(f(x))$.

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

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

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

Вычисление

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

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

Определение 2-арной функции Аккермана приводит к очевидным правилам редукции

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

Пример

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

Последовательность сокращения

Крайняя левая-крайняя (одношаговая) стратегия :	Самая левая-внутренняя (одношаговая) стратегия :
${\underline {A(S(0),S(S(0)))}}$	${\underline {A(S(0),S(S(0)))}}$
$\rightarrow _{r3}{\underline {A(0,A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,{\underline {A(S(0),S(0))}})$
$\rightarrow _{r1}S({\underline {A(S(0),S(0))}})$	$\rightarrow _{r3}A(0,A(0,{\underline {A(S(0),0)}}))$
$\rightarrow _{r3}S({\underline {A(0,A(S0,0))}})$	$\rightarrow _{r2}A(0,A(0,{\underline {A(0,S(0))}}))$
$\rightarrow _{r1}S(S({\underline {A(S(0),0)}}))$	$\rightarrow _{r1}A(0,{\underline {A(0,S(S(0)))}})$
$\rightarrow _{r2}S(S({\underline {A(0,S(0))}}))$	$\rightarrow _{r1}{\underline {A(0,S(S(S(0))))}}$
$\rightarrow _{r1}S(S(S(S(0))))$	$\rightarrow _{r1}S(S(S(S(0))))$

Чтобы вычислить $\operatorname {A} (m,n)$ можно использовать стек , который изначально содержит элементы $\langle m,n\rangle$.

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

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

Схематически, начиная с $\langle m,n\rangle$:

WHILE stackLength <> 1
{
   POP 2 elements;
   PUSH 1 or 2 or 3 elements, applying the rules r1, r2, r3
}

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

Например, на входе $\langle 2,1\rangle$,

конфигурации стека	отражают сокращение
${\underline {2,1}}$	${\underline {A(2,1)}}$
$\rightarrow 1,{\underline {2,0}}$	$\rightarrow _{r1}A(1,{\underline {A(2,0)}})$
$\rightarrow 1,{\underline {1,1}}$	$\rightarrow _{r2}A(1,{\underline {A(1,1)}})$
$\rightarrow 1,0,{\underline {1,0}}$	$\rightarrow _{r3}A(1,A(0,{\underline {A(1,0)}}))$
$\rightarrow 1,0,{\underline {0,1}}$	$\rightarrow _{r2}A(1,A(0,{\underline {A(0,1)}}))$
$\rightarrow 1,{\underline {0,2}}$	$\rightarrow _{r1}A(1,{\underline {A(0,2)}})$
$\rightarrow {\underline {1,3}}$	$\rightarrow _{r1}{\underline {A(1,3)}}$
$\rightarrow 0,{\underline {1,2}}$	$\rightarrow _{r3}A(0,{\underline {A(1,2)}})$
$\rightarrow 0,0,{\underline {1,1}}$	$\rightarrow _{r3}A(0,A(0,{\underline {A(1,1)}}))$
$\rightarrow 0,0,0,{\underline {1,0}}$	$\rightarrow _{r3}A(0,A(0,A(0,{\underline {A(1,0)}})))$
$\rightarrow 0,0,0,{\underline {0,1}}$	$\rightarrow _{r2}A(0,A(0,A(0,{\underline {A(0,1)}})))$
$\rightarrow 0,0,{\underline {0,2}}$	$\rightarrow _{r1}A(0,A(0,{\underline {A(0,2)}}))$
$\rightarrow 0,{\underline {0,3}}$	$\rightarrow _{r1}A(0,{\underline {A(0,3)}})$
$\rightarrow {\underline {0,4}}$	$\rightarrow _{r1}{\underline {A(0,4)}}$
$\rightarrow 5$	$\rightarrow _{r1}5$

Примечания

• Самая левая-внутренняя стратегия реализована на 225 компьютерных языках в Rosetta Code .
• Для всех $m,n$ вычисление $A(m,n)$ занимает не более $(A(m,n)+1)^{m}$ шаги.
• Гроссман и Зейтман (1988) отметили, что при вычислении $\operatorname {A} (m,n)$ максимальная длина стека равна $\operatorname {A} (m,n)$, пока $m>0$.

Их собственный алгоритм, по своей сути итеративный, вычисляет $\operatorname {A} (m,n)$ в пределах ${\mathcal {O}}(m\operatorname {A} (m,n))$ время и внутри ${\mathcal {O}}(m)$ космос.

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

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

${\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 можно определить

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

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

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

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

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

Схематически, начиная с $\langle 1,m,n\rangle$:

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

Пример

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

${\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r6}1,1,{\underline {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,{\underline {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{aligned}}$

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

${\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}(A_{0}^{3}(1))=A_{0}(A_{0}(A_{0}^{2}(1)))\\&=A_{0}(A_{0}(A_{0}(A_{0}(1))))=A_{0}(A_{0}(A_{0}(2)))=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}$

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

${\begin{array}{lllllllll}{\text{(r7)}}&(x+2)&,m&,n&\rightarrow &(x+1)&,m&,1&,m&,n\end{array}}$

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

${\begin{aligned}&{\underline {1,2,1}}\rightarrow _{r5}{\underline {2,1,1}}\rightarrow _{r7}1,1,{\underline {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{aligned}}$

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

${\begin{aligned}&A_{2}(1)=A_{1}^{2}(1)=A_{1}(A_{1}(1))=A_{1}(A_{0}^{2}(1))=A_{1}(A_{0}(A_{0}(1)))\\&=A_{1}(A_{0}(2))=A_{1}(3)=A_{0}^{4}(1)=A_{0}^{3}(A_{0}(1))=A_{0}^{3}(2)\\&=A_{0}^{2}(A_{0}(2))=A_{0}^{2}(3)=A_{0}(A_{0}(3))=A_{0}(4)=5\end{aligned}}$

Примечания

• На любых входных данных представленные до сих пор TRS сходятся за одинаковое количество шагов. Они также используют одни и те же правила редукции (в этом сравнении правила r1, r2, r3 считаются «такими же, как» правила r4, r5, r6/r7 соответственно). Например, сокращение $A(2,1)$ сходится за 14 шагов: 6×r1, 3×r2, 5×r3. Сокращение $A_{2}(1)$ сходится за те же 14 шагов: 6×r4, 3×r5, 5×r6/r7. ИВВ различаются порядком применения правил сокращения.
• Когда $A_{i}(n)$ вычисляется по правилам {r4, r5, r6}, максимальная длина стека остается ниже $2\times A(i,n)$. Когда вместо правила r6 используется правило сокращения r7, максимальная длина стека составляет всего $2(i+2)$. Длина стека отражает глубину рекурсии. Поскольку приведение по правилам {r4, r5, r7} предполагает меньшую максимальную глубину рекурсии, в этом отношении такое вычисление более эффективно.

TRS на основе гипероператоров

Как ясно показали Сундблад (1971) или Порто и Матос (1980) , функцию Аккермана можно выразить через последовательность гиперопераций :

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

или, после удаления константы 2 из списка параметров, через функцию Бака

$={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}$

Функция Бака $\operatorname {F} (m,n)=2[m]n$, вариант функции Аккермана сам по себе можно вычислить с помощью следующих правил сведения:

${\begin{array}{lll}{\text{(b1)}}&F(S(0),0,n)&\rightarrow &S(n)\\{\text{(b2)}}&F(S(0),S(0),0)&\rightarrow &S(S(0))\\{\text{(b3)}}&F(S(0),S(S(0)),0)&\rightarrow &0\\{\text{(b4)}}&F(S(0),S(S(S(m))),0)&\rightarrow &S(0)\\{\text{(b5)}}&F(S(0),S(m),S(n))&\rightarrow &F(S(n),m,F(S(0),S(m),0))\\{\text{(b6)}}&F(S(S(x)),m,n)&\rightarrow &F(S(0),m,F(S(x),m,n))\end{array}}$

Вместо правила b6 можно определить правило

${\begin{array}{lll}{\text{(b7)}}&F(S(S(x)),m,n)&\rightarrow &F(S(x),m,F(S(0),m,n))\end{array}}$

Для вычисления функции Аккермана достаточно добавить три правила приведения

${\begin{array}{lll}{\text{(r8)}}&A(0,n)&\rightarrow &S(n)\\{\text{(r9)}}&A(S(m),n)&\rightarrow &P(F(S(0),S(m),S(S(S(n)))))\\{\text{(r10)}}&P(S(S(S(m))))&\rightarrow &m\\\end{array}}$

Эти правила учитывают базовый случай A(0,n), выравнивание (n+3) и выдумку (-3).

Пример

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

используя правило сокращения ${\text{b7}}$:	используя правило сокращения ${\text{b6}}$:
${\underline {A(2,1)}}$	${\underline {A(2,1)}}$
$\rightarrow _{r9}P({\underline {F(1,2,4)}})$	$\rightarrow _{r9}P({\underline {F(1,2,4)}})$
$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$	$\rightarrow _{b5}P(F(4,1,{\underline {F(1,2,0)}}))$
$\rightarrow _{b3}P({\underline {F(4,1,0)}})$	$\rightarrow _{b3}P({\underline {F(4,1,0)}})$
$\rightarrow _{b7}P(F(3,1,{\underline {F(1,1,0)}}))$	$\rightarrow _{b6}P(F(1,1,{\underline {F(3,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(3,1,2)}})$	$\rightarrow _{b6}P(F(1,1,F(1,1,{\underline {F(2,1,0)}})))$
$\rightarrow _{b7}P(F(2,1,{\underline {F(1,1,2)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,1,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b5}P(F(2,1,F(2,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(1,1,2)}})))$
$\rightarrow _{b2}P(F(2,1,{\underline {F(2,0,2)}}))$	$\rightarrow _{b5}P(F(1,1,F(1,1,F(2,0,{\underline {F(1,1,0)}}))))$
$\rightarrow _{b7}P(F(2,1,F(1,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b2}P(F(1,1,F(1,1,{\underline {F(2,0,2)}})))$
$\rightarrow _{b1}P(F(2,1,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,1,F(1,0,{\underline {F(1,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(2,1,4)}})$	$\rightarrow _{b1}P(F(1,1,F(1,1,{\underline {F(1,0,3)}})))$
$\rightarrow _{b7}P(F(1,1,{\underline {F(1,1,4)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,1,4)}}))$
$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$	$\rightarrow _{b5}P(F(1,1,F(4,0,{\underline {F(1,1,0)}})))$
$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$	$\rightarrow _{b2}P(F(1,1,{\underline {F(4,0,2)}}))$
$\rightarrow _{b7}P(F(1,1,F(3,0,{\underline {F(1,0,2)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,{\underline {F(3,0,2)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(3,0,3)}}))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,{\underline {F(2,0,2)}}))))$
$\rightarrow _{b7}P(F(1,1,F(2,0,{\underline {F(1,0,3)}})))$	$\rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}})))))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(2,0,4)}}))$	$\rightarrow _{b1}P(F(1,1,F(1,0,F(1,0,{\underline {F(1,0,3)}}))))$
$\rightarrow _{b7}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$	$\rightarrow _{b1}P(F(1,1,F(1,0,{\underline {F(1,0,4)}})))$
$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,1,{\underline {F(1,0,5)}}))$
$\rightarrow _{b1}P({\underline {F(1,1,6)}})$	$\rightarrow _{b1}P({\underline {F(1,1,6)}})$
$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$	$\rightarrow _{b5}P(F(6,0,{\underline {F(1,1,0)}}))$
$\rightarrow _{b2}P({\underline {F(6,0,2)}})$	$\rightarrow _{b2}P({\underline {F(6,0,2)}})$
$\rightarrow _{b7}P(F(5,0,{\underline {F(1,0,2)}}))$	$\rightarrow _{b6}P(F(1,0,{\underline {F(5,0,2)}}))$
$\rightarrow _{b1}P({\underline {F(5,0,3)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,{\underline {F(4,0,2)}})))$
$\rightarrow _{b7}P(F(4,0,{\underline {F(1,0,3)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,{\underline {F(3,0,2)}}))))$
$\rightarrow _{b1}P({\underline {F(4,0,4)}})$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(2,0,2)}})))))$
$\rightarrow _{b7}P(F(3,0,{\underline {F(1,0,4)}}))$	$\rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,2)}}))))))$
$\rightarrow _{b1}P({\underline {F(3,0,5)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,F(1,0,{\underline {F(1,0,3)}})))))$
$\rightarrow _{b7}P(F(2,0,{\underline {F(1,0,5)}}))$	$\rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,{\underline {F(1,0,4)}}))))$
$\rightarrow _{b1}P({\underline {F(2,0,6)}})$	$\rightarrow _{b1}P(F(1,0,F(1,0,{\underline {F(1,0,5)}})))$
$\rightarrow _{b7}P(F(1,0,{\underline {F(1,0,6)}}))$	$\rightarrow _{b1}P(F(1,0,{\underline {F(1,0,6)}}))$
$\rightarrow _{b1}P({\underline {F(1,0,7)}})$	$\rightarrow _{b1}P({\underline {F(1,0,7)}})$
$\rightarrow _{b1}{\underline {P(8)}}$	$\rightarrow _{b1}{\underline {P(8)}}$
$\rightarrow _{r10}5$	$\rightarrow _{r10}5$

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

• когда ИВВ с правилом сокращения ${\text{b6}}$ применяется:

${\begin{aligned}&A(2,1)+3=F(2,4)=\dots =F^{6}(0,2)=F(0,F^{5}(0,2))=F(0,F(0,F^{4}(0,2)))\\&=F(0,F(0,F(0,F^{3}(0,2))))=F(0,F(0,F(0,F(0,F^{2}(0,2)))))=F(0,F(0,F(0,F(0,F(0,F(0,2))))))\\&=F(0,F(0,F(0,F(0,F(0,3)))))=F(0,F(0,F(0,F(0,4))))=F(0,F(0,F(0,5)))=F(0,F(0,6))=F(0,7)=8\end{aligned}}$

• когда ИВВ с правилом сокращения ${\text{b7}}$ применяется:

${\begin{aligned}&A(2,1)+3=F(2,4)=\dots =F^{6}(0,2)=F^{5}(0,F(0,2))=F^{5}(0,3)=F^{4}(0,F(0,3))=F^{4}(0,4)\\&=F^{3}(0,F(0,4))=F^{3}(0,5)=F^{2}(0,F(0,5))=F^{2}(0,6)=F(0,F(0,6))=F(0,7)=8\end{aligned}}$

Примечания

• Вычисление $\operatorname {A} _{i}(n)$ по правилам {b1 - b5, b6, r8 - r10} является глубоко рекурсивным. Максимальная глубина вложенности $F$это $A(i,n)+1$. Виновником является порядок выполнения итерации: $F^{n+1}(x)=F(F^{n}(x))$. Первый $F$ исчезает только после того, как вся последовательность развернута.
• Вычисление по правилам {b1 - b5, b7, r8 - r10} в этом отношении более эффективно. Итерация $F^{n+1}(x)=F^{n}(F(x))$ имитирует повторяющийся цикл по блоку кода. Вложение ограничивается $(i+1)$, один уровень рекурсии на каждую повторяемую функцию. Мейер и Ричи (1967) показали это соответствие.
• Эти соображения касаются только глубины рекурсии. Любой способ итерации приводит к одинаковому количеству шагов сокращения с использованием одних и тех же правил (когда правила b6 и b7 считаются «одинаковыми»). Сокращение $A(2,1)$ например, сходится за 35 шагов: 12 × b1, 4 × b2, 1 × b3, 4 × b5, 12 × b6/b7, 1 × r9, 1 × r10. Modus iterandi влияет только на порядок применения правил сокращения.
• Реального выигрыша во времени выполнения можно добиться, только не пересчитывая промежуточные результаты снова и снова. Мемоизация — это метод оптимизации, при котором результаты вызовов функций кэшируются и возвращаются, когда те же входные данные повторяются. См., например, Ward (1993) . Гроссман и Зейтман (1988) опубликовали хитрый алгоритм, который вычисляет $A(i,n)$ в пределах ${\mathcal {O}}(iA(i,n))$ время и внутри ${\mathcal {O}}(i)$ космос.

Огромные цифры

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

${\begin{aligned}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,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,65533))\\&\qquad \vdots \\&\rightarrow A(3,2^{65536}-3)\\&\qquad \vdots \\&\rightarrow 2^{2^{65536}}-3.\\\end{aligned}}$

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

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

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

н м	0	1	2	3	4	н
0	1	2	3	4	5	$n+1$
1	2	3	4	5	6	$n+2=2+(n+3)-3$
2	3	5	7	9	11	$2n+3=2\cdot (n+3)-3$
3	5	13	29	61	125	$2^{(n+3)}-3$
4	13	65533	2 65536  − 3	${2^{2^{65536}}}-3$	${2^{2^{2^{65536}}}}-3$	${\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} _{n+3}-3\end{matrix}}$
	$={2^{2^{2}}}-3$ $=2\uparrow \uparrow 3-3$	$={2^{2^{2^{2}}}}-3$ $=2\uparrow \uparrow 4-3$	$={2^{2^{2^{2^{2}}}}}-3$ $=2\uparrow \uparrow 5-3$	$={2^{2^{2^{2^{2^{2}}}}}}-3$ $=2\uparrow \uparrow 6-3$	$={2^{2^{2^{2^{2^{2^{2}}}}}}}-3$ $=2\uparrow \uparrow 7-3$
						$=2\uparrow \uparrow (n+3)-3$
5	65533 $=2\uparrow \uparrow (2\uparrow \uparrow 2)-3$ $=2\uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow (n+3)-3$
6	$2\uparrow \uparrow \uparrow \uparrow 3-3$	$2\uparrow \uparrow \uparrow \uparrow 4-3$	$2\uparrow \uparrow \uparrow \uparrow 5-3$	$2\uparrow \uparrow \uparrow \uparrow 6-3$	$2\uparrow \uparrow \uparrow \uparrow 7-3$	$2\uparrow \uparrow \uparrow \uparrow (n+3)-3$
м	$(2\to 3\to (m-2))-3$	$(2\to 4\to (m-2))-3$	$(2\to 5\to (m-2))-3$	$(2\to 6\to (m-2))-3$	$(2\to 7\to (m-2))-3$	$(2\to (n+3)\to (m-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)	А (2, А (3, n −1))
4	А (3, 1)	А (3, А (4, 0)) = А (3, 13)	А (3, А (4, 1)) = А (3, 65533)	А (3, А (4, 2))	А (3, А (4, 3))	А (3, А (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, п -1))

Свойства

Общие замечания

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

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

Функция Аккермана растет быстрее, чем любая примитивно-рекурсивная функция , и поэтому сама по себе не является примитивно-рекурсивной. Схема доказательства такова: примитивно-рекурсивная функция, определенная с использованием до k рекурсий, должна расти медленнее, чем $f_{k+1}(n)$, (k+1)-я функция в быстрорастущей иерархии, но функция Аккермана растет по крайней мере так же быстро, как $f_{\omega }(n)$.

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

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

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

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

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

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

в

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

Инверсия

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

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

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

$\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 годами.

См. также

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

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

• Акерманн, Вильгельм (1928). «О гильбертовой структуре действительных чисел» . Математические летописи . 99 : 118–133. дои : 10.1007/BF01459088 . S2CID   123431274 .
• Бак, RC (1963). «Математическая индукция и рекурсивные определения». Американский математический ежемесячник . 70 (2): 128–135. дои : 10.2307/2312881 . JSTOR   2312881 .
• Калуде, Кристиан ; Маркус, Соломон ; Теви, Ионел (ноябрь 1979 г.). «Первый пример рекурсивной функции, которая не является примитивно-рекурсивной» . История математики . 6 (4): 380–84. дои : 10.1016/0315-0860(79)90024-7 .
• Коэн, Дэниел Э. (январь 1987 г.). Вычислимость и логика . Холстед Пресс. ISBN  9780745800349 .
• Корнелиус, Би Джей; Кирби, GH (1975). «Глубина рекурсии и функция Аккермана». БИТ Численная математика . 15 (2): 144–150. дои : 10.1007/BF01932687 . S2CID   120532578 .
• Червинский, Войцех; Орликовский, Лукаш (7 февраля 2022 г.). Достижимость в системах сложения векторов является полной по Аккерману . Материалы 62-го ежегодного симпозиума IEEE по основам информатики 2021 года. arXiv : 2104.13866 . дои : 10.1109/FOCS52979.2021.00120 .
• Гроссман, Джеррольд В.; Зейтман, Р.Сюзанна (май 1988 г.). «Итеративное по своей сути вычисление функции Аккермана». Теоретическая информатика . 57 (2–3): 327–330. дои : 10.1016/0304-3975(88)90046-1 .
• ван Хейеноорт, Жан (1977) [перепечатано с исправлениями, впервые опубликовано в 1967 году]. От Фреге до Гёделя: Справочник по математической логике, 1879–1931 . Издательство Гарвардского университета.
• Гильберт, Дэвид (1926). «О Бесконечном». Математические летописи . 95 : 161-190. дои : 10.1007/BF01206605 . S2CID   121888793 .
• Леру, Жером (7 февраля 2022 г.). Проблема достижимости сетей Петри не является примитивно-рекурсивной . Материалы 62-го ежегодного симпозиума IEEE по основам информатики 2021 года. arXiv : 2104.12695 . дои : 10.1109/FOCS52979.2021.00121 .
• Матос, Армандо Б. (7 мая 2014 г.). «Обратная функция Аккермана примитивно рекурсивна» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.
• Меуссен, VCS; Зантема, Х. (1992). Длины вывода при переписывании терминов на основе интерпретаций в натуральных числах (PDF) (Отчет). Университет Утрехта. УУ-КС, факультет компьютерных наук. ISSN   0924-3275 . Архивировано (PDF) из оригинала 9 октября 2022 г.
• Мейер, Альберт Р .; Ричи, Деннис Макалистер (1967). «Сложность циклических программ». Материалы 22-й национальной конференции 1967 года . ACM '67: Материалы 22-й национальной конференции 1967 года. стр. 465–469. дои : 10.1145/800196.806014 .
• Монен, Жан-Франсуа; Хинчи, М.Г. (2003). Понимание формальных методов . Спрингер. п. 61. ИСБН  9781852332471 .
• Мунафо, Роберт (1999a). «Варианты функции Аккермана» . Большие числа в MROB . Проверено 6 ноября 2021 г.
• Мунафо, Роберт (1999b). «Изобретение новых операторов и функций» . Большие числа в MROB . Проверено 6 ноября 2021 г.
• Полсон, Лоуренс К. (2021). «Функция Аккермана в итеративной форме: эксперимент-помощник по доказательству» . Проверено 19 октября 2021 г.
• Петер, Рожа (1935). «Построение нерекурсивных функций». Математические летописи . 111 : 42–60. дои : 10.1007/BF01472200 . S2CID   121107217 .
• Петти, С. (2002). «Нижняя оценка в стиле обратного Аккермана для онлайн-задачи проверки минимального остовного дерева». 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г. Материалы . стр. 155–163. дои : 10.1109/SFCS.2002.1181892 . ISBN  0-7695-1822-2 . S2CID   8636108 .
• Порту, Антониу; Матос, Армандо Б. (1 сентября 1980 г.). «Акерманн и сверхдержавы» (PDF) . Новости ACM SIGACT . 12 (3): Исходная версия 1980 г., опубликована в «ACM SIGACT News», с изменениями от 20 октября 2012 г., с изменениями от 23 января 2016 г. (рабочий документ). дои : 10.1145/1008861.1008872 . S2CID   29780652 . Архивировано (PDF) из оригинала 9 октября 2022 г.
• Ричи, Роберт Уэллс (ноябрь 1965 г.). «Классы рекурсивных функций, основанные на функции Аккермана» . Тихоокеанский математический журнал . 15 (3): 1027–1044. дои : 10.2140/pjm.1965.15.1027 .
• Робинсон, Рафаэль Митчел (1948). «Рекурсия и двойная рекурсия» . Бюллетень Американского математического общества . 54 (10): 987–93. дои : 10.1090/S0002-9904-1948-09121-2 .
• Сундблад, Ингве (март 1971 г.). «Функция Аккермана. Теоретическое, вычислительное исследование и исследование формул». БИТ Численная математика . 11 (1): 107–119. дои : 10.1007/BF01935330 . S2CID   123416408 .
• Вайда, Драгош (1970). «Проверка компилятора для алголоподобного языка». Математический вестник Общества математических наук Социалистической Республики Румыния . Новая серия. 14 (62) (4): 487–502. JSTOR   43679758 .
• Уорд, Мартин П. (16 июля 1993 г.). Итерационные процедуры вычисления функции Аккермана . CiteSeerX   10.1.1.35.9907 .
• Вичманн, Брайан А. (март 1976 г.). «Функция Аккермана: исследование эффективности процедур вызова». БИТ Численная математика . 16 : 103–110. CiteSeerX   10.1.1.108.4125 . дои : 10.1007/BF01940783 . S2CID   16993343 .
• Вичманн, Брайан А. (июль 1977 г.). «Как вызывать процедуры, или размышления о функции Аккермана». БИТ Численная математика . 16 (3): 103–110. дои : 10.1002/спе.4380070303 . S2CID   206507320 .
• Вичманн, Брайан А. (июль 1982 г.). «Последние результаты теста вызова процедуры, функция Аккермана» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.

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

• «Функция Аккермана» . Энциклопедия математики . ЭМС Пресс . 2001 [1994].
• Вайсштейн, Эрик В. «Функция Аккермана» . Математический мир .
• В этой статье использованы общедоступные материалы из Пол Э. Блэк. «Функция Аккермана» . Словарь алгоритмов и структур данных . НИСТ .
• Анимированный калькулятор функций Аккермана.
• Ааронсон, Скотт (1999). «Кто назовет большее число?» .
• Функции Аккермана . Включает таблицу некоторых значений.
• Брубейкер, Бен (04 декабря 2023 г.). «Просто кажущаяся проблема дает числа, слишком большие для нашей Вселенной» .
• Мунафо, Роберт. «Большие числа» . описывает несколько вариантов определения A .
• Ниваш, Габриэль (октябрь 2021 г.). «Обратный Аккерман без боли» . Архивировано из оригинала 21 августа 2007 г. Проверено 18 июня 2023 г.
• Зейдель, Раймунд. «Понимание обратной функции Аккермана» (PDF) .
• Функция Аккермана, написанная на разных языках программирования , (на Rosetta Code )
• Смит, Гарри Дж. «Функция Аккермана» . Архивировано из оригинала 26 октября 2009 г. ) Немного учебы и программирования.