Função de Ackermann

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

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

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 versão indexada da Notação de Knuth (para índices ≥ -2)

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 → n → m = 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×10^{7004197280000000000♠19728} e a forma decimal de A(4, 3) é grande demais para qualquer medida normal. Se nós definirmos a função f (n) = A(n, n), 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

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(m, n)

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(m, n)

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

A seguir encontram-se calculados vários valores da função de Ackermann com três argumentos $\varphi (m,n,p)$ ou ainda descrito como A(m, n, p). Repare que quando p = 0 temos o valor de m+n como resposta da função, para p = 1 temos m * n, e por fim, para p = 2 temos m^n. Os valores de p > 2 faz uma generalização da função potenciação básica. Os valores representados por um (-) representam valores não computados por serem grandes e estourarem a capacidade computacional do computador usado nos cálculos.

Valores de A(0, n, p)

n\p	0	1	2	3
0	0	0	1	0
1	1	0	0	1
2	2	0	0	0
3	3	0	0	1
4	4	0	0	0
5	5	0	0	1
6	6	0	0	0
7	7	0	0	1

Valores de A(1, n, p)

n\p	0	1	2	3
0	1	0	1	1
1	2	1	1	1
2	3	2	1	1
3	4	3	1	1
4	5	4	1	1
5	6	5	1	1
6	7	6	1	1
7	8	7	1	1

Valores de A(2, n, p)

n\p	0	1	2	3
0	2	0	1	2
1	3	2	2	4
2	4	4	4	16
3	5	6	8	65536
4	6	8	16	-
5	7	10	32	-
6	8	12	64	-
7	9	14	128	-

Valores de A(3, n, p)

n\p	0	1	2	3
0	3	0	1	3
1	4	3	3	27
2	5	6	9	-
3	6	9	27	-
4	7	12	81	-
5	8	15	242	-
6	9	18	729	-
7	10	21	2187	-

Valores de A(4, n, p)

n\p	0	1	2	3
0	4	0	1	4
1	5	4	4	256
2	6	8	16	-
3	7	12	64	-
4	8	16	256	-
5	9	20	1024	-
6	10	24	4096	-
7	11	28	16384	-

Valores de A(5, n, p)

n\p	0	1	2	3
0	5	0	1	5
1	6	5	5	3125
2	7	10	25	-
3	8	15	125	-
4	9	20	625	-
5	10	25	3125	-
6	11	30	15625	-
7	12	35	78125	-

Valores de A(6, n, p)

n\p	0	1	2	3
0	6	0	1	6
1	7	6	6	46656
2	8	12	36	-
3	9	18	216	-
4	10	24	1296	-
5	11	30	7776	-
6	12	36	46656	-
7	13	42	279936	-

Valores de A(7, n, p)

n\p	0	1	2	3
0	7	0	1	7
1	8	7	7	823543
2	9	14	49	-
3	10	21	343	-
4	11	28	2401	-
5	12	35	16807	-
6	13	42	117649	-
7	14	49	823543	-

Expansão

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

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

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

Escrito em base 10, esse número seria equivalente à 10^{6.031×107004197270000000000♠19727}.

Inversa

Sabendo que a função  f (n) = A(n, n) descrita acima cresce rapidamente, a sua função inversa, f⁻¹, 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)

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 4ⁿ⁺¹. A análise de A(3, 1) nos exemplos acima leva 16 (4²) 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×2ⁿ−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

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↑ⁿn (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 = 1¹ = 1,
• 2↑↑2 = 2↑2 = 2² = 4,
• 3↑↑↑3 = 3↑↑3↑↑3 = 3↑↑(3↑3↑3) = $3\uparrow \uparrow 3^{3^{3}}=3\uparrow \uparrow 7625597484987=\underbrace {3^{3^{3^{3^{.^{.^{.^{3}}}}}}}} _{\text{7625597484987 três}}$

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 ⁴4 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

  

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

Ligações externas

• An animated Ackermann function calculator
• Scott Aaronson, Who can name the biggest number? (1999)
• Ackermann function's. Includes a table of some values.
• Hyper-operations: Ackermann's Function and New Arithmetical Operation
• Robert Munafo's Large Numbers describes several variations on the definition of A.
• Gabriel Nivasch, Inverse Ackermann without pain on the inverse Ackermann function.
• Raimund Seidel, Understanding the inverse Ackermann function (PDF presentation).
• The Ackermann function written in different programming languages, (on Rosetta Code)
• Ackermann's Function (Archived 2009-10-24) - some study and programming by Harry J. Smith