Функция Аккермана
Быстрорастущая функция

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

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

История

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

φ ( м , н , 0 ) = м + н φ ( м , н , 1 ) = м × н φ ( м , н , 2 ) = м н {\displaystyle {\begin{align}\varphi (m,n,0)&=m+n\\\varphi (m,n,1)&=m\times n\\\varphi (m,n,2)&=m^{n}\end{align}}}

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

φ ( м , н , 3 ) = м [ 4 ] ( н + 1 ) φ ( м , н , п ) ⪆ м [ п + 1 ] ( н + 1 ) для  п > 3 {\displaystyle {\begin{align}\varphi (m,n,3)&=m[4](n+1)\\\varphi (m,n,p)&\gtrapprox m[p+1](n+1)&&{\text{for }}p>3\end{align}}}

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

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

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

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

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

Ф ⁡ ( м , н ) = 2 [ м ] н . {\displaystyle \operatorname {F} (m,n)=2[m]n.}

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

F ⁡ ( 0 , n ) = 2 [ 0 ] n = n + 1 F ⁡ ( 1 , n ) = 2 [ 1 ] n = 2 + n F ⁡ ( 2 , n ) = 2 [ 2 ] n = 2 × n F ⁡ ( 3 , n ) = 2 [ 3 ] n = 2 n F ⁡ ( 4 , n ) = 2 [ 4 ] n = 2 2 2 . . . 2 ⋮ {\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-арная функция

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

φ ( m , n , 0 ) = m + n φ ( m , 0 , 1 ) = 0 φ ( m , 0 , 2 ) = 1 φ ( m , 0 , p ) = m for  p > 2 φ ( m , n , p ) = φ ( m , φ ( m , n − 1 , p ) , p − 1 ) for  n , p > 0 {\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}}}

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

A ⁡ ( 0 , n ) = n + 1 A ⁡ ( m + 1 , 0 ) = A ⁡ ( m , 1 ) A ⁡ ( m + 1 , n + 1 ) = A ⁡ ( m , A ⁡ ( m + 1 , 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]

A ( m , n ) = { n + 1 m = 0 2 [ m ] ( n + 3 ) − 3 m > 0 {\displaystyle A(m,n)={\begin{cases}n+1&m=0\\2[m](n+3)-3&m>0\\\end{cases}}}
или, записанный в нотации Кнута со стрелкой вверх (расширенной до целочисленных индексов ): ≥ − 2 {\displaystyle \geq -2}
= { n + 1 m = 0 2 ↑ m − 2 ( n + 3 ) − 3 m > 0 {\displaystyle ={\begin{cases}n+1&m=0\\2\uparrow ^{m-2}(n+3)-3&m>0\\\end{cases}}}
или, что эквивалентно, в терминах функции Бака F: [10]
= { n + 1 m = 0 F ( m , n + 3 ) − 3 m > 0 {\displaystyle ={\begin{cases}n+1&m=0\\F(m,n+3)-3&m>0\\\end{cases}}}

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

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

f 0 ( x ) = x f n + 1 ( x ) = f ( f n ( x ) ) {\displaystyle {\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 ) ) {\displaystyle f(f^{n}(x))=f^{n}(f(x))}

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

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

A 0 ⁡ ( n ) = n + 1 A m + 1 ⁡ ( n ) = A m n + 1 ⁡ ( 1 ) {\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]

(r1) A ( 0 , n ) → S ( n ) (r2) A ( S ( m ) , 0 ) → A ( m , S ( 0 ) ) (r3) A ( S ( m ) , S ( n ) ) → A ( m , A ( S ( m ) , n ) ) {\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}}}

Пример

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

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

Стратегия «самый левый-самый внешний» (одношаговая) :            Стратегия «самый левый-самый внутренний» (один шаг) :
A ( S ( 0 ) , S ( S ( 0 ) ) ) _ {\displaystyle {\underline {A(S(0),S(S(0)))}}} A ( S ( 0 ) , S ( S ( 0 ) ) ) _ {\displaystyle {\underline {A(S(0),S(S(0)))}}}
     → r 3 A ( 0 , A ( S ( 0 ) , S ( 0 ) ) _ ) {\displaystyle \rightarrow _{r3}{\underline {A(0,A(S(0),S(0))}})}      → r 3 A ( 0 , A ( S ( 0 ) , S ( 0 ) ) _ ) {\displaystyle \rightarrow _{r3}A(0,{\underline {A(S(0),S(0))}})}
     → r 1 S ( A ( S ( 0 ) , S ( 0 ) ) _ ) {\displaystyle \rightarrow _{r1}S({\underline {A(S(0),S(0))}})}      → r 3 A ( 0 , A ( 0 , A ( S ( 0 ) , 0 ) _ ) ) {\displaystyle \rightarrow _{r3}A(0,A(0,{\underline {A(S(0),0)}}))}
     → r 3 S ( A ( 0 , A ( S 0 , 0 ) ) _ ) {\displaystyle \rightarrow _{r3}S({\underline {A(0,A(S0,0))}})}      → r 2 A ( 0 , A ( 0 , A ( 0 , S ( 0 ) ) _ ) ) {\displaystyle \rightarrow _{r2}A(0,A(0,{\underline {A(0,S(0))}}))}
     → r 1 S ( S ( A ( S ( 0 ) , 0 ) _ ) ) {\displaystyle \rightarrow _{r1}S(S({\underline {A(S(0),0)}}))}      → r 1 A ( 0 , A ( 0 , S ( S ( 0 ) ) ) _ ) {\displaystyle \rightarrow _{r1}A(0,{\underline {A(0,S(S(0)))}})}
     → r 2 S ( S ( A ( 0 , S ( 0 ) ) _ ) ) {\displaystyle \rightarrow _{r2}S(S({\underline {A(0,S(0))}}))}      → r 1 A ( 0 , S ( S ( S ( 0 ) ) ) ) _ {\displaystyle \rightarrow _{r1}{\underline {A(0,S(S(S(0))))}}}
     → r 1 S ( S ( S ( S ( 0 ) ) ) ) {\displaystyle \rightarrow _{r1}S(S(S(S(0))))}      → r 1 S ( S ( S ( S ( 0 ) ) ) ) {\displaystyle \rightarrow _{r1}S(S(S(S(0))))}

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

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

(r1) 0 , n → ( n + 1 ) (r2) ( m + 1 ) , 0 → m , 1 (r3) ( m + 1 ) , ( n + 1 ) → m , ( m + 1 ) , n {\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}}}

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

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

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

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

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

Замечания

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

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

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

(r4) A ( S ( 0 ) , 0 , n ) → S ( n ) (r5) A ( S ( 0 ) , S ( m ) , n ) → A ( S ( n ) , m , S ( 0 ) ) (r6) A ( S ( S ( x ) ) , m , n ) → A ( S ( 0 ) , m , A ( S ( x ) , m , n ) ) {\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 можно определить

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

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

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

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

(r4) 1 , 0 , n → ( n + 1 ) (r5) 1 , ( m + 1 ) , n → ( n + 1 ) , m , 1 (r6) ( x + 2 ) , m , n → 1 , m , ( x + 1 ) , m , n {\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}}}

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

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

Пример

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

1 , 2 , 1 _ → r 5 2 , 1 , 1 _ → r 6 1 , 1 , 1 , 1 , 1 _ → r 5 1 , 1 , 2 , 0 , 1 _ → r 6 1 , 1 , 1 , 0 , 1 , 0 , 1 _ → r 4 1 , 1 , 1 , 0 , 2 _ → r 4 1 , 1 , 3 _ → r 5 4 , 0 , 1 _ → r 6 1 , 0 , 3 , 0 , 1 _ → r 6 1 , 0 , 1 , 0 , 2 , 0 , 1 _ → r 6 1 , 0 , 1 , 0 , 1 , 0 , 1 , 0 , 1 _ → r 4 1 , 0 , 1 , 0 , 1 , 0 , 2 _ → r 4 1 , 0 , 1 , 0 , 3 _ → r 4 1 , 0 , 4 _ → r 4 5 {\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}}}

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

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

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

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

1 , 2 , 1 _ → r 5 2 , 1 , 1 _ → r 7 1 , 1 , 1 , 1 , 1 _ → r 5 1 , 1 , 2 , 0 , 1 _ → r 7 1 , 1 , 1 , 0 , 1 , 0 , 1 _ → r 4 1 , 1 , 1 , 0 , 2 _ → r 4 1 , 1 , 3 _ → r 5 4 , 0 , 1 _ → r 7 3 , 0 , 1 , 0 , 1 _ → r 4 3 , 0 , 2 _ → r 7 2 , 0 , 1 , 0 , 2 _ → r 4 2 , 0 , 3 _ → r 7 1 , 0 , 1 , 0 , 3 _ → r 4 1 , 0 , 4 _ → r 4 5 {\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}}}

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

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

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

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

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

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

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

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

(b1) F ( S ( 0 ) , 0 , n ) → S ( n ) (b2) F ( S ( 0 ) , S ( 0 ) , 0 ) → S ( S ( 0 ) ) (b3) F ( S ( 0 ) , S ( S ( 0 ) ) , 0 ) → 0 (b4) F ( S ( 0 ) , S ( S ( S ( m ) ) ) , 0 ) → S ( 0 ) (b5) F ( S ( 0 ) , S ( m ) , S ( n ) ) → F ( S ( n ) , m , F ( S ( 0 ) , S ( m ) , 0 ) ) (b6) F ( S ( S ( x ) ) , m , n ) → F ( S ( 0 ) , m , F ( S ( x ) , 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 можно определить правило

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

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

(r8) A ( 0 , n ) → S ( n ) (r9) A ( S ( m ) , n ) → P ( F ( S ( 0 ) , S ( m ) , S ( S ( S ( n ) ) ) ) ) (r10) P ( S ( S ( S ( m ) ) ) ) → m {\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).

Пример

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

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

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

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

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

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

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 ) ) ) ) ⋮ → A ( 3 , A ( 3 , A ( 3 , 13 ) ) ) ⋮ → A ( 3 , A ( 3 , 65533 ) ) ⋮ → A ( 3 , 2 65536 − 3 ) ⋮ → 2 2 65536 − 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» в предыдущей строке. Вот небольшая верхняя левая часть таблицы:

Значения A ( m ,  n )
н
м
01234н
012345 n + 1 {\displaystyle n+1}
123456 n + 2 = 2 + ( n + 3 ) − 3 {\displaystyle n+2=2+(n+3)-3}
2357911 2 n + 3 = 2 ⋅ ( n + 3 ) − 3 {\displaystyle 2n+3=2\cdot (n+3)-3}
35132961125 2 ( n + 3 ) − 3 {\displaystyle 2^{(n+3)}-3}
413655332 65536  − 3 2 2 65536 − 3 {\displaystyle {2^{2^{65536}}}-3} 2 2 2 65536 − 3 {\displaystyle {2^{2^{2^{65536}}}}-3} 2 2 ⋅ ⋅ ⋅ 2 ⏟ n + 3 − 3 {\displaystyle {\begin{matrix}\underbrace {{2^{2}}^{{\cdot }^{{\cdot }^{{\cdot }^{2}}}}} _{n+3}-3\end{matrix}}}
= 2 2 2 − 3 {\displaystyle ={2^{2^{2}}}-3}
= 2 ↑↑ 3 − 3 {\displaystyle =2\uparrow \uparrow 3-3} 		= 2 2 2 2 − 3 {\displaystyle ={2^{2^{2^{2}}}}-3}
= 2 ↑↑ 4 − 3 {\displaystyle =2\uparrow \uparrow 4-3} 		= 2 2 2 2 2 − 3 {\displaystyle ={2^{2^{2^{2^{2}}}}}-3}
= 2 ↑↑ 5 − 3 {\displaystyle =2\uparrow \uparrow 5-3} 		= 2 2 2 2 2 2 − 3 {\displaystyle ={2^{2^{2^{2^{2^{2}}}}}}-3}
= 2 ↑↑ 6 − 3 {\displaystyle =2\uparrow \uparrow 6-3} 		= 2 2 2 2 2 2 2 − 3 {\displaystyle ={2^{2^{2^{2^{2^{2^{2}}}}}}}-3}
= 2 ↑↑ 7 − 3 {\displaystyle =2\uparrow \uparrow 7-3}
= 2 ↑↑ ( n + 3 ) − 3 {\displaystyle =2\uparrow \uparrow (n+3)-3}
565533
= 2 ↑↑ ( 2 ↑↑ 2 ) − 3 {\displaystyle =2\uparrow \uparrow (2\uparrow \uparrow 2)-3}
= 2 ↑↑↑ 3 − 3 {\displaystyle =2\uparrow \uparrow \uparrow 3-3} 		2 ↑↑↑ 4 − 3 {\displaystyle 2\uparrow \uparrow \uparrow 4-3} 2 ↑↑↑ 5 − 3 {\displaystyle 2\uparrow \uparrow \uparrow 5-3} 2 ↑↑↑ 6 − 3 {\displaystyle 2\uparrow \uparrow \uparrow 6-3} 2 ↑↑↑ 7 − 3 {\displaystyle 2\uparrow \uparrow \uparrow 7-3} 2 ↑↑↑ ( n + 3 ) − 3 {\displaystyle 2\uparrow \uparrow \uparrow (n+3)-3}
6 2 ↑↑↑↑ 3 − 3 {\displaystyle 2\uparrow \uparrow \uparrow \uparrow 3-3} 2 ↑↑↑↑ 4 − 3 {\displaystyle 2\uparrow \uparrow \uparrow \uparrow 4-3} 2 ↑↑↑↑ 5 − 3 {\displaystyle 2\uparrow \uparrow \uparrow \uparrow 5-3} 2 ↑↑↑↑ 6 − 3 {\displaystyle 2\uparrow \uparrow \uparrow \uparrow 6-3} 2 ↑↑↑↑ 7 − 3 {\displaystyle 2\uparrow \uparrow \uparrow \uparrow 7-3} 2 ↑↑↑↑ ( n + 3 ) − 3 {\displaystyle 2\uparrow \uparrow \uparrow \uparrow (n+3)-3}
м ( 2 → 3 → ( m − 2 ) ) − 3 {\displaystyle (2\to 3\to (m-2))-3} ( 2 → 4 → ( m − 2 ) ) − 3 {\displaystyle (2\to 4\to (m-2))-3} ( 2 → 5 → ( m − 2 ) ) − 3 {\displaystyle (2\to 5\to (m-2))-3} ( 2 → 6 → ( m − 2 ) ) − 3 {\displaystyle (2\to 6\to (m-2))-3} ( 2 → 7 → ( m − 2 ) ) − 3 {\displaystyle (2\to 7\to (m-2))-3} ( 2 → ( n + 3 ) → ( m − 2 ) ) − 3 {\displaystyle (2\to (n+3)\to (m-2))-3}

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

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

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

Значения A ( m ,  n )
н
м
01234н
00+11+12+13+14+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, n −1))

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

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

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

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

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

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

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

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

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

A = { f | ∃ t   ∀ x 1 ⋯ ∀ x n :   f ( x 1 , … , x n ) < A ( t , max i x i ) } {\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\}}

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

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

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

Обратный

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

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

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

α ( m , n ) = min { i ≥ 1 : A ( i , ⌊ m / n ⌋ ) ≥ log 2 ⁡ n } . {\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 2 n иногда заменяется на n , а функция floor иногда заменяется на ceiling .

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

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

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

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

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

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

В Wikifunctions есть функция Аккермана .

Примечания

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

Ссылки

  1. ^ Монин и Хинчи 2003, с. 61.
  2. ^ ab Аккерманн 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. ^ abc Бак 1963.
  11. ^ Меуссен и Зантема 1992, стр. 6.
  12. ^ Мунафо 1999a.
  13. ↑ Ричи 1965.
  14. ^ ab 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 г.) Немного учебы и программирования.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ackermann_function&oldid=1251373413"