Notação de poderes iterados de Knuth
Em matemática , a notação dos poderes iterados de Knuth é uma notação que torna possível escrever inteiros muito grandes e que foi introduzida por Donald Knuth em 1976. A ideia desta notação é baseada no conceito de exponenciação repetida, em assim como a exponenciação consiste em uma multiplicação iterada ou multiplicação de uma adição iterada.
Introdução
Repita uma função simples
A iteração de uma função simples é usada em aritmética para definir uma operação mais complexa. A partir da função sucessora , que torna possível construir inteiros naturais por incrementos sucessivos, a adição é assim definida como uma incrementação iterada:
no+b=no+1+1+⋯+1⏟ b cópias de 1{\ displaystyle {\ begin {matrix} a + b = a + \ underbrace {1 _ {} + 1+ \ dots +1} \\\ qquad \ quad \ \ b {\ mbox {cópias de}} 1 \ end {matriz}}}A multiplicação é definida como uma adição iterada:
no×b=no+no+⋯+no⏟ b cópias de no{\ displaystyle {\ begin {matrix} a \ times b = \ underbrace {a _ {} + a + \ dots + a} \\\ qquad \ quad \ \ b {\ mbox {cópias de}} a \ end { matriz}}}Da mesma forma, a exponenciação é definida como uma multiplicação iterada:
nob=no×no×⋯×no⏟ b cópias de no{\ displaystyle {\ begin {matrix} a ^ {b} = \ underbrace {a _ {} \ times a \ times \ dots \ times a} \\\ qquad \ b {\ mbox {cópias de}} a \ end {matriz}}}
Generalização
Partindo do incremento como operação primitiva, as iterações sucessivas permitem definir primeiro a adição, depois a multiplicação e depois a exponenciação. Knuth queria generalizar esse princípio; para isso, ele introduziu uma nova notação para exponenciação, a seta para cima :
no↑b=nob{\ displaystyle a \ uparrow b = a ^ {b}}que ele pode, assim, generalizar, usando a seta dupla para exponenciação iterada - que ele chama de tetração :
no↑↑b=no↑no↑⋯↑no⏟=nono...no b cópias de no{\ displaystyle {\ begin {matrix} a \ uparrow \ uparrow b = \ underbrace {a \ uparrow a \ uparrow \ cdots \ uparrow a} = a _ {} ^ {a ^ {{} ^ {. \, ^ { . \, ^ {. \, ^ {a}}}}}} \\\ \ \ b {\ mbox {cópias de}} a \ end {matriz}}}De acordo com esta definição, obtemos:
3↑↑2=33=27{\ displaystyle 3 \ uparrow \ uparrow 2 = 3 ^ {3} = 27 \, \!}
3↑↑3=333=327=7625597484987{\ displaystyle 3 \ uparrow \ uparrow 3 = 3 ^ {3 ^ {3}} = 3 ^ {27} = 7 \, 625 \, 597 \, 484 \, 987 \, \!}
3↑↑4=3333=37625597484987{\ displaystyle 3 \ uparrow \ uparrow 4 = 3 ^ {3 ^ {3 ^ {3}}} = 3 ^ {7 \, 625 \, 597 \, 484 \, 987} \, \!}
3↑↑5=33333{\ displaystyle 3 \ uparrow \ uparrow 5 = 3 ^ {3 ^ {3 ^ {3 ^ {3}}}} \, \!}
etc.
O termo está na forma e possui dígitos, ou seja, mais do que dígitos decimais.
3↑↑4=3333{\ displaystyle 3 \ uparrow \ uparrow 4 = 3 ^ {3 ^ {3 ^ {3}}}}12580 ... 39387{\ displaystyle 12580 ... 39387}3638334640025{\ displaystyle 3 \, 638 \, 334 \, 640 \, 025}3,6×1012{\ displaystyle 3,6 \ times 10 ^ {12}}
Certamente permite que números muito grandes sejam escritos, mas Knuth não parou por aí. Ele passou a definir o operador de seta para cima triplo , que é a aplicação iterada do operador de seta para cima :
no↑↑↑b=no↑↑no↑↑⋯↑↑no⏟=no↑↑(no↑↑(⋯↑↑no))) b cópias de no{\ displaystyle {\ begin {matrix} a \ uparrow \ uparrow \ uparrow b = \ underbrace {a _ {} \ uparrow \ uparrow a \ uparrow \ uparrow \ dots \ uparrow \ uparrow a} = a _ {} \ uparrow \ uparrow (a \ uparrow \ uparrow (\ dots \ uparrow \ uparrow a))) \\\ qquad \ qquad \ \, b {\ mbox {cópias de}} a \ end {matriz}}} (operações sendo realizadas da direita para a esquerda)
então ele continuou com o operador de seta quádrupla para cima :
no↑↑↑↑b=no↑↑↑no↑↑↑⋯↑↑↑no⏟b cópias de no{\ displaystyle {\ begin {matrix} a \ uparrow \ uparrow \ uparrow \ uparrow b = \ underbrace {a _ {} \ uparrow \ uparrow \ uparrow a \ uparrow \ uparrow \ uparrow \ dots \ uparrow \ uparrow \ uparrow a} \ \\ qquad \ qquad \ quad b {\ mbox {cópias de}} a \ end {matriz}}}E assim por diante. A regra geral afirma que o operador n- setas é uma sequência de operadores ( n - 1)-setas. De forma geral,
b{\ displaystyle b}b{\ displaystyle b}
no ↑↑...↑⏟ b=no ↑...↑⏟ no ↑...↑⏟ no ... no ↑...↑⏟ no não não-1 não-1 não-1 ⏟ b cópias de no{\ displaystyle {\ 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 \ fim {matriz}}}
Comutatividade
A exponenciação não é comutativa : se aeb são diferentes, é diferente de . É o mesmo para os operadores seguintes: , , etc.
no↑b{\ displaystyle a \ uparrow b}b↑no{\ displaystyle b \ uparrow a}↑{\ displaystyle \ uparrow}↑↑{\ displaystyle \ uparrow \ uparrow}↑↑↑{\ displaystyle \ uparrow \ uparrow \ uparrow}
Parênteses e associatividade
Embora não parêntesis está escrito, os cálculos associada direito de prioridade para cada operador , , etc.
↑{\ displaystyle \ uparrow}↑↑{\ displaystyle \ uparrow \ uparrow}↑↑↑{\ displaystyle \ uparrow \ uparrow \ uparrow}
Exemplo: =3↑2↑↑3↑4{\ displaystyle 3 \ uparrow 2 \ uparrow \ uparrow 3 \ uparrow 4}3↑(2↑↑(3↑4))){\ displaystyle 3 \ uparrow (2 \ uparrow \ uparrow (3 \ uparrow 4)))}
Isso ocorre porque a exponenciação não é associativa , portanto, a ordem em que as operações são realizadas é importante. Então (ie ) não é (ie ). No exemplo acima, as operações são realizadas da direita para a esquerda, ou seja, os parênteses são associados da direita para a esquerda.
3↑(2↑3){\ displaystyle 3 \ uparrow (2 \ uparrow 3)}3↑8=6561{\ displaystyle 3 \ uparrow 8 = 6 \, 561}(3↑2)↑3{\ displaystyle (3 \ uparrow 2) \ uparrow 3}9↑3=729{\ displaystyle 9 \ uparrow 3 = 729}
Observe que em virtude das regras de potência, obtemos = = . Se alguém escolhesse a associação de prioridade à esquerda, isso traria o segundo operador elétrico de volta a uma operação de multiplicação 'simples'. O crescimento de uma potência é mais forte quando aumentamos o prazo à direita (isso está na origem da não comutatividade):
(3↑2)↑3{\ displaystyle (3 \ uparrow 2) \ uparrow 3}(3↑2)×(3↑2)×(3↑2){\ displaystyle (3 \ uparrow 2) \ times (3 \ uparrow 2) \ times (3 \ uparrow 2)}3↑(2×3){\ displaystyle 3 \ uparrow (2 \ vezes 3)}
3↑(2↑3){\ displaystyle 3 \ uparrow (2 \ uparrow 3)}= = é maior que = = .
3↑(2×2×2){\ displaystyle 3 \ uparrow (2 \ vezes 2 \ vezes 2)}3↑8{\ displaystyle 3 \ uparrow 8}(3↑2)↑3{\ displaystyle (3 \ uparrow 2) \ uparrow 3}(3×3)↑3{\ displaystyle (3 \ times 3) \ uparrow 3}9↑3{\ displaystyle 9 \ uparrow 3}
A associação é, portanto, escolhida com prioridade à direita; é a única escolha que produz um crescimento digno de um novo signo operativo.
O resultado de será, portanto, 6.561 e não 729.
3↑2↑3{\ displaystyle 3 \ uparrow 2 \ uparrow 3}
Definição de poderes iterados
Os poderes iterativos de Knuth são formalmente definidos da seguinte forma:
no↑nãob={nobE se não=11 E se b=0no↑não-1(no↑não(b-1))se não {\ displaystyle a \ uparrow ^ {n} b = \ left \ {{\ begin {matrix} a ^ {b} \ qquad \ qquad \ qquad \ qquad && {\ mbox {si}} n = 1 \ quad \\ 1 \ qquad \ qquad \ qquad \ qquad \ && {\ mbox {si}} b = 0 \ quad \, \\ a \ uparrow ^ {n-1} (a \ uparrow ^ {n} (b-1)) && {\ mbox {caso contrário}} \ \, \ end {matriz}} \ direita.}para todos os inteiros a , b e n onde b ≥ 0 e n ≥ 1.
Esta família de funções pode ser definida por um programa iterativo:
function Knuth(rang: naturel; a, b: naturel) : naturel
begin
if rang = 1
then R = a^b
else begin
R := 1 (* 1 est élément neutre à droite pour l'exponentiation *)
(* Application b fois de l'opérateur à gauche "a Knuth(rang-1)" *)
for compteur := 1 to b do R := Knuth(rang-1, a, R)
end
return R
end.
ou por um programa recursivo (em Haskell, por exemplo):
(↑) :: Integer -> (Integer, Integer) -> Integer
a ↑ (1,b) = a^b
_ ↑ (_,0) = 1
a ↑ (n,b) = a ↑ (n-1,a ↑ (n,b-1))
Notas sobre pontuação
Em uma expressão a b , escrevemos o expoente b em letra maiúscula . Mas muitos ambientes, como linguagens de programação e e - mails de texto simples, não suportam esse arranjo bidimensional. Eles então propuseram uma notação linear, a ** b para Fortran e a ↑ b para outros ambientes; a seta apontando para cima sugere elevação a uma potência. Se o conjunto de caracteres não contém uma seta, o circunflexo ^ ou ambos asteriscos ** são usados.
Outra notação usada neste artigo é ↑ n para indicar um operador de seta de ordem n (onde ↑ 1 é equivalente a ↑ sozinho).
Como dissemos acima, todos esses operadores (incluindo a exponenciação clássica a ↑ b ) não são associativos e, na ausência de parênteses, devem ser associados, da direita para a esquerda, ou seja, a avaliação é feita da direita à esquerda para uma expressão que contém pelo menos dois desses operadores. Por exemplo, a ↑ b ↑ c significa a ↑ ( b ↑ c ), e não ( a ↑ b ) ↑ c que seria então escrito a ↑ ( b × c ):
3↑↑3=3↑23=333 que vale a pena 3(33)=327=7625597484987 e não (33)3=273=3(3⋅3)=39=19683.{\ displaystyle 3 \ uparrow \ uparrow 3 = 3 \ uparrow ^ {2} 3 = 3 ^ {3 ^ {3}} {\ mbox {vale}} 3 ^ {(3 ^ {3})} = 3 ^ {27} = 7 \, 625 \, 597 \, 484 \, 987 {\ text {and not}} \ left (3 ^ {3} \ right) ^ {3} = 27 ^ {3} = 3 ^ { (3 \ cdot 3)} = 3 ^ {9} = 19 \, 683.}Há um bom motivo para escolher essa avaliação da direita para a esquerda; de fato, se a escolha tivesse sido da esquerda para a direita, então a ↑↑ b significaria a ↑ ( a ↑ ( b -1)) e ↑↑ não teria sido um novo operador.
Generalizações da notação de Knuth
Alguns números são tão grandes que a notação da seta de Knuth se torna muito complicada para descrevê-los. Este é, por exemplo, o caso do número de Graham . Os hyperopérateurs ou seta em cadeia Conway podem então ser usados.
no↑nãob=hiper(no,não+2,b)=no→b→não(Knuth)(Conway){\ displaystyle {\ begin {matrix} a \ uparrow ^ {n} b && = && {\ mbox {hyper}} (a, n + 2, b) && = && a \ to b \ to n \\ {\ mbox {(Knuth)}} &&&&&&&& {\ mbox {(Conway)}} \ end {matriz}}}A seta de Knuth será usada para números pequenos em relação a estes, enquanto as setas encadeadas ou hiperoperadores serão adequados para números maiores; quando essas próprias notações tornam-se insuficientes, como é o caso por exemplo das sequências de Goodstein , ainda é possível usar a hierarquia de crescimento rápido (que é aproximadamente o mesmo que definir a notação , onde α é um número ordinal ).
no↑αb{\ displaystyle a \ uparrow ^ {\ alpha} b}
Referências
-
O incremento é o processo de adicionar um número. Por exemplo, em uma notação de inteiros por dominó (ou pedrinhas), consistiria em adicionar um dominó (ou pedrinha).1{\ displaystyle 1}
-
Continuação A014222 na Online Encyclopedia of Integer Strings .
-
Omitimos o qualificador "up".
-
"Letra maiúscula" é o termo usado na tipografia.
Bibliografia
links externos
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">