Função de Ackermann

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde Dezembro de 2012).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

Na teoria da computabilidade, a Função de Ackermann, nomeada por Wilhelm Ackermann, é um dos mais simples e recém-descobertos exemplos de uma função computável que não são funções recursivas primitivas. Todas as funções recursivas primitivas são totais e computáveis, mas a Função de Ackermann mostra que nem toda função total-computável é recursiva primitiva.

Depois que Ackermann publicou sua função (que continha três inteiros positivos como argumentos), vários autores a modificaram para atender a várias finalidades. Então, a função de Ackermann atual pode ser referenciada a uma de suas várias formas da função original. Uma das versões mais comuns, a função de Ackermann-Péter (com dois argumentos), é definida a seguir para os inteiros não negativos m e n:

 A(m, n) =
 \begin{cases}
 n+1 & \mbox{se } m = 0 \\
 A(m-1, 1) & \mbox{se } m > 0 \mbox{ e } n = 0 \\
 A(m-1, A(m, n-1)) & \mbox{se } m > 0 \mbox{ e } n > 0.
 \end{cases}

Como se pode ver, seu valor cresce rapidamente, até mesmo para pequenas entradas. Por exemplo, A(4,2) resulta em um inteiro com 19.729 dígitos.

História[editar | editar código-fonte]

No final dos anos 20, os matemáticos Gabriel Sudan e Wilhelm Ackermann, alunos de David Hilbert, estavam estudando os fundamentos da computação. Os dois levaram os créditos por terem descoberto as funções computáveis totais que não são recursivas primitivas. Sudan publicou sua própria função, menos conhecida. Logo depois, em 1928, Ackermann publicou sua função \varphi. A função de Ackermann de três argumentos, \varphi(m, n, p), é definida de tal forma que, para p = 0, 1 ou 2, ela reproduz as funções básicas de adição, multiplicação e exponenciação, como:

\varphi(m, n, 0) = m+n,
\varphi(m, n, 1) = m\cdot n,
\varphi(m, n, 2) = m^n,

e para p > 2, ela estende essas três operações básicas de modo que possa ser expresso pela Notação de Knuth como:

\varphi(m, n, p) = m\uparrow^{p - 1}(n + 1).

(Além de seu papel histórico como uma função computável não recursiva primitiva, a função original de Ackermann é vista como uma extensão das funções aritméticas básicas além da exponenciação, embora não como suas variantes, que são projetadas especificamente para esse fim, como a sequência de hiperoperação de Goodstein.

Rózsa Péter e Raphael Robinson desenvolveram, mais tarde, a versão com apenas duas variáveis da função de Ackermann, que se tornou a preferida de vários autores.

Definições e Propriedades[editar | editar código-fonte]

A função original de Ackermann com três argumentos \varphi(m, n, p) é definida recursivamente para inteiros não-negativos m, n e p:

 \varphi(m,n,p) = \begin{cases}
\varphi(m, n, 0) = m + n \\
\varphi(m, 0, 1) = 0 \\
\varphi(m, 0, 2) = 1 \\
\varphi(m, 0, p) = m &\text{ para } p > 2 \\
\varphi(m, n, p) = \varphi(m, \varphi(m, n-1, p), p - 1) &\text{ para } n > 0 \text{ e } p > 0.
\end{cases}

De suas várias versões com dois argumentos, a função de Ackermann desenvolvida por Péter e Robinson é definida para inteiros não-negativos m e n a seguir:

 A(m, n) =
\begin{cases}
n+1 & \mbox{se } m = 0 \\
A(m-1, 1) & \mbox{se } m > 0 \mbox{ e } n = 0 \\
A(m-1, A(m, n-1)) & \mbox{se } m > 0 \mbox{ e } n > 0.
\end{cases}

Pode não ser óbvio que A(m,n) sempre para. Entretanto, a recursão é limitada porque em cada iteração recursiva ou o m decresce, ou o m permanece inalterado enquanto o n diminui. A cada vez que n chega a zero, m decresce uma unidade, logo, m eventualmente chegará a zero. Porém, quando m chega a zero, não há limite de quanto n pode crescer, podendo aumentar consideravelmente.

A função de Péter-Ackermann também pode ser expressada em termos de outras versões da função original de Ackermann:

A(m, n) = 2\uparrow^{m-2} (n+3) - 3.
A parte da definição A(m, 0) = A(m-1, 1) corresponde para 2\uparrow^{m+1} 3=2\uparrow^m 4.
  • hiper-operadores:
A(m, n) = hyper(2, m, n + 3) − 3.
  • notação de Conway:
A(m, n) = (2 → (n+3) → (m − 2)) − 3 para m > 2
por isso
2 → nm = A(m+2,n-3) + 3 para n>2.
(n=1 e n=2 vai corresponder com A(m,−2) = −1 e A(m,−1) = 1, o que pode ,logicamente, ser adicionado.)

Para pequenos valores de m, como 1, 2 ou 3, a função de Ackermann cresce relativamente devagar em relação a n(no máximo exponencialmente). Para m ≥ 4, entretanto, ela cresce muito mais rápido: A(4, 2) resulta em 2×1019728 e a forma decimal de A(4, 3) é grande demais para qualquer medida normal. Se nós definirmos a função f (n) = A(nn), que incrementa tanto m quanto n ao mesmo tempo, teremos uma função com uma variável que supera toda função primitiva, incluindo funções de crescimento rápido, como as exponenciais, fatoriais, multi- e super-fatoriais e, até mesmo, as funções definidas usando a notação de Knuth.

Esse crescimento extremo pode ser explorado para mostrar que f, o que é obviamente computável em uma Máquina de Turing, logo uma função computável, cresce mais rápido que qualquer função recursiva primitiva e é, portanto, recursiva não primitiva. Numa categoria com exponenciais, usando o isomorfismo A \times B \rightarrow C \cong A \rightarrow (B \rightarrow C) (em ciência da computação, chamado de currying), a função de Ackermann pode ser definida através de recursão primitiva ao longo de funções de maior ordem:


\begin{array}{lcl}
\operatorname{Ack}(0) & = & \operatorname{Suc} \\
\operatorname{Ack}(m+1) & = & \operatorname{Iter}(\operatorname{Ack})(m)
\end{array}

Onde Suc é a função sucessor e Iter é definida como função recursiva


\begin{array}{lcl}
\operatorname{Iter}(f)(0) & = & f(1) \\
\operatorname{Iter}(f)(n+1) & = & f(\operatorname{Iter}(f)(n)).
\end{array}

Um aspecto interessante da função de Ackermann, é que as únicas operações aritméticas que ele nunca usa são adição e subtração de 1. Essa propriedade vem, exclusivamente, do "poder" da recursão ilimitada. Isso também implica que seu tempo de execução seja, pelo menos, proporcional à sua saída, que também é algo absurdamente grande.

Tabela de Valores[editar | editar código-fonte]

Calculando a função de Ackermann, ela pode ser escrita como uma tabela infinita de valores. Colocamos os números naturais na primeira linha. Para determinar um número na tabela, pegue o número imediatamente à esquerda, então olhe para o número necessário na linha anterior, na posição determinada pelo número escolhido. Se não houver número à esquerda, simplesmente olhe para a coluna "1" na linha anterior. Um exemplo da parte de cima da tabela:

Valores de A(mn)
m\n 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 = 2\cdot(n + 3) - 3
3 5 13 29 61 125 2^{(n+3)} - 3
4 13

={2^{2^{2}}}-3
65533

={2^{2^{2^{2}}}}-3
265536 − 3

={2^{2^{2^{2^{2}}}}}-3
{2^{2^{65536}}} - 3

={2^{2^{2^{2^{2^{2}}}}}}-3
{2^{2^{2^{65536}}}} - 3

={2^{2^{2^{2^{2^{2^{2}}}}}}}-3
\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\mbox{ + 3}\end{matrix}

Os números listados aqui em uma referência recursiva são grandes demais para serem descritos de outra forma. Apesar do tamanho dos números que aparecem nessa parte da tabela, alguns números ainda maiores foram definidos, como o Número de Graham.

Abaixo, temos a tabela novamente mas, dessa vez, substituindo os números pelas suas respectivas expressões da função:

Valores de A(mn)
m\n 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,A(1,1)) A(0,A(1,2)) A(0,A(1,3)) n + 2 = 2 + (n + 3) - 3
2 A(1,1) A(1,A(2,0)) A(1,A(2,1)) A(1,A(2,2)) A(1,A(2,3)) 2n + 3 = 2\cdot(n + 3) - 3
3 A(2,1) A(2,A(3,0)) A(2,A(3,1)) A(2,A(3,2)) A(2,A(3,3)) 2^{(n+3)} - 3
4 A(3,1) A(3,A(4,0)) A(3,A(4,1)) A(3,A(4,2)) A(3,A(4,3))

\begin{matrix}\underbrace{{2^2}^{{\cdot}^{{\cdot}^{{\cdot}^2}}}} - 3 \\n\mbox{ + 3}\end{matrix}

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))

Expansão[editar | editar código-fonte]

Para ver como a função de Ackermann cresce tão rapidamente, é de grande ajuda expandir algumas expressões simples usando as regras da definição original. Por exemplo, podemos avaliar completamente A(1, 2) desse jeito:

\begin{align}
A(1,2) & = A(0, A(1, 1)) \\
& = A(0, A(0, A(1, 0))) \\
& = A(0, A(0, A(0, 1))) \\
& = A(0, A(0, 2)) \\
& = A(0, 3) \\
& = 4.
\end{align}

Para demonstrar como a avaliação de A(4, 3) resulta em inúmeros passos e em um número gigantesco:

\begin{align}
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^{ \overset{65536}{} }} - 3. \\
\end{align}

Escrito em base 10, esse número seria equivalente à 106.031×1019727.

Inversa[editar | editar código-fonte]

Sabendo que a função  f (n) = A(nn) descrita acima cresce rapidamente, a sua função inversa, f−1, cresce muito devagar. Essa Função Inversa de Ackermann é normalmente notada como α. De fato, α(n) é menor que 5 para quase qualquer entrada de tamanho n, sendo A(4, 4) o número 2^{2^{10^{19729}}}.

Essa inversa aparece na complexidade de alguns algoritmos, como a estrutura de dados "Conjuntos Disjuntos" e o algoritmo de Chazelle para Árvore de extensão mínima. Uma variação da função inversa de Ackermann pode ser definida do seguinte jeito, sendo \lfloor x \rfloor a função chão:

\alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}.

Essa função aparece em análises mais precisas dos algoritmos mencionados acima e dá um limite de tempo mais preciso.

Uso como Referência(Benchmark)[editar | editar código-fonte]

Devido à sua definição em termos de recursão extremamente profunda, a função de Ackermann pode ser usada como um teste de otimização de recursões para compiladores. O primeiro uso da função para esse princípio, foi feito por Yngve Sundblad, em The Ackermann function. A Theoretical, computational and formula manipulative study. (BIT 11 (1971), 107119).

Por exemplo, um compilador que, durante a análise de A(3, 30) é capaz de guardar valores como A(3, n) e A(2, n) ao invés de recalcula-los, pode acelerar o processo de A(3, 30) numa ordem de cem milhões(100.000.000.000). Além disso, se A(2, n) é calculado diretamente em vez de uma expansão recursiva como A(1, A(1, A(1,...A(1, 0)...))), isso vai poupar uma quantia significativa de tempo. Computar A(1, n) requer tempo linear n. Computar A(2, n) requer tempo quadrático, uma vez que ele expande para O(n) chamadas de A(1, i) para vários i`s. Computar A(3, n) requer tempo proporcional a 4n+1. A análise de A(3, 1) nos exemplos acima leva 16 (42) steps.

A(4, 2) não pode, eventualmente, ser computada simplesmente através da aplicação recursiva da função de Ackermann em tempo tratável. Em vez disso, "fórmulas de atalho" como A(3, n) = 8×2n−3 são utilizados como uma otimização para completar algumas das chamadas recursivas.

Um método prático de computar funções similares à de Ackermann é guardar os resultados intermediários. Um compilador pode utilizar dessa técnica para uma função automaticamente usando as funções de Donald Michie.

Números de Ackermann[editar | editar código-fonte]

No livro The Book of Numbers, John Horton Conway e Richard K. Guy definem a sequência dos Números de Ackermann como 1↑1, 2↑↑2, 3↑↑↑3, etc. Isto é, o n-ésimo número de Ackermann é definido como n↑nn (n = 1, 2, 3, ...), onde m↑kn é a versão de Knuth da função de Ackermann.

Os três primeiros números de Ackermann são:

  • 1↑1 = 11 = 1,
  • 2↑↑2 = 2↑2 = 22 = 4,
  • 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑(3↑3↑3) = 3\uparrow\uparrow3^{3^3} = 3\uparrow\uparrow7625597484987 = \underbrace{3^{3^{3^{3^{.^{.^{.^{3}}}}}}}}_{7625597484987{\rm\ tres}}

O quarto número de Ackermann, 4↑↑↑↑4, pode ser escrito em termos da tetração, como segue:

4↑↑↑↑4 = 4↑↑↑4↑↑↑4↑↑↑4 = 4↑↑↑4↑↑↑(4↑↑4↑↑4↑↑4)
 = \underbrace{~~^{^{^{^{^{^{^{^{4}.}.}.}4}4}4}4}4~~}_{\underbrace{~^{^{^{^{^{4}.}.}.}4}4~}_{^{^{^{^4}4}4}4 {\rm\ quatros}} {\rm quatros}}

Na camada do meio, existe uma tetração cuja altura é ^{^{^{^4}4}4}4 e o resultado final é a camada superior de 4`s tetrados, onde sua altura é o cálculo da camada do meio. Note que, através dessa comparação, a expressão 44 já passa de um Googolplex (10^{(10^{100})}), logo, apenas o quarto número de Ackermann já é absurdamente grande. De maneira alternativa, ele pode ser reescrito como uma exponenciação como:

4\uparrow\uparrow\uparrow\uparrow 4 =
\quad

\left.
\begin{matrix} 4^{4^{\cdot^{\cdot^{\cdot^{\cdot^{4}}}}}}\end{matrix}
\right \}
\left.
\begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{4}}}}}\end{matrix}
\right \}
\dots
\left.
\begin{matrix}4^{4^{4^4}}\end{matrix}
\right \}
4,
onde o número de "torres" na linha anterior (incluindo o "4" mais à direita) é

\left.
\begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{\cdot^{4}}}}}}\end{matrix}
\right \}
\left.
\begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{4}}}}}\end{matrix}
\right \}
\dots
\left.
\begin{matrix}4^{4^{4^4}}\end{matrix}
\right \}
4,
onde o número de "torres" na linha anterior (incluindo o "4" mais à direita) é

\left.
\begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{4}}}}}\end{matrix}
\right \}
\left.
\begin{matrix}4^{4^{\cdot^{\cdot^{\cdot^{4}}}}}\end{matrix}
\right \}
\left.
\begin{matrix}4^{4^{4^4}}\end{matrix}
\right \}
4,

onde o número de "4"s em cada torre, em cada uma das linhas acima, é especificado pelo valor da torre seguinte à sua direita (como indicado por uma chave ")").

Código em C[editar | editar código-fonte]

 
#include <stdio.h>
#define TAM 4
int ack(int x, int y);
 
int main(){
	int i, j;
	for (i = 0; i <= TAM; i++){
		for (j = 0; j <= i; j++){
			int valor = ack(i, j);
			printf("Ack (%d, %d) = %d\n", i, j, valor);
		}
	}
	return 0;
}
 
int ack(int x, int y){
	if (x == 0){
		return y+1;
	}else if (y == 0){
		return ack(x - 1, 1);
	}else{
		int resp = ack(x, y - 1);
		return ack(x - 1, resp);
	}
}

Ligações externas[editar | editar código-fonte]