Notação de Knuth

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita fontes confiáveis e independentes, o que compromete sua credibilidade (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:

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ção[editar | editar código-fonte]

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ências[editar | editar código-fonte]

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ção[editar | editar código-fonte]

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çõ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 é ú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ção[editar | editar código-fonte]

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 valores[editar | editar código-fonte]

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

Nós 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.

Values of = 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 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 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é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