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

Быстрорастущая функция

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

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

История

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

${\displaystyle {\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,n,1)&=m\times n\\\varphi (m,n,2)&=m^{n}\end{aligned}}}$

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

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

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

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

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

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

В 1963 году Р. К. Бак основал интуитивный вариант с двумя переменными ^{[n 1]} на последовательности гиперопераций : ^{[10] [11]} ${\displaystyle \operatorname {F} }$

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

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

${\displaystyle {\begin{aligned}\operatorname {F} (0,n)&=2[0]n=n+1\\\operatorname {F} (1,n)&=2[1]n=2+n\\\operatorname {F} (2,n)&=2[2]n=2\times n\\\operatorname {F} (3,n)&=2[3]n=2^{n}\\\operatorname {F} (4,n)&=2[4]n=2^{2^{2^{{}^{.^{.^{{}_{.}2}}}}}}\\&\quad \vdots \end{aligned}}}$

Было исследовано много других версий функции Аккермана. ^{[12] [13]}

Определение

Определение: как m-арная функция

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

${\displaystyle {\begin{aligned}\varphi (m,n,0)&=m+n\\\varphi (m,0,1)&=0\\\varphi (m,0,2)&=1\\\varphi (m,0,p)&=m&&{\text{for }}p>2\\\varphi (m,n,p)&=\varphi (m,\varphi (m,n-1,p),p-1)&&{\text{for }}n,p>0\end{aligned}}}$

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

${\displaystyle {\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,\operatorname {A} (m+1,n))\end{array}}}$

Функция Аккермана также была выражена в отношении последовательности гиперопераций : ^{[14] [15]}

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

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

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

или, что эквивалентно, в терминах функции Бака F: ^[10]

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

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

Определим как n -ю итерацию : ${\displaystyle f^{n}}$ ${\displaystyle f}$

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

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

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

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

${\displaystyle {\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-арной функции Аккермана приводит к очевидным правилам редукции ^{[16] [17]}

${\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 A(1,2)\rightarrow _{*}4}$

Последовательность сокращения: ^{[n 3]}

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

Затем повторно два верхних элемента заменяются в соответствии с правилами ^{[n 4]}

${\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 m,n\rangle }$

WHILE длина стека <> 1{ ВСТАВИТЬ 2 элемента; ВСТАВИТЬ 1 или 2 или 3 элемента, применяя правила r1, r2, r3}

Псевдокод опубликован в работе Гроссмана и Цейтмана (1988).

Например, при вводе , ${\displaystyle \langle 2,1\rangle }$

Замечания

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

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

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

Определение итерированных 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,m,n\rangle }$

Затем три верхних элемента многократно заменяются в соответствии с правилами ^{[n 4]}

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

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

WHILE длина стека <> 1{ ВСТАВИТЬ 3 элемента; ВЫТЯНУТЬ 1 или 3 или 5 элементов, применяя правила r4, r5, r6;}

Пример

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

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

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

${\displaystyle {\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 замены в стеке будут следующими

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

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

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

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

${\displaystyle {\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 соответственно). Например, редукция сходится за 14 шагов: 6 × r1, 3 × r2, 5 × r3. Редукция сходится за те же 14 шагов: 6 × r4, 3 × r5, 5 × r6/r7. TRS различаются порядком применения правил редукции. ${\displaystyle A(2,1)}$ ${\displaystyle A_{2}(1)}$
• Когда вычисляется по правилам {r4, r5, r6}, максимальная длина стека остается ниже . Когда вместо правила r6 используется правило редукции r7, максимальная длина стека составляет всего . Длина стека отражает глубину рекурсии. Поскольку редукции по правилам {r4, r5, r7} подразумевает меньшую максимальную глубину рекурсии, ^{[n 6]} это вычисление более эффективно в этом отношении. ${\displaystyle A_{i}(n)}$ ${\displaystyle 2\times A(i,n)}$ ${\displaystyle 2(i+2)}$

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

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

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

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

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

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

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

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

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

${\displaystyle {\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).

Пример

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

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

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

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

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

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

Замечания

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

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

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

${\displaystyle {\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» в предыдущей строке. Вот небольшая верхняя левая часть таблицы:

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

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

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

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

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

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

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

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

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

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

Использование в вычислительной сложности

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

Обратный

Поскольку рассмотренная выше функция 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 , а функция floor иногда заменяется на ceiling .

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

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

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

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

Основополагающая работа Сундблада была продолжена Брайаном Вихманном (соавтором эталонного теста Whetstone ) в трилогии статей, написанных между 1975 и 1982 годами. ^{[25] [26] [27]}

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

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

Примечания

1. с обратным порядком параметров
2. ' карри '
3. На каждом шаге подчеркнутый редекс переписывается.
4. здесь: стратегия «самая левая-самая внутренняя»!
5. Для лучшей читаемости
   S(0) обозначается как 1,
   S(S(0)) обозначается как 2,
   S(S(S(0))) обозначается как 3
   и т. д.
6. Максимальная глубина рекурсии относится к числу уровней активации процедуры, которые существуют во время самого глубокого вызова процедуры. Корнелиус и Кирби (1975)
7. ЦИКЛ n+1 РАЗ ДЕЛИТЬ F

Ссылки

1. Монин и Хинчи 2003, с. 61.
2. Аккерманн 1928.
3. "Десятичное разложение A(4,2)". kosara.net . 27 августа 2000 г. Архивировано из оригинала 20 января 2010 г.
4. Калуде, Маркус и Теви 1979.
5. Гильберт 1926, стр. 185.
6. ван Хейеноорт 1977.
7. Питер 1935.
8. Робинсон 1948.
9. Ричи 1965, стр. 1028.
10. Бак 1963.
11. Меуссен и Зантема 1992, стр. 6.
12. Мунафо 1999a.
13. Ричи 1965.
14. Sundblad 1971.
15. Порто и Матос 1980.
16. Гроссман и Цейтман 1988.
17. Полсон 2021.
18. Коэн 1987, стр. 56, Предложение 3.16 (см. в корректуре).
19. Брубейкер 2023.
20. Червинский и Орликовский 2022.
21. Леру 2022.
22. Петти 2002.
23. Матос 2014.
24. Вайда 1970.
25. Вихманн 1976.
26. Вихманн 1977.
27. Вихманн 1982.

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

• Акерманн, Вильгельм (1928). «Zum Hilbertschen Aufbau der reellen Zahlen». Математические Аннален . 99 : 118–133. дои : 10.1007/BF01459088. S2CID  123431274.
• Бак, RC (1963). «Математическая индукция и рекурсивные определения». American Mathematical Monthly . 70 (2): 128–135. doi :10.2307/2312881. JSTOR  2312881.
• Calude, Cristian ; Marcus, Solomon ; Tevy, Ionel (ноябрь 1979 г.). «Первый пример рекурсивной функции, которая не является примитивно рекурсивной». Historia Math . 6 (4): 380–84. doi : 10.1016/0315-0860(79)90024-7 .
• Коэн, Дэниел Э. (январь 1987). Вычислимость и логика . Halsted Press. ISBN 9780745800349.
• Корнелиус, Б. Дж.; Кирби, Г. Х. (1975). «Глубина рекурсии и функция Акермана». BIT Numerical Mathematics . 15 (2): 144–150. doi :10.1007/BF01932687. S2CID  120532578.
• Czerwiński, Wojciech; Orlikowski, Łukasz (7 февраля 2022 г.). Достижимость в системах сложения векторов является полной по Аккерману. Труды 62-го ежегодного симпозиума IEEE 2021 года по основам компьютерной науки. arXiv : 2104.13866 . doi :10.1109/FOCS52979.2021.00120.
• Grossman, Jerrold W.; Zeitman, R.Suzanne (май 1988). "По сути итеративное вычисление функции Аккермана". Теоретическая информатика . 57 (2–3): 327–330. doi :10.1016/0304-3975(88)90046-1.
• ван Хейеноорт, Жан (1977) [перепечатано с исправлениями, впервые опубликовано в 1967]. От Фреге до Гёделя: Учебник по математической логике, 1879–1931 . Издательство Гарвардского университета.
• Гильберт, Дэвид (1926). «Über das Unendliche». Математические Аннален . 95 : 161–190. дои : 10.1007/BF01206605. S2CID  121888793.
• Leroux, Jérôme (7 февраля 2022 г.). Проблема достижимости сетей Петри не является примитивно рекурсивной. Труды 62-го ежегодного симпозиума IEEE 2021 года по основам компьютерной науки. arXiv : 2104.12695 . doi : 10.1109/FOCS52979.2021.00121.
• Матос, Армандо Б. (7 мая 2014 г.). "Обратная функция Аккермана примитивно рекурсивна" (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.
• Meeussen, VCS; Zantema, H. (1992). Derivation lengths in term rewriting from interpretations in the naturals (PDF) (Report). Universiteit Utrecht. UU-CS, Department of Computer Science. ISSN  0924-3275. Архивировано (PDF) из оригинала 9 октября 2022 г.
• Мейер, Альберт Р.; Ритчи , Деннис МакАлистер (1967). «Сложность циклических программ». Труды 22-й национальной конференции 1967 г. . ACM '67: Труды 22-й национальной конференции 1967 г. Стр. 465–469. doi : 10.1145/800196.806014 .
• Монин, Жан-Франсуа; Хинчи, МГ (2003). Понимание формальных методов. Springer. стр. 61. ISBN 9781852332471.
• Мунафо, Роберт (1999a). «Версии функции Аккермана». Большие числа в MROB . Получено 6 ноября 2021 г.
• Мунафо, Роберт (1999b). «Изобретение новых операторов и функций». Большие числа в MROB . Получено 6 ноября 2021 г.
• Полсон, Лоуренс К. (2021). "Функция Аккермана в итеративной форме: эксперимент с помощником по доказательству" . Получено 19 октября 2021 г. .
• Петер, Рожа (1935). «Конструкция nichtrekursiver Funktionen». Математические Аннален . 111 : 42–60. дои : 10.1007/BF01472200. S2CID  121107217.
• Pettie, S. (2002). "Нижняя граница в стиле обратного Аккермана для проблемы проверки минимального остовного дерева в режиме онлайн". 43-й ежегодный симпозиум IEEE по основам компьютерной науки, 2002. Труды . С. 155–163. doi :10.1109/SFCS.2002.1181892. ISBN 0-7695-1822-2. S2CID  8636108.
• Порту, Антонио; Матос, Армандо Б. (1 сентября 1980 г.). «Акерман и сверхдержавы» (PDF) . Новости ACM SIGACT . 12 (3): Оригинальная версия 1980 г., опубликована в «Новости ACM SIGACT», Изменено 20 октября 2012 г., Изменено 23 января 2016 г. (рабочий документ). doi : 10.1145/1008861.1008872. S2CID  29780652. Архивировано (PDF) из оригинала 9 октября 2022 г.
• Ритчи, Роберт Уэллс (ноябрь 1965 г.). «Классы рекурсивных функций, основанные на функции Аккермана». Pacific Journal of Mathematics . 15 (3): 1027–1044. doi : 10.2140/pjm.1965.15.1027 .
• Робинсон, Рафаэль Митчел (1948). «Рекурсия и двойная рекурсия». Бюллетень Американского математического общества . 54 (10): 987–93. doi : 10.1090/S0002-9904-1948-09121-2 .
• Сундблад, Ингве (март 1971 г.). «Функция Аккермана. Теоретическое, вычислительное и формульное исследование». BIT Numerical Mathematics . 11 (1): 107–119. doi :10.1007/BF01935330. S2CID  123416408.
• Вайда, Драгош (1970). «Проверка компилятора для алголоподобного языка». Бюллетень Математического общества Математических наук Республики Социалистическая Румыния . Новая серия. 14 (62) (4): 487–502. JSTOR  43679758.
• Уорд, Мартин П. (16 июля 1993 г.). Итеративные процедуры вычисления функции Аккермана . CiteSeerX  10.1.1.35.9907 .
• Wichmann, Brian A. (март 1976 г.). «Функция Аккермана: исследование эффективности вызовов процедур». BIT Numerical Mathematics . 16 : 103–110. CiteSeerX  10.1.1.108.4125 . doi :10.1007/BF01940783. S2CID  16993343.
• Вихманн, Брайан А. (июль 1977 г.). «Как вызывать процедуры, или вторые мысли о функции Аккермана». BIT Numerical Mathematics . 16 (3): 103–110. doi :10.1002/spe.4380070303. S2CID  206507320.
• Вихманн, Брайан А. (июль 1982 г.). "Последние результаты теста вызова процедур, функция Аккермана" (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г.

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

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