Notação de Knuth

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Este artigo não cita fontes confiáveis e independentes (desde Dezembro de 2012). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

Em matemática, a Notação de Knuth (em inglês:Knuth's up-arrow notation) é um método de notação para inteiros muito grandes, introduzido por Donald Knuth em 1976 . É intimamente relacionada com a função de Ackermann e, especialmente, para a seqüência de hiperoperações. A idéia é baseada no fato de que a multiplicação pode ser visto como uma adição iterada e a exponenciação como uma multiplicação iterada. Continuando desta forma se leva a exponenciação iterada (tetração) e para o restante da seqüência de hiperoperação, que é comumente denotada pela notação da seta de Knuth.

Introdução[editar | editar código-fonte]

As operações aritméticas simples de adição, multiplicação e exponenciação são naturalmente estendidas em uma seqüência de hiperoperações como segue.

Multiplicação por um número natural pode ser definida como uma adição iterada:


  \begin{matrix}
   a\times b & = & \underbrace{a+a+\dots+a} \\
   & & b\mbox{ cópias de }a
  \end{matrix}

Por exemplo,


  \begin{matrix}   4\times 3 & = & \underbrace{4+4+4} & = & 12\\
   & & 3\mbox{ cópias de }4
  \end{matrix}

Exponenciação para uma potência natural b pode ser definida como uma multiplicação iterada, denotada por Knuth por uma simples seta para cima:


  \begin{matrix}
   a\uparrow b= a^b = & \underbrace{a\times a\times\dots\times a}\\
   & b\mbox{ cópias de }a
  \end{matrix}

Por exemplo,


  \begin{matrix}
   4\uparrow 3= 4^3 = & \underbrace{4\times 4\times 4} & = & 64\\
   & 3\mbox{ cópias de }4
  \end{matrix}

Para estender a seqüência de operações para além exponenciação, Knuth definiu um operador “seta dupla” para denotar a exponenciação iterada (tetração):


  \begin{matrix}
   a\uparrow\uparrow b & = {\ ^{b}a}  = & \underbrace{a^{a^{{}^{.\,^{.\,^{.\,^a}}}}}} & 
   = & \underbrace{a\uparrow (a\uparrow(\dots\uparrow a))} 
\\  
    & & b\mbox{ cópias de }a
    & & b\mbox{ cópias de }a
  \end{matrix}

Por exemplo,


  \begin{matrix}
   4\uparrow\uparrow 3 & = {\ ^{3}4}  = & \underbrace{4^{4^4}} & 
   = & \underbrace{4\uparrow (4\uparrow 4)} & = & 4^{256} \approx 1.3\times 10^{154}
\\  
    & & 3\mbox{ cópias de }4
    & & 3\mbox{ cópias de }4
  \end{matrix}

Aqui e abaixo a avaliação é para ser realizada da direita para a esquerda, uma vez que os operadores de seta de Knuth (como exponenciação) são definidos para serem associativos à direita.

Segundo esta definição,

3\uparrow\uparrow2=3^3=27
3\uparrow\uparrow3=3^{3^3}=3^{27}=7.625.597.484.987
3\uparrow\uparrow4=3^{3^{3^3}}=3^{7625597484987}
3\uparrow\uparrow5=3^{3^{3^{3^3}}} = 3^{3^{7625597484987}}
etc.

Isso já leva a alguns números bastante grandes, mas Knuth estendeu a notação. Ele passou a definir um operador de seta "tripla" para a aplicação iterada do operador de seta dupla (também conhecido como pentação):



  \begin{matrix}
   a\uparrow\uparrow\uparrow b= &
    \underbrace{a_{}\uparrow\uparrow (a\uparrow\uparrow(\dots\uparrow\uparrow a))}\\
    & b\mbox{ cópias de }a
  \end{matrix}

seguido por um operador de 'seta quádrupla':


  \begin{matrix}
   a\uparrow\uparrow\uparrow\uparrow b= &
    \underbrace{a_{}\uparrow\uparrow\uparrow (a\uparrow\uparrow\uparrow(\dots\uparrow\uparrow\uparrow a))}\\
    & b\mbox{ cópias de }a
  \end{matrix}

e assim por diante. A regra geral é que um operador-n seta expande-se em uma série associativa à direita de (n - 1)-operadores seta. Simbolicamente,


  \begin{matrix}
   a\ \underbrace{\uparrow_{}\uparrow\!\!\dots\!\!\uparrow}\ b=
    a\ \underbrace{\uparrow\!\!\dots\!\!\uparrow}
    \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}
    \ a\ \dots
    \ a\ \underbrace{\uparrow_{}\!\!\dots\!\!\uparrow}
    \ a
  \\
   \quad\ \ \,n\qquad\ \ \ \underbrace{\quad n_{}\!-\!\!1\quad\ \,n\!-\!\!1\qquad\quad\ \ \ \,n\!-\!\!1\ \ \ }
  \\
   \qquad\qquad\quad\ \ b\mbox{ cópias de }a
  \end{matrix}

Exemplos:

3\uparrow\uparrow\uparrow2 = 3\uparrow\uparrow3 = 3^{3^3} = 3^{27}=7.625.597.484.987


  \begin{matrix}
    3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow3\uparrow3) = &
    \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\
   & 3\uparrow3\uparrow3\mbox{ cópias de }3
  \end{matrix}
  \begin{matrix}
   = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\
   & \mbox{7.625.597.484.987 cópias de 3}
  \end{matrix}

A notação a \uparrow^n b é comumente usada para denotar a \uparrow\uparrow \dots \uparrow b com n setas.

Notação[editar | editar código-fonte]

Em expressões tais como a^b, a notação para a exponenciação consiste geralmente em se escrever o expoente b como um número sobrescrito em relação ao número base a. Mas muitos ambientes — tais como nos fontes de linguagens de programação e em textos em formato de texto simples como mensagens de e-mail - não dispõe deste formato bidimensional. As pessoas adotaram a notação linear a \uparrow b para tais ambientes, a seta para cima sugere 'elevar à potência'. Se o conjunto de caracteres não contém uma seta para cima, o acento circunflexo ^ é usado em seu lugar.

A notação sobrescrita a^b não se presta bem a generalização, o que explica a razão de Knuth optar por trabalhar a partir da notação cursiva a \uparrow b em vez disso.

Escrevendo a notação de seta para cima em termos de potências[editar | editar código-fonte]

A tentativa de se escrever a \uparrow \uparrow b usando a notação familiar com números sobrescritos resulta em uma torre de potências.

Por exemplo: a \uparrow \uparrow 4 = a \uparrow a \uparrow a \uparrow a = a^{a^{a^a}}

Se b é uma variável (ou é muito grande), a torre de potências pode ser escrita usando pontos e uma nota indicando a altura da torre.

a \uparrow \uparrow b = \underbrace{a^{a^{.^{.^{.{a}}}}}}_{b}

Continuando com esta notação, a \uparrow \uparrow \uparrow b poderia ser escrita com uma pilha destas torres de potências, cada uma descrevendo o tamanho daquela que está acima de si.

a \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow a \uparrow \uparrow a \uparrow \uparrow a = 
  \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{a} }}

Novamente, se b é uma variável ou é muito grande, a pilha pode ser escrita usando pontos e uma nota indicando a sua altura.

a \uparrow \uparrow \uparrow b = 
  \left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\} b

Além disso, a \uparrow \uparrow \uparrow \uparrow b pode ser escrito usando-se várias colunas destas pilhas como torres de potências, cada coluna descrevendo o número de torres de potências na pilha à sua esquerda:

a \uparrow \uparrow \uparrow \uparrow 4 = a \uparrow \uparrow \uparrow a \uparrow \uparrow \uparrow a \uparrow \uparrow \uparrow a = 
  \left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                     \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                     \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                     a

E de forma mais geral:

a \uparrow \uparrow \uparrow \uparrow b = 
  \underbrace{
    \left.\left.\left. \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                       \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{a^{a^{.^{.^{.{a}}}}}}_{ \underbrace{\vdots}_{a} }} \right\}
                       \cdots \right\}
                       a
  }_{b}

Isso pode ser realizado indefinidamente para representar a \uparrow^n b como uma exponenciação iterada de exponenciações iteradas para qualquer a,n e b(embora ele torna-se claramente bastante pesado).

Usando tetração[editar | editar código-fonte]

A notação de tetração ^{b}a nos permite fazer estes diagramas de forma um pouco mais simples, ainda empregando uma representação geométrica (que poderíamos chamar estas de torres de tetração).


 a \uparrow \uparrow b = ^{b}a
 a \uparrow \uparrow \uparrow b = \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{b}
 a \uparrow \uparrow \uparrow \uparrow b = 
   \left. \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{^{^{^{^{^{a}.}.}.}a}a}_{ \underbrace{\vdots}_{a} }} \right\} b

Finalmente, a título de exemplo, o quarto número de Ackermann 4 \uparrow^4 4 poderia ser representado como:

\underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{4} }} = 
        \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ \underbrace{^{^{^{^{^{4}.}.}.}4}4}_{ ^{^{^{4}4}4}4 }}

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

Alguns números são tão grandes que o uso de várias setas da notação de seta para cima de Knuth torna-se demasiado pesado; então um operador n-seta\uparrow^n é útil (e também para as descrições com um número variável de setas), ou de forma equivalente, hiper operadores.

Alguns números são tão grandes que até mesmo esta notação não é suficiente. O número de Graham é um exemplo. A Notação de seta encadeada de Conway pode ser usada: uma cadeia de três elementos é equivalente ao de outras notações, mas uma cadeia de quatro ou mais é ainda mais poderosa.


  \begin{matrix}
   a\uparrow^n b & = & \mbox{hyper}(a,n+2,b) & = & a\to b\to n \\
   \mbox{(Knuth)} & & & & \mbox{(Conway)}
  \end{matrix}

Em geral, é sugerido que a seta de Knuth deva ser usada para números de menor magnitude, e a seta encadeada de Conway ou hiper operadores para os de maior magnitude.

Definição[editar | editar código-fonte]

A notação de seta para cima é formalmente definida por


  a\uparrow^n b=
  \left\{
   \begin{matrix}
    a^b, & \mbox{se }n=1; \\
    1, & \mbox{se }b=0; \\
    a\uparrow^{n-1}(a\uparrow^n(b-1)), & \mbox{em outro caso}
   \end{matrix}
  \right.

para todos inteiros a, b, n com b \ge 0, n \ge 1.

Todos os operadores de seta para cima (incluindo a exponenciação normal, a \uparrow b) são associativos à direita, ou seja, a avaliação é realizada da direita para a esquerda em uma expressão que contém dois ou mais desses operadores. Por exemplo, a \uparrow b \uparrow c = a \uparrow (b \uparrow c), e não (a \uparrow b) \uparrow c; por exemplo
3\uparrow\uparrow 3=3^{3^3} é 3^{(3^3)}=3^{27}=7625597484987 e não \left(3^3\right)^3=27^3=19683.

Há uma boa razão para a escolha desta ordem de avaliação da direita para à esquerda. Se usássemos a avaliação da esquerda para a direita, então a \uparrow\uparrow b seria igual a a \uparrow (a \uparrow (b - 1)), de modo que \uparrow\uparrow não seria uma operação essencialmente nova. A associatividade à direita também é natural porque nós podemos reescrever a expressão de seta iterada a\uparrow^n\cdots\uparrow^na que aparece na expansão de a \uparrow^{n + 1}b como a\uparrow^n\cdots\uparrow^na\uparrow^n1, de forma que todos os as aparecem como operandos à esquerda dos operadores de seta. Isto é significativo uma vez que os operadores de seta não são comutativos.

Escrevendo (a\uparrow ^m)^b para a b-ésima potência funcional da função f(x)=a\uparrow ^m x nós temos a\uparrow ^n b = (a\uparrow ^{n-1})^b 1.

A definição poderia ser extrapolada um passo, começando com a\uparrow^n b=    ab se n = 0, porque exponenciação é uma multiplicação repetida iniciando em 1. Extrapolando mais um passo, escrevendo a multiplicação como uma adição repetida, não é tão simples, porque a multiplicação é a adição repetida a partir de 0 ao invés de 1. "Extrapolando" novamente um passo a mais, além de escrever n como adições repetidas de 1, se requer o começo com o número a. Compare com a definição de operador hiperoperador, onde os valores de partida para a adição e multiplicação também são especificados separadamente.

Tabelas de valores[editar | editar código-fonte]

A Computação de 2\uparrow^m n pode ser reafirmada em termos de uma tabela infinita. Nós colocamos os números 2 n na linha superior, e preenchemos a coluna da esquerda com valores 2. Para determinar um número na tabela, pegamos o número imediatamente à esquerda, em seguida, procuramos o número necessário na linha anterior, na posição dada pelo número acabamos de tomar.

Valores de 2\uparrow^m n = hiper(2, m + 2, n) = 2 → n → m
m\n 1 2 3 4 5 6 7 formula
0 2 4 6 8 10 12 14 2n
1 2 4 8 16 32 64 128 2^n
2 2 4 16 65536 2^{65536}\approx 2.0 \times 10^{19,729} 2^{2^{65536}}\approx 10^{6.0 \times 10^{19,728}} 2^{2^{2^{65536}}}\approx 10^{10^{6.0 \times 10^{19,728}}} 2\uparrow\uparrow n
3 2 4 65536 
  \begin{matrix}
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}} \\
   65536\mbox{ cópias de }2  \end{matrix}\approx (10\uparrow)^{65531}(6.0 \times 10^{19,728})
      2\uparrow\uparrow\uparrow n
4 2 4 
  \begin{matrix}
   \underbrace{2_{}^{2^{{}^{.\,^{.\,^{.\,^2}}}}}}\\
   65536\mbox{ cópias de }2
  \end{matrix}         2\uparrow\uparrow\uparrow\uparrow n

Nota: (10\uparrow)^k denota uma função de potência da função f(n)=10^n (A função também é expressa pelo sufixo-plex como em googolplex).

A tabela é a mesma que a da função de Ackermann, com exceção de uma mudança em m e n, e um acréscimo de 3 a todos os valores.

Computando 3\uparrow^m n

Nós colocamos os números 3 n na linha superior, e preenchemos a coluna da esquerda com valores 3. Para determinar um número na tabela, pegue o número imediatamente à esquerda, em seguida, procura-se o número necessário na linha anterior, na posição dada pelo número acabado de tomar.

Valores de 3\uparrow^m n = hiper(3, m + 2, n) = 3 → n → m
m\n 1 2 3 4 5 fórmula
0 3 6 9 12 15 3n
1 3 9 27 81 243 3^n
2 3 27 7.625.597.484.987 3^{7.625.597.484.987}   3\uparrow\uparrow n
3 3 7.625.597.484.987 
  \begin{matrix}
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\
   7.625.597.484.987\mbox{ cópias de }3
  \end{matrix}     3\uparrow\uparrow\uparrow n
4 3 \begin{matrix}
   \underbrace{3_{}^{3^{{}^{.\,^{.\,^{.\,^3}}}}}}\\
   7.625.597.484.987\mbox{ cópias de }3
  \end{matrix}       3\uparrow\uparrow\uparrow\uparrow n

Computando 10\uparrow^m n

Nós colocamos os números 10 n na linha superior, e preenchemos a coluna da esquerda com valores 10. Para determinar um número na tabela, se pega o número imediatamente à esquerda, em seguida, procura-se o número necessário na linha anterior, na posição dada pelo número que se acabou de tomar.

Values of 10\uparrow^m n = hiper(10, m + 2, n) = 10 → n → m
m\n 1 2 3 4 5 fórmula
0 10 20 30 40 50 10n
1 10 100 1.000 10.000 100.000 10^n
2 10 10.000.000.000 10^{10.000.000.000} 10^{10^{10.000.000.000}} 10^{10^{10^{10.000.000.000}}} 10\uparrow\uparrow n
3 10 
  \begin{matrix}
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   10\mbox{ cópias de }10
  \end{matrix} 
  \begin{matrix}
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   10^{10}\mbox{ cópias de }10
  \end{matrix} 
  \begin{matrix}
   \underbrace{10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}}\\
   10^{10^{10}}\mbox{ cópias de }10
  \end{matrix}   10\uparrow\uparrow\uparrow n
4 10 
  \begin{matrix}
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   10\mbox{ cópias de }10
  \end{matrix} 
  \begin{matrix}
   \underbrace{^{^{^{^{^{10}.}.}.}10}10}\\
   10^{10}\mbox{ cópias de }10
  \end{matrix}     10\uparrow\uparrow\uparrow\uparrow n

Observe que, para 2 ≤ n ≤ 9 a ordem numérica dos números 10\uparrow^m n é a ordem lexicográfica com m como o número mais significativo, assim, para os números dessas 8 colunas a ordem numérica é simplesmente linha por linha. O mesmo se aplica para os números das 97 colunas com 3 ≤ n ≤ 99, e se começarmos a partir de m = 1, mesmo para 3 ≤ n ≤ 9.999.999.999.

Sistemas de Numeração com base na seqüência de hiperoperações[editar | editar código-fonte]

Goodstein [1947], com um sistema de notação diferente da notação de setas de Knuth, usou a seqüência de hiperoperadores aqui denotada por ( +, \ \times, \ \uparrow, \ \uparrow\uparrow, \ \dots)\,\! para criar sistemas de numeração para os inteiros não negativos. Deixando sobrescritos  \quad ( ^{(1)}, \ ^{(2)}, \ ^{(3)}, \ ^{(4)}, \ \dots )\,\! denotando os respectivos hiperoperadores ( +, \ \times, \ \uparrow, \ \uparrow\uparrow, \ \dots)\,\!, a assim chamada representação hereditária completa do inteiro n, ao nível k e base b, pode ser expresso da seguinte forma usando apenas os k primeiros hiperoperadores e utilizando-se como dígitos apenas 0, 1, ...,b-1:

  • Para 0 ≤ nb-1, n é representado simplesmente por o dígito correspondente.
  • Para n > b-1, a representação de n é encontrada de forma recursiva, em primeiro lugar representando n na forma
b^{(k)}{x_k}^{(k-1)}{x_{k-1}}^{(k-2)} \dots {x_2}^{(1)}x_1
onde xk, ..., x1 são os maiores números inteiros que satisfazem (no turno)
b^{(k)}x_k \le n
b^{(k)}{x_k}^{(k-1)}x_{k-1} \le n
...
b^{(k)}{x_k}^{(k-1)}{x_{k-1}}^{(k-2)} \dots {x_2}^{(1)}x_1 \le n.
Qualquer xi excedendo b-1 é então re-expressado da mesma forma, e assim por diante, repetindo este procedimento até que a forma resultante contenha apenas os dígitos 0, 1, ..., b-1.

O restante desta seção usará ( +, \ \times, \ \uparrow, \ \uparrow\uparrow, \ \uparrow\uparrow\uparrow, \ \dots), ao invés de sobrescritos, para denotar o hiperoperadores.

Parênteses desnecessários podem ser evitados, dando maior precedência para operadores de maior nível na ordem de avaliação; assim,

representações de nível-1 têm a forma b + X, com X também desta forma;

representações de nível-2 têm a forma b \times X + Y, com X,Y também desta forma;

representações de nível-3 têm a forma b \uparrow X \times Y + Z, com X,Y,Z também desta forma;

representações de nível-4 têm a forma b \uparrow\uparrow X \uparrow Y \times Z + T, com X,Y,Z,T também desta forma;

e assim por diante.

As representações podem ser abreviadas, omitindo-se todas as instâncias de +0, \ \times1, \uparrow1, \ \uparrow\uparrow1, etc.; por exemplo, a representação de nível-3 base-2 do número 6 é 2\uparrow(2\uparrow1\times1+0)\times1+(2\uparrow1\times1+0), que abrevia a 2 \uparrow 2 + 2.

Exemplos: As únicas representações base-2 do número 266, nos níveis 1, 2, 3, 4, e 5 são as seguintes:

\text{Nível 1:} \ \ 266 = 2 + 2 + \dots + 2 \ \ \text{(com 133 2s)}
\text{Nível 2:} \ \ 266 = 2 \times (2 \times (2 \times (2 \times 2 \times 2 \times 2 \times 2 + 1)) + 1)
\text{Nível 3:} \ \ 266 = 2 \uparrow 2 \uparrow (2 + 1) + 2 \uparrow (2 + 1) + 2
\text{Nível 4:} \ \ 266 = 2 \uparrow\uparrow (2 + 1) \uparrow 2 + 2 \uparrow\uparrow 2 \times 2 + 2
\text{Nível 5:} \ \ 266 = 2 \uparrow\uparrow\uparrow 2 \uparrow\uparrow 2 + 2 \uparrow\uparrow\uparrow 2 \times 2 + 2.

Ver também[editar | editar código-fonte]

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

  • Knuth, Donald E., "Coping With Finiteness", Science vol. 194 n. 4271 (Dec 1976), pp. 1235–1242.
  • Robert Munafo, Large Numbers