Abrir menu principal

Notação de Knuth

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çãoEditar

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:

 

Por exemplo,

 

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

 

Por exemplo,

 

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

 

Por exemplo,

 

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,

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


 

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

 

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

 

Exemplos:

 

 

A notação   é comumente usada para denotar   com n setas.

NotaçãoEditar

Em expressões tais como  , a notação para a exponenciação consiste geralmente em se escrever o expoente   como um número sobrescrito em relação ao número base  . 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   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   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   em vez disso.

Escrevendo a notação de seta para cima em termos de potênciasEditar

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

Por exemplo:  

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.

 

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

 

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

 

Além disso,   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:

 

E de forma mais geral:

 

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

Usando tetraçãoEditar

A notação de tetração   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).


 
 
 

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

 

GeneralizaçõesEditar

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  é ú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.

 

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çãoEditar

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

 

para todos inteiros   com  .

Todos os operadores de seta para cima (incluindo a exponenciação normal,  ) 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,  , e não  ; por exemplo
  é   e não  

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   seria igual a  , de modo que   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   que aparece na expansão de   como  , de forma que todos os  s aparecem como operandos à esquerda dos operadores de seta. Isto é significativo uma vez que os operadores de seta não são comutativos.

Escrevendo   para a b-ésima potência funcional da função   nós temos  .

A definição poderia ser extrapolada um passo, começando com   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 valoresEditar

A Computação de   pode ser reafirmada em termos de uma tabela infinita. Nós colocamos os números 2   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   = 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  
1 2 4 8 16 32 64 128  
2 2 4 16 65536        
3 2 4 65536          
4 2 4            

Nota:   denota uma função de potência da função   (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   e  , e um acréscimo de 3 a todos os valores.

Computando  

Nós colocamos os números 3   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   = hiper(3, m + 2, n) = 3 → n → m
m\n 1 2 3 4 5 fórmula
0 3 6 9 12 15  
1 3 9 27 81 243  
2 3 27 7.625.597.484.987      
3 3 7.625.597.484.987        
4 3          

Computando  

Colocamos os números 10   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.

Valores de   = hiper(10, m + 2, n) = 10 → n → m
m\n 1 2 3 4 5 fórmula
0 10 20 30 40 50  
1 10 100 1.000 10.000 100.000  
2 10 10.000.000.000        
3 10          
4 10          

Observe que, para 2 ≤ n ≤ 9 a ordem numérica dos números   é 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 sequência de hiperoperaçõesEditar

Goodstein [1947], com um sistema de notação diferente da notação de setas de Knuth, usou a sequência de hiperoperadores aqui denotada por   para criar sistemas de numeração para os inteiros não negativos. Deixando sobrescritos   denotando os respectivos hiperoperadores  , 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
 
onde xk, ..., x1 são os maiores números inteiros que satisfazem (no turno)
 
 
...
 .
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á  , 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  , com X também desta forma;

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

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

representações de nível-4 têm a forma  , 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   etc.; por exemplo, a representação de nível-3 base-2 do número 6 é  , que abrevia a  .

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

 
 
 
 
 .

Ver tambémEditar

Ligações externasEditar

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