Função de Ackermann

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Função de crescimento rápido

Na teoria da computabilidade, a função de Ackermann, batizada em homenagem a Wilhelm Ackermann, é um dos exemplos mais simples e descobertos mais cedo de uma função computável total que não é recursiva primitiva. Todas as funções recursivas primitivas são totais e computáveis, mas a função de Ackermann ilustra que nem todas as funções computáveis totais são recursivas primitivas. Após a publicação de sua função por Ackermann (que tinha três argumentos inteiros não negativos), muitos autores a modificaram para atender a vários propósitos, de modo que hoje "a função de Ackermann" pode se referir a qualquer uma das inúmeras variantes da função original. Uma versão comum, a função Ackermann–Péter de dois argumentos, é definida da seguinte forma para inteiros não negativos m e 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}}}

Seu valor cresce rapidamente, mesmo para pequenos insumos. Por exemplo, A(4, 2) é um número inteiro de 19.729 dígitos decimais (equivalente a 2⁶⁵⁵³⁶−3, ou 2^{2^{2^2²}}-3).

História

No final da década de 1920, os matemáticos Gabriel Sudão e Wilhelm Ackermann, estudantes de David Hilbert, estavam estudando as bases da computação. Tanto o Sudão como Ackermann são creditados com a descoberta de funções computáveis totais (terminadas simplesmente "recursivas" em algumas referências) que não são recursivas primitivas. O Sudão publicou a função menos conhecida do Sudão, logo depois e independentemente, em 1928, Ackermann publicou sua função $varphi$ (a carta grega phi). A função de três argumentos de Ackermann, ${displaystyle varphi (m,n,p)}$ , é definido tal como para ${displaystyle p=0,1,2}$ , reproduz as operações básicas de adição, multiplicação e exponencial

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

e para p > 2 ele estende essas operações básicas de uma forma que pode ser comparada às hiperoperações:

3end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">φ φ (m,n,3)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =mNão.4](n+1)φ φ (m,n,p)⪆ ⪆ mNão.p+1](n+1)parap>3{displaystyle {begin{aligned}varphi (m,n,3)&=m[4](n+1)\varphi (m,n,p)&gtrapprox m[p+1](n+1)&{text{for }}p>3end{aligned}}}3end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/55d4772652d7289170cc00951d017f5ae1c25d5b" style="vertical-align: -2.505ex; width:43.007ex; height:6.176ex;"/>

(Além de seu papel histórico como uma função recursiva total-computável-mas-não-primitiva, a função original de Ackermann estende as operações aritméticas básicas além da exponenciação, embora não tão perfeitamente quanto as variantes de Ackermann que são especificamente projetadas para esse propósito, como a sequência de hiperoperação de Goodstein.)

Em On the Infinite, David Hilbert levantou a hipótese de que a função de Ackermann não era recursiva primitiva, mas foi Ackermann, secretário pessoal de Hilbert e ex-aluno, quem realmente provou a hipótese em seu artigo Sobre a construção dos números reais de Hilbert.

Rózsa Péter e Raphael Robinson desenvolveram posteriormente uma versão de duas variáveis da função de Ackermann que se tornou preferida por quase todos os autores.

A sequência de hiperoperação generalizada, por exemplo. ${displaystyle G(m,a,b)=a[m]b}$ , é uma versão da função Ackermann também.

Em 1963 R.C. Buck baseou uma variante intuitiva de duas variáveis $operatorname {F}$ na sequência de hiperoperação:

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

Em comparação com a maioria das outras versões, a função de Buck não possui deslocamentos não essenciais:

{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=2times 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}}}

Muitas outras versões da função de Ackermann foram investigadas.

Definição

Definição: como função m-ária

Função original de três braços de Ackermann ${displaystyle varphi (m,n,p)}$ é definida recursivamente como segue para inteiros nonnegativos ${displaystyle m,n,}$ e $p$ :

2\varphi (m,n,p)&=varphi (m,varphi (m,n-1,p),p-1)&&{text{for }}n,p>0end{aligned}}}" xmlns="http://www.w3.org/1998/Math/MathML">φ φ (m,n,0)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =m+nφ φ (m,0,1)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0φ φ (m,0,2)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1φ φ (m,0,p)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =mparap>2φ φ (m,n,p)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =φ φ (m,φ φ (m,n- Sim. - Sim. 1,p),p- Sim. - Sim. 1)paran,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>0end{aligned}}}2\varphi (m,n,p)&=varphi (m,varphi (m,n-1,p),p-1)&&{text{for }}n,p>0end{aligned}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c6855f9ddb1eb08206260d704b921e4a459da030" style="vertical-align: -7.171ex; width:56.337ex; height:15.509ex;"/>

Das várias versões de dois braços, a desenvolvida por Péter e Robinson (chamado "a" função de Ackermann pela maioria dos autores) é definida para inteiros nonnegativos. $m$ e $n$ da seguinte forma:

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

A função de Ackermann também foi expressa em relação à sequência de hiperoperação:

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">A(m,n)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(n+1m= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =02Não.m](n+3)- Sim. - Sim. 3m>0{displaystyle A(m,n)={begin{cases}n+1&m=02[m](n+3)-3&m>0\end{cases}}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d74a51ad59c098733b952a52eff92e6fc38ded13" style="vertical-align: -2.505ex; width:37.945ex; height:6.176ex;"/>

ou, escrito na notação estreita de Knuth (destinado a integer índices

{displaystyle geq -2}

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(n+1m= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =02↑ ↑ m- Sim. - Sim. 2(n+3)- Sim. - Sim. 3m>0{displaystyle ={begin{cases}n+1&m=02uparrow ^{m-2}(n+3)-3&m>0\end{cases}}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d5eb19389f023dbd9efd2fa3ed9c0a69948aecc" style="vertical-align: -2.505ex; width:32.172ex; height:6.176ex;"/>

ou, equivalentemente, em termos da função de Buck F:

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(n+1m= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0F(m,n+3)- Sim. - Sim. 3m>0{displaystyle ={begin{cases}n+1&m=0F(m,n+3)-3&m>0\\end{cases}}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49184cb225696100ff333a9e9632716bb2bb4c18" style="vertical-align: -2.505ex; width:29.597ex; height:6.176ex;"/>

Definição: como função 1-ária iterada

Definir ${displaystyle f^{n}}$ como o n- o iterado de $f$ :

{displaystyle {begin{array}{rll}f^{0}(x)&=&x\f^{n+1}(x)&=&f(f^{n}(x)),,,,{{textrm {for}},,ngeq 1}end{array}}}

A iteração é o processo de compor uma função com si mesmo um certo número de vezes. A composição da função é uma operação associativa, portanto ${displaystyle f(f^{n}(x))=f^{n}(f(x))}$ .

Concebindo a função Ackermann como uma sequência de funções unárias, pode-se definir ${displaystyle operatorname {A} _{m}(n)=operatorname {A} (m,n)}$ .

A função então se torna uma sequência ${displaystyle operatorname {A} _{0},operatorname {A} _{1},operatorname {A} _{2},...}$ de funções unárias, definidas a partir da iteração:

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

Computação

A definição recursiva da função de Ackermann pode ser naturalmente transposta para um sistema de reescrita de termos (TRS).

TRS, baseado na função 2-ária

A definição da função 2-ária de Ackermann leva às óbvias regras de redução

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

Exemplo

Compute ${displaystyle A(1,2)rightarrow _{*}4}$

A sequência de redução é

Estratégia mais ocidental (um passo) de esquerda:	Estratégia mais interna (um passo):
${displaystyle {underline {A(S(0),S(S(0)))}}}$	${displaystyle {underline {A(S(0),S(S(0)))}}}$
${displaystyle rightarrow _{r3}{underline {A(0,A(S(0),S(0))}})}$	${displaystyle rightarrow _{r3}A(0,{underline {A(S(0),S(0))}})}$
${displaystyle rightarrow _{r1}S({underline {A(S(0),S(0))}})}$	${displaystyle rightarrow _{r3}A(0,A(0,{underline {A(S(0),0)}}))}$
${displaystyle rightarrow _{r3}S({underline {A(0,A(S0,0))}})}$	${displaystyle rightarrow _{r2}A(0,A(0,{underline {A(0,S(0))}}))}$
${displaystyle rightarrow _{r1}S(S({underline {A(S(0),0)}}))}$	${displaystyle rightarrow _{r1}A(0,{underline {A(0,S(S(0)))}})}$
${displaystyle rightarrow _{r2}S(S({underline {A(0,S(0))}}))}$	${displaystyle rightarrow _{r1}{underline {A(0,S(S(S(0))))}}}$
${displaystyle rightarrow _{r1}S(S(S(S(0))))}$	${displaystyle rightarrow _{r1}S(S(S(S(0))))}$

Para calcular ${displaystyle operatorname {A} (m,n)}$ pode-se usar uma pilha, que inicialmente contém os elementos ${displaystyle langle m,nrangle }$ .

Em seguida, repetidamente, os dois elementos superiores são substituídos de acordo com as regras

{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)&,&nend{array}}}

Esquematicamente, a partir de ${displaystyle langle m,nrangle }$ :

PORTUGAL stackLength  1
(
 POP 2 elementos;
 PUSH 1 ou 2 ou 3 elementos, aplicando as regras r1, r2, r3
?

O pseudocódigo é publicado em Grossman & Zeitman (1988).

Por exemplo, na entrada ${displaystyle langle 2,1rangle }$ ,

as configurações da pilha	refletir a redução
${displaystyle {underline {2,1}}}$	${displaystyle {underline {A(2,1)}}}$
${displaystyle rightarrow 1,{underline {2,0}}}$	${displaystyle rightarrow _{r1}A(1,{underline {A(2,0)}})}$
${displaystyle rightarrow 1,{underline {1,1}}}$	${displaystyle rightarrow _{r2}A(1,{underline {A(1,1)}})}$
${displaystyle rightarrow 1,0,{underline {1,0}}}$	${displaystyle rightarrow _{r3}A(1,A(0,{underline {A(1,0)}}))}$
${displaystyle rightarrow 1,0,{underline {0,1}}}$	${displaystyle rightarrow _{r2}A(1,A(0,{underline {A(0,1)}}))}$
${displaystyle rightarrow 1,{underline {0,2}}}$	${displaystyle rightarrow _{r1}A(1,{underline {A(0,2)}})}$
${displaystyle rightarrow {underline {1,3}}}$	${displaystyle rightarrow _{r1}{underline {A(1,3)}}}$
${displaystyle rightarrow 0,{underline {1,2}}}$	${displaystyle rightarrow _{r3}A(0,{underline {A(1,2)}})}$
${displaystyle rightarrow 0,0,{underline {1,1}}}$	${displaystyle rightarrow _{r3}A(0,A(0,{underline {A(1,1)}}))}$
${displaystyle rightarrow 0,0,0,{underline {1,0}}}$	${displaystyle rightarrow _{r3}A(0,A(0,A(0,{underline {A(1,0)}})))}$
${displaystyle rightarrow 0,0,0,{underline {0,1}}}$	${displaystyle rightarrow _{r2}A(0,A(0,A(0,{underline {A(0,1)}})))}$
${displaystyle rightarrow 0,0,{underline {0,2}}}$	${displaystyle rightarrow _{r1}A(0,A(0,{underline {A(0,2)}}))}$
${displaystyle rightarrow 0,{underline {0,3}}}$	${displaystyle rightarrow _{r1}A(0,{underline {A(0,3)}})}$
${displaystyle rightarrow {underline {0,4}}}$	${displaystyle rightarrow _{r1}{underline {A(0,4)}}}$
${displaystyle rightarrow 5}$	${displaystyle rightarrow _{r1}5}$

Comentários

A estratégia mais interna é implementada em 225 idiomas de computador no código Rosetta.
Para todos $m,n$ a computação de ${displaystyle A(m,n)}$ não leva mais do que ${displaystyle (A(m,n)+1)^{m}}$ passos.
Grossman & Zeitman (1988) apontou que na computação ${displaystyle operatorname {A} (m,n)}$ o comprimento máximo da pilha é ${displaystyle operatorname {A} (m,n)}$ , desde que $0}" xmlns="http://www.w3.org/1998/Math/MathML">m>0- Sim. 0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/501173910e6da8425b4e9d44a4e8643620bc2464" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;"/>$ .

Seu próprio algoritmo, inerentemente iterativo, computa

{displaystyle operatorname {A} (m,n)}

dentro de

{displaystyle {mathcal {O}}(moperatorname {A} (m,n))}

tempo e dentro

{mathcal {O}}(m)

espaço.

TRS, baseado na função 1-ária iterada

A definição das funções 1-árias iteradas de Ackermann leva a diferentes regras de redução

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

Como a composição da função é associativa, em vez da regra r6 pode-se definir

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

Como na seção anterior a computação de ${displaystyle operatorname {A} _{m}^{1}(n)}$ pode ser implementado com uma pilha.

Inicialmente a pilha contém os três elementos ${displaystyle langle 1,m,nrangle }$ .

Em seguida, repetidamente, os três elementos superiores são substituídos de acordo com as regras

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

Esquematicamente, a partir de ${displaystyle langle 1,m,nrangle }$ :

PORTUGAL stackLength  1
(
 POP 3 elementos;
 PUSH 1 ou 3 ou 5 elementos, aplicando as regras r4, r5, r6;
?

Exemplo

Na entrada ${displaystyle langle 1,2,1rangle }$ as configurações sucessivas da pilha são

{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}5end{aligned}}}

As igualdades correspondentes são

{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)=5end{aligned}}}

Quando a regra de redução r7 é usada em vez da regra r6, as substituições na pilha seguirão

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

As sucessivas configurações de pilha serão então

{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}5end{aligned}}}

As igualdades correspondentes são

{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)=5end{aligned}}}

Comentários

Em qualquer entrada dada os TRSs apresentados até agora convergem no mesmo número de passos. Eles também usam as mesmas regras de redução (nesta comparação, as regras r1, r2, r3 são consideradas "as mesmas que" as regras r4, r5, r6/r7 respectivamente). Por exemplo, a redução de ${displaystyle A(2,1)}$ converge em 14 etapas: 6 × r1, 3 × r2, 5 × r3. A redução da ${displaystyle A_{2}(1)}$ converge nas mesmas 14 etapas: 6 × r4, 3 × r5, 5 × r6/r7. O TRSs difere na ordem em que as regras de redução são aplicadas.
Quando ${displaystyle A_{i}(n)}$ é computado seguindo as regras {r4, r5, r6}, o comprimento máximo da pilha permanece abaixo ${displaystyle 2times A(i,n)}$ . Quando a regra de redução r7 é usada em vez da regra r6, o comprimento máximo da pilha é apenas ${displaystyle 2(i+2)}$ . O comprimento da pilha reflete a profundidade de recursão. Como a redução de acordo com as regras {r4, r5, r7} envolve uma profundidade máxima menor de recursão, essa computação é mais eficiente nesse sentido.

TRS, baseado em hiperoperadores

Como Sundblad (1971) — ou Porto & Matos (1980) — mostrou explicitamente, a função de Ackermann pode ser expressa em termos da sequência de hiperoperações:

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">A(m,n)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(n+1m= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =02Não.m](n+3)- Sim. - Sim. 3m>0{displaystyle A(m,n)={begin{cases}n+1&m=02[m](n+3)-3&m>0\end{cases}}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d74a51ad59c098733b952a52eff92e6fc38ded13" style="vertical-align: -2.505ex; width:37.945ex; height:6.176ex;"/>

ou, após a remoção da constante 2 da lista de parâmetros, em função da função de Buck

0\end{cases}}}" xmlns="http://www.w3.org/1998/Math/MathML">= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(n+1m= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0F(m,n+3)- Sim. - Sim. 3m>0{displaystyle ={begin{cases}n+1&m=0F(m,n+3)-3&m>0\\end{cases}}}0\end{cases}}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49184cb225696100ff333a9e9632716bb2bb4c18" style="vertical-align: -2.505ex; width:29.597ex; height:6.176ex;"/>

Função de Buck ${displaystyle operatorname {F} (m,n)=2[m]n}$ , uma variante da função Ackermann por si só, pode ser computado com as seguintes regras de redução:

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

Em vez da regra b6 pode-se definir a regra

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

Para calcular a função de Ackermann basta adicionar três regras de redução

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

Essas regras cuidam do caso base A(0,n), o alinhamento (n+3) e o fudge (-3).

Exemplo

Compute ${displaystyle A(2,1)rightarrow _{*}5}$

using reduction rule ${displaystyle {text{b7}}}$ :	using reduction rule ${displaystyle {text{b6}}}$ :
${displaystyle {underline {A(2,1)}}}$	${displaystyle {underline {A(2,1)}}}$
${displaystyle rightarrow _{r9}P({underline {F(1,2,4)}})}$	${displaystyle rightarrow _{r9}P({underline {F(1,2,4)}})}$
${displaystyle rightarrow _{b5}P(F(4,1,{underline {F(1,2,0)}}))}$	${displaystyle rightarrow _{b5}P(F(4,1,{underline {F(1,2,0)}}))}$
${displaystyle rightarrow _{b3}P({underline {F(4,1,0)}})}$	${displaystyle rightarrow _{b3}P({underline {F(4,1,0)}})}$
${displaystyle rightarrow _{b7}P(F(3,1,{underline {F(1,1,0)}}))}$	${displaystyle rightarrow _{b6}P(F(1,1,{underline {F(3,1,0)}}))}$
${displaystyle rightarrow _{b2}P({underline {F(3,1,2)}})}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,1,{underline {F(2,1,0)}})))}$
${displaystyle rightarrow _{b7}P(F(2,1,{underline {F(1,1,2)}}))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,1,F(1,1,{underline {F(1,1,0)}}))))}$
${displaystyle rightarrow _{b5}P(F(2,1,F(2,0,{underline {F(1,1,0)}})))}$	${displaystyle rightarrow _{b2}P(F(1,1,F(1,1,{underline {F(1,1,2)}})))}$
${displaystyle rightarrow _{b2}P(F(2,1,{underline {F(2,0,2)}}))}$	${displaystyle rightarrow _{b5}P(F(1,1,F(1,1,F(2,0,{underline {F(1,1,0)}}))))}$
${displaystyle rightarrow _{b7}P(F(2,1,F(1,0,{underline {F(1,0,2)}})))}$	${displaystyle rightarrow _{b2}P(F(1,1,F(1,1,{underline {F(2,0,2)}})))}$
${displaystyle rightarrow _{b1}P(F(2,1,{underline {F(1,0,3)}}))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,1,F(1,0,{underline {F(1,0,2)}}))))}$
${displaystyle rightarrow _{b1}P({underline {F(2,1,4)}})}$	${displaystyle rightarrow _{b1}P(F(1,1,F(1,1,{underline {F(1,0,3)}})))}$
${displaystyle rightarrow _{b7}P(F(1,1,{underline {F(1,1,4)}}))}$	${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(1,1,4)}}))}$
${displaystyle rightarrow _{b5}P(F(1,1,F(4,0,{underline {F(1,1,0)}})))}$	${displaystyle rightarrow _{b5}P(F(1,1,F(4,0,{underline {F(1,1,0)}})))}$
${displaystyle rightarrow _{b2}P(F(1,1,{underline {F(4,0,2)}}))}$	${displaystyle rightarrow _{b2}P(F(1,1,{underline {F(4,0,2)}}))}$
${displaystyle rightarrow _{b7}P(F(1,1,F(3,0,{underline {F(1,0,2)}})))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,0,{underline {F(3,0,2)}})))}$
${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(3,0,3)}}))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,{underline {F(2,0,2)}}))))}$
${displaystyle rightarrow _{b7}P(F(1,1,F(2,0,{underline {F(1,0,3)}})))}$	${displaystyle rightarrow _{b6}P(F(1,1,F(1,0,F(1,0,F(1,0,{underline {F(1,0,2)}})))))}$
${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(2,0,4)}}))}$	${displaystyle rightarrow _{b1}P(F(1,1,F(1,0,F(1,0,{underline {F(1,0,3)}}))))}$
${displaystyle rightarrow _{b7}P(F(1,1,F(1,0,{underline {F(1,0,4)}})))}$	${displaystyle rightarrow _{b1}P(F(1,1,F(1,0,{underline {F(1,0,4)}})))}$
${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(1,0,5)}}))}$	${displaystyle rightarrow _{b1}P(F(1,1,{underline {F(1,0,5)}}))}$
${displaystyle rightarrow _{b1}P({underline {F(1,1,6)}})}$	${displaystyle rightarrow _{b1}P({underline {F(1,1,6)}})}$
${displaystyle rightarrow _{b5}P(F(6,0,{underline {F(1,1,0)}}))}$	${displaystyle rightarrow _{b5}P(F(6,0,{underline {F(1,1,0)}}))}$
${displaystyle rightarrow _{b2}P({underline {F(6,0,2)}})}$	${displaystyle rightarrow _{b2}P({underline {F(6,0,2)}})}$
${displaystyle rightarrow _{b7}P(F(5,0,{underline {F(1,0,2)}}))}$	${displaystyle rightarrow _{b6}P(F(1,0,{underline {F(5,0,2)}}))}$
${displaystyle rightarrow _{b1}P({underline {F(5,0,3)}})}$	${displaystyle rightarrow _{b6}P(F(1,0,F(1,0,{underline {F(4,0,2)}})))}$
${displaystyle rightarrow _{b7}P(F(4,0,{underline {F(1,0,3)}}))}$	${displaystyle rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,{underline {F(3,0,2)}}))))}$
${displaystyle rightarrow _{b1}P({underline {F(4,0,4)}})}$	${displaystyle rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,{underline {F(2,0,2)}})))))}$
${displaystyle rightarrow _{b7}P(F(3,0,{underline {F(1,0,4)}}))}$	${displaystyle rightarrow _{b6}P(F(1,0,F(1,0,F(1,0,F(1,0,F(1,0,{underline {F(1,0,2)}}))))))}$
${displaystyle rightarrow _{b1}P({underline {F(3,0,5)}})}$	${displaystyle rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,F(1,0,{underline {F(1,0,3)}})))))}$
${displaystyle rightarrow _{b7}P(F(2,0,{underline {F(1,0,5)}}))}$	${displaystyle rightarrow _{b1}P(F(1,0,F(1,0,F(1,0,{underline {F(1,0,4)}}))))}$
${displaystyle rightarrow _{b1}P({underline {F(2,0,6)}})}$	${displaystyle rightarrow _{b1}P(F(1,0,F(1,0,{underline {F(1,0,5)}})))}$
${displaystyle rightarrow _{b7}P(F(1,0,{underline {F(1,0,6)}}))}$	${displaystyle rightarrow _{b1}P(F(1,0,{underline {F(1,0,6)}}))}$
${displaystyle rightarrow _{b1}P({underline {F(1,0,7)}})}$	${displaystyle rightarrow _{b1}P({underline {F(1,0,7)}})}$
${displaystyle rightarrow _{b1}{underline {P(8)}}}$	${displaystyle rightarrow _{b1}{underline {P(8)}}}$
${displaystyle rightarrow _{r10}5}$	${displaystyle rightarrow _{r10}5}$

As igualdades correspondentes são

quando o TRS com a regra de redução ${displaystyle {text{b6}}}$ é aplicado:

{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)=8end{aligned}}}

quando o TRS com a regra de redução ${displaystyle {text{b7}}}$ é aplicado:

{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)=8end{aligned}}}

Comentários

A computação ${displaystyle operatorname {A} _{i}(n)}$ de acordo com as regras {b1 - b5, b6, r8 - r10} é profundamente recursivo. A profundidade máxima de aninhado $F$ " ${displaystyle A(i,n)+1}$ . O culpado é a ordem em que a iteração é executada: ${displaystyle F^{n+1}(x)=F(F^{n}(x))}$ . O primeiro $F$ desaparece apenas depois que toda a sequência é desdobrada.
A computação de acordo com as regras {b1 - b5, b7, r8 - r10} é mais eficiente nesse sentido. A iteração ${displaystyle F^{n+1}(x)=F^{n}(F(x))}$ simula o loop repetido sobre um bloco de código. O aninhamento é limitado a $(i+1)$ , um nível de recursão por função iterada. Meyer & Ritchie (1967) mostrou esta correspondência.
Estas considerações dizem respeito apenas à profundidade de recursão. Qualquer forma de iterar leva ao mesmo número de etapas de redução, envolvendo as mesmas regras (quando as regras b6 e b7 são consideradas "as mesmas"). A redução da ${displaystyle A(2,1)}$ por exemplo converge em 35 etapas: 12 × b1, 4 × b2, 1 × b3, 4 × b5, 12 × b6/b7, 1 × r9, 1 × r10. O Modus iterandi apenas afeta a ordem em que as regras de redução são aplicadas.
Um ganho real de tempo de execução só pode ser alcançado por não recalcular subresultados repetidamente. A memorização é uma técnica de otimização onde os resultados das chamadas de função são armazenados em cache e retornados quando as mesmas entradas ocorrem novamente. Veja por exemplo Ward (1993). Grossman & Zeitman (1988) publicou um algoritmo de astúcia que computa ${displaystyle A(i,n)}$ dentro de ${displaystyle {mathcal {O}}(iA(i,n))}$ tempo e dentro ${displaystyle {mathcal {O}}(i)}$ espaço.

Números enormes

Para demonstrar como a computação $A(4,3)$ resulta em muitas etapas e em um grande número:

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

Tabela de valores

O cálculo da função de Ackermann pode ser reformulado em termos de uma tabela infinita. Primeiro, coloque os números naturais ao longo da linha superior. Para determinar um número na tabela, pegue o número imediatamente à esquerda. Em seguida, use esse número para procurar o número necessário na coluna fornecida por esse número e uma linha acima. Se não houver nenhum número à esquerda, basta olhar para a coluna intitulada "1" na linha anterior. Aqui está uma pequena parte superior esquerda da tabela:

Valores de A(m,n)
n m	0	1	2	3	4	n
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=2cdot (n+3)-3$
3	5	13	29 de Março	61	125	$2^{(n+3)}-3$
4	13 ${displaystyle ={2^{2^{2}}}-3}$ ${displaystyle =2uparrow uparrow 3-3}$	65533 ${displaystyle ={2^{2^{2^{2}}}}-3}$ ${displaystyle =2uparrow uparrow 4-3}$	2⁶⁵⁵³⁶- 3 ${displaystyle ={2^{2^{2^{2^{2}}}}}-3}$ ${displaystyle =2uparrow uparrow 5-3}$	${2^{2^{65536}}}-3$ ${displaystyle ={2^{2^{2^{2^{2^{2}}}}}}-3}$ ${displaystyle =2uparrow uparrow 6-3}$	${2^{2^{2^{65536}}}}-3$ ${displaystyle ={2^{2^{2^{2^{2^{2^{2}}}}}}}-3}$ ${displaystyle =2uparrow uparrow 7-3}$	${displaystyle {begin{matrix}underbrace {{2^{2}}^{{cdot }^{{cdot }^{{cdot }^{2}}}}} _{n+3}-3end{matrix}}}$ ${displaystyle =2uparrow uparrow (n+3)-3}$
5	65533 ${displaystyle =2uparrow uparrow (2uparrow uparrow 2)-3}$ ${displaystyle =2uparrow uparrow uparrow 3-3}$	$2uparrow uparrow uparrow 4-3$	$2uparrow uparrow uparrow 5-3$	$2uparrow uparrow uparrow 6-3$	$2uparrow uparrow uparrow 7-3$	$2uparrow uparrow uparrow (n+3)-3$
6	$2uparrow uparrow uparrow uparrow 3-3$	$2uparrow uparrow uparrow uparrow 4-3$	$2uparrow uparrow uparrow uparrow 5-3$	$2uparrow uparrow uparrow uparrow 6-3$	$2uparrow uparrow uparrow uparrow 7-3$	$2uparrow uparrow uparrow uparrow (n+3)-3$
m	${displaystyle (2to 3to (m-2))-3}$	${displaystyle (2to 4to (m-2))-3}$	${displaystyle (2to 5to (m-2))-3}$	${displaystyle (2to 6to (m-2))-3}$	${displaystyle (2to 7to (m-2))-3}$	${displaystyle (2to (n+3)to (m-2))-3}$

Os números aqui expressos apenas com exponenciação recursiva ou setas de Knuth são muito grandes e ocupariam muito espaço para anotar em dígitos decimais simples.

Apesar dos grandes valores que ocorrem nesta seção inicial da tabela, alguns números ainda maiores foram definidos, como o número de Graham, que não pode ser escrito com nenhum número pequeno de setas de Knuth. Esse número é construído com uma técnica semelhante à aplicação recursiva da função de Ackermann a si mesmo.

Esta é uma repetição da tabela acima, mas com os valores substituídos pela expressão relevante da definição da função para mostrar o padrão claramente:

Valores de A(m,n)
n m	0	1	2	3	4	n
0	0+1	1+1	2+1	3+1	4+1	n + 1
1	A(0,1)	A(0, A(1, 0) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(0, 2)	A(0, A(1, 1) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(0,3)	A(0, A(1, 2)) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(0, 4)	A(0, A(1, 3) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(0,5)	A(0, A(1 n-1)
2	A(1, 1)	A(1 A(2, 0) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(1, 3)	A(1 A(2, 1) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(1, 5)	A(1 A(2, 2)) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(1, 7)	A(1 A(2, 3) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(1, 9)	A(1 A(2 n-1)
3	A(2, 1)	A(2 A(3, 0) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(2,5)	A(2 A(3, 1) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(2, 13)	A(2 A(3, 2)) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(2, 29)	A(2 A(3, 3) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(2, 61)	A(2 A(3 n-1)
4	A(3, 1)	A(3 A(4, 0) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(3, 13)	A(3 A(4, 1) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = A(3, 65533)	A(3 A(4, 2))	A(3 A(4, 3)	A(3 A(4 n-1)
5	A(4, 1)	A(4 A(5, 0)	A(4 A(5, 1))	A(4 A(5, 2))	A(4 A(5, 3)	A(4 A(5 n-1)
6	A(5, 1)	A(5 A(6, 0)	A(5 A(6, 1))	A(5 A(6, 2))	A(5 A(6, 3)	A(5 A(6 n-1)

Propriedades

Observações gerais

Pode não ser imediatamente óbvio que a avaliação $A(m,n)$ sempre termina. No entanto, a recursão é limitada porque em cada aplicação recursiva ou $m$ diminui, ou $m$ permanece o mesmo e $n$ diminui. Cada vez que $n$ atinge zero, $m$ diminui, então $m$ eventualmente atinge zero também. (Expresso mais tecnicamente, em cada caso o par $(m,n)$ diminui na ordem lexicográfico em pares, que é uma ordem bem ordenada, assim como a ordenação de inteiros não negativos únicos; isso significa que não se pode descer na ordenação infinitamente muitas vezes na sucessão.) No entanto, quando $m$ diminui não há nenhum limite superior em quanto $n$ pode aumentar — e muitas vezes aumentará muito.
Para pequenos valores de m como 1, 2 ou 3, a função Ackermann cresce relativamente lentamente em relação a n (na maioria exponencialmente). Para ${displaystyle mgeq 4}$ , no entanto, cresce muito mais rapidamente; mesmo ${displaystyle A(4,2)}$ é cerca de 2×10.¹⁹⁷²⁸, e a expansão decimal de $A(4,3)$ é muito grande por qualquer medida típica.
Um aspecto interessante é que a única operação aritmética que ele já usa é a adição de 1. Seu poder de crescimento rápido é baseado apenas na recursão aninhada. Isso também implica que seu tempo de execução é pelo menos proporcional à sua saída, e assim também é extremamente enorme. Na realidade, para a maioria dos casos o tempo de execução é muito maior do que a saída; ver acima.
Uma versão de um único argumento ${displaystyle f(n)=A(n,n)}$ que aumenta tanto $m$ e $n$ ao mesmo tempo anula cada função recursiva primitiva, incluindo funções de crescimento muito rápido, como a função exponencial, a função fatorial, funções multi- e superfatoriais, e até funções definidas usando a notação de Knuth (exceto quando o up-arrow indexado é usado). Pode ser visto que $f(n)$ é aproximadamente comparável a ${displaystyle f_{omega }(n)}$ na hierarquia de crescimento rápido. Este crescimento extremo pode ser explorado para mostrar que $f$ que é obviamente computável em uma máquina com memória infinita, como uma máquina de Turing e assim é uma função computável, cresce mais rápido do que qualquer função recursiva primitiva e, portanto, não é recursiva primitiva.

Não recursivo primitivo

A função Ackermann cresce mais rápido do que qualquer função recursiva primitiva e, portanto, não é em si primitiva recursiva. O esboço da prova é este: uma função recursiva primitiva definida usando até k recursões deve crescer mais lento do que ${displaystyle f_{k+1}(n)}$ , a função (k+1)-th na hierarquia de crescimento rápido, mas a função Ackermann cresce pelo menos tão rápido quanto ${displaystyle f_{omega }(n)}$ .

Especificamente, mostra-se que a cada função recursiva primitiva $f(x_{1},ldotsx_{n})$ existe um inteiro não negativo $t$ tal que para todos os inteiros não negativos $x_{1},ldotsx_{n}$ ,