Notação de seta em cadeia de Conway - Conway chained arrow notation

A notação de seta em cadeia de Conway , criada pelo matemático John Horton Conway , é um meio de expressar certos números extremamente grandes . É simplesmente uma sequência finita de inteiros positivos separados por setas para a direita, por exemplo . ${\ displaystyle 2 \ a 3 \ a 4 \ a 5 \ a 6}$

Como acontece com a maioria das notações combinatórias , a definição é recursiva . Neste caso, a notação eventualmente resolve ser o número mais à esquerda elevado a alguma potência inteira (geralmente enorme).

Definição e visão geral

Uma "corrente de Conway" é definida da seguinte forma:

• Qualquer número inteiro positivo é uma cadeia de comprimento .${\ displaystyle 1}$
• Uma cadeia de comprimento n , seguida por uma seta para a direita → e um inteiro positivo, juntos formam uma cadeia de comprimento .${\ displaystyle n + 1}$

Qualquer cadeia representa um número inteiro, de acordo com as cinco (tecnicamente quatro) regras abaixo. Duas cadeias são consideradas equivalentes se representarem o mesmo número inteiro.

Se , e são inteiros positivos, e é uma subcadeia, então: ${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle r}$${\ displaystyle X}$

1. Uma cadeia vazia (ou uma cadeia de comprimento 0) é igual a e a cadeia representa o número .${\ displaystyle 1}$${\ displaystyle p}$${\ displaystyle p}$
2. ${\ displaystyle X \ a 1}$é equivalente a .${\ displaystyle X}$
3. ${\ displaystyle p \ rightarrow q \ rightarrow r}$é equivalente a . (veja a notação de seta para cima de Knuth )${\ displaystyle p [\ uparrow ^ {r}] q}$
4. ${\ displaystyle X \ a p \ a (q + 1)}$é equivalente a (com cópias de , cópias de e pares de parênteses; aplica-se a  > 0).${\ displaystyle X \ to (X \ to (\ cdots (X \ to (X) \ to q) \ cdots) \ to q) \ to q}$
   ${\ displaystyle p}$${\ displaystyle X}$${\ displaystyle p-1}$${\ displaystyle q}$${\ displaystyle p-1}$${\ displaystyle q}$
5. Porque é equivalente a , (Pela regra 2) e também a = , (Pela regra 3) podemos definir como igual${\ displaystyle p \ rightarrow q \ rightarrow 1}$${\ displaystyle p \ to q}$${\ displaystyle p \ uparrow q}$${\ displaystyle p ^ {q}}$${\ displaystyle p \ to q}$${\ displaystyle p ^ {q}}$

Observe que a quarta regra pode ser substituída aplicando repetidamente duas regras para evitar as reticências :

4a. é equivalente a${\ displaystyle X \ a 1 \ a (q + 1)}$${\ displaystyle X}$

4b. é equivalente a${\ displaystyle X \ to (p + 1) \ to (q + 1)}$${\ displaystyle X \ to (X \ to p \ to (q + 1)) \ to q}$

Propriedades

1. Uma cadeia avalia a potência perfeita de seu primeiro número
2. Portanto, é igual a${\ displaystyle 1 \ a Y}$${\ displaystyle 1}$
3. ${\ displaystyle X \ a 1 \ a Y}$ é equivalente a ${\ displaystyle X}$
4. ${\ displaystyle 2 \ a 2 \ a Y}$ é igual a ${\ displaystyle 4}$
5. ${\ displaystyle X \ a 2 \ a 2}$ é equivalente a (não deve ser confundido com )${\ displaystyle X \ to (X)}$${\ displaystyle X \ to X}$

Interpretação

É preciso ter cuidado ao tratar uma corrente de flecha como um todo . As cadeias de setas não descrevem a aplicação iterada de um operador binário. Considerando que cadeias de outros símbolos infixados (por exemplo, 3 + 4 + 5 + 6 + 7) podem frequentemente ser considerados em fragmentos (por exemplo, (3 + 4) + 5 + (6 + 7)) sem uma mudança de significado (ver associatividade ), ou pelo menos pode ser avaliado passo a passo em uma ordem prescrita, por exemplo, 3 ^{4 5 6 7} da direita para a esquerda, o que não é assim com as cadeias de flechas de Conway.

Por exemplo:

• ${\ displaystyle 2 \ rightarrow 3 \ rightarrow 2 = 2 \ uparrow \ uparrow 3 = 2 ^ {2 ^ {2}} = 16}$
• ${\ displaystyle 2 \ rightarrow \ left (3 \ rightarrow 2 \ right) = 2 ^ {(3 ^ {2})} = 2 ^ {3 ^ {2}} = 512}$
• ${\ displaystyle \ left (2 \ rightarrow 3 \ right) \ rightarrow 2 = \ left (2 ^ {3} \ right) ^ {2} = 64}$

A quarta regra é o núcleo: uma cadeia de 4 ou mais elementos terminando com 2 ou mais torna-se uma cadeia do mesmo comprimento com um penúltimo elemento (geralmente muito) aumentado. Mas seu elemento final é decrementado, eventualmente permitindo que a segunda regra encurte a cadeia. Depois, parafraseando Knuth , "muitos detalhes", a cadeia é reduzida a três elementos e a terceira regra encerra a recursão.

Exemplos

Os exemplos ficam bastante complicados rapidamente. Aqui estão alguns pequenos exemplos:

${\ displaystyle n}$

${\ displaystyle = n}$ (Pela regra 1)

${\ displaystyle p \ to q}$

${\ displaystyle = p ^ {q}}$ (Pela regra 5)

Desse modo, ${\ displaystyle 3 \ to 4 = 3 ^ {4} = 81}$

${\ displaystyle 4 \ a 3 \ a 2}$

${\ displaystyle = 4 \ uparrow \ uparrow 3}$ (Pela regra 3)

${\ displaystyle = 4 \ uparrow (4 \ uparrow 4)}$

${\ displaystyle = 4 \ uparrow 256}$

${\ displaystyle = 4 ^ {256}}$

${\ displaystyle = 13.407.807.929.942.597.099.574.024.998.205.846.127.479.365.820.592.393.377.723.561.443.721.764.030.073,}$ ${\ displaystyle 546.976.801.874.298.166.903.427.690.031.858.186.486.050.853.882.811.946.569.946.433.649.006.084.096}$

${\ displaystyle \ aprox. 1,34 * 10 ^ {154}}$

${\ displaystyle 2 \ a 2 \ a}$

${\ displaystyle = 2 [\ uparrow ^ {a}] 2}$ (Pela regra 3)

${\ displaystyle = 4}$(veja a notação de seta para cima de Knuth )

${\ displaystyle 2 \ a 4 \ a 3}$

${\ displaystyle = 2 \ uparrow \ uparrow \ uparrow 4}$ (Pela regra 3)

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow (2 \ uparrow \ uparrow 2))}$

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow \ uparrow 4)}$

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow (2 \ uparrow (2 \ uparrow 2)))}$

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow (2 \ uparrow 4))}$

${\ displaystyle = 2 \ uparrow \ uparrow (2 \ uparrow 16)}$

${\ displaystyle = 2 \ uparrow \ uparrow (65536)}$

${\ displaystyle = {^ {65536} 2}}$(veja tetration )

${\ displaystyle 2 \ a 3 \ a 2 \ a 2}$

${\ displaystyle = 2 \ a 3 \ a (2 \ a 3) \ a 1}$ (Pela regra 4)

${\ displaystyle = 2 \ a 3 \ a 8 \ a 1}$ (Pela regra 5)

${\ displaystyle = 2 \ a 3 \ a 8}$ (Pela regra 2)

${\ displaystyle = 2 \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow 3}$ (Pela regra 3)

= muito maior que o número anterior

${\ displaystyle 3 \ a 2 \ a 2 \ a 2}$

${\ displaystyle = 3 \ to 2 \ to (3 \ to 2) \ to 1}$ (Pela regra 4)

${\ displaystyle = 3 \ a 2 \ a 9 \ a 1}$ (Pela regra 5)

${\ displaystyle = 3 \ a 2 \ a 9}$ (Pela regra 2)

${\ displaystyle = 3 \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow \ uparrow 2}$ (Pela regra 3)

= muito, muito maior do que o número anterior

Exemplos sistemáticos

Os casos mais simples com quatro termos (sem números inteiros menores que 2) são:

• ${\ displaystyle a \ a b \ a 2 \ a 2}$
  ${\ displaystyle = a \ to b \ to 2 \ to (1 + 1)}$
  ${\ displaystyle = a \ to b \ to (a \ to b) \ to 1}$
  ${\ displaystyle = a \ para b \ para a ^ {b}}$
  ${\ displaystyle = a [a ^ {b} +2] b}$

(equivalente à última propriedade mencionada)

• ${\ displaystyle a \ a b \ a 3 \ a 2}$
  ${\ displaystyle = a \ to b \ to 3 \ to (1 + 1)}$
  ${\ displaystyle = a \ to b \ to (a \ to b \ to (a \ to b) \ to 1) \ to 1}$
  ${\ displaystyle = a \ to b \ to (a \ to b \ to a ^ {b})}$
  ${\ displaystyle = a [a \ to b \ to 2 \ to 2 + 2] b}$
• ${\ displaystyle a \ a b \ a 4 \ a 2}$
  ${\ displaystyle = a \ to b \ to (a \ to b \ to (a \ to b \ to a ^ {b}))}$
  ${\ displaystyle = a [a \ to b \ to 3 \ to 2 + 2] b}$

Podemos ver um padrão aqui. Se, para qualquer cadeia , deixarmos então (ver poderes funcionais ). ${\ displaystyle X}$${\ displaystyle f (p) = X \ a p}$${\ displaystyle X \ a p \ a 2 = f ^ {p} (1)}$

Aplicando isso com , então e${\ displaystyle X = a \ to b}$${\ displaystyle f (p) = a [p + 2] b}$${\ displaystyle a \ to b \ to p \ to 2 = a [a \ to b \ to (p-1) \ to 2 + 2] b = f ^ {p} (1)}$

Assim, por exemplo ,. ${\ displaystyle 10 \ a 6 \ a 3 \ a 2 = 10 [10 [1000002] 6 + 2] 6}$

Se movendo:

• ${\ displaystyle a \ a b \ a 2 \ a 3}$
  ${\ displaystyle = a \ to b \ to 2 \ to (2 + 1)}$
  ${\ displaystyle = a \ to b \ to (a \ to b) \ to 2}$
  ${\ displaystyle = a \ para b \ para a ^ {b} \ para 2}$
  ${\ displaystyle = f ^ {a ^ {b}} (1)}$

Novamente, podemos generalizar. Quando escrevemos , temos , isto é ,. No caso acima, e , então${\ displaystyle g_ {q} (p) = X \ para p \ para q}$${\ displaystyle X \ para p \ para q + 1 = g_ {q} ^ {p} (1)}$${\ displaystyle g_ {q + 1} (p) = g_ {q} ^ {p} (1)}$${\ displaystyle g_ {2} (p) = a \ para b \ para p \ para 2 = f ^ {p} (1)}$${\ displaystyle g_ {3} (p) = g_ {2} ^ {p} (1)}$${\ displaystyle a \ to b \ to 2 \ to 3 = g_ {3} (2) = g_ {2} ^ {2} (1) = g_ {2} (g_ {2} (1)) = f ^ {f (1)} (1) = f ^ {a ^ {b}} (1)}$

Função Ackermann

A função de Ackermann pode ser expressa usando a notação de seta em cadeia de Conway:

${\ displaystyle A (m, n) = (2 \ a (n + 3) \ a (m-2)) - 3}$para (desde em hiperoperação )${\ displaystyle m \ geq 3}$${\ displaystyle A (m, n) = 2 [m] (n + 3) -3}$

por isso

${\ displaystyle 2 \ a n \ a m = A (m + 2, n-3) +3}$ para ${\ displaystyle n> 2}$

( e corresponderia com e , que poderia ser logicamente adicionado).${\ displaystyle n = 1}$${\ displaystyle n = 2}$${\ displaystyle A (m, -2) = - 1}$${\ displaystyle A (m, -1) = 1}$

Número de Graham

O próprio número de Graham não pode ser expresso de forma concisa na notação de seta em cadeia de Conway, mas é limitado pelo seguinte: ${\ displaystyle G}$

${\ displaystyle 3 \ rightarrow 3 \ rightarrow 64 \ rightarrow 2 <G <3 \ rightarrow 3 \ rightarrow 65 \ rightarrow 2}$

Prova: primeiro definimos a função intermediária , que pode ser usada para definir o número de Graham como . (O sobrescrito 64 denota um poder funcional .) ${\ displaystyle f (n) = 3 \ rightarrow 3 \ rightarrow n = {\ begin {matriz} 3 \ underbrace {\ uparrow \ uparrow \ cdots \ uparrow} 3 \\ {\ text {n setas}} \ end {matriz }}}$${\ displaystyle G = f ^ {64} (4)}$

Ao aplicar a regra 2 e a regra 4 ao contrário, simplificamos:

${\ displaystyle f ^ {64} (1)}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow 1)) \ cdots))}$(com 64 's)${\ displaystyle 3 \ rightarrow 3}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3) \ rightarrow 1) \ cdots) \ rightarrow 1) \ rightarrow 1}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow 64 \ rightarrow 2;}$

${\ displaystyle f ^ {64} (4) = G;}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow 4)) \ cdots))}$(com 64 's)${\ displaystyle 3 \ rightarrow 3}$

${\ displaystyle f ^ {64} (27)}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow 27)) \ cdots))}$(com 64 's)${\ displaystyle 3 \ rightarrow 3}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (\ cdots (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3))) \ cdots))}$(com 65 's)${\ displaystyle 3 \ rightarrow 3}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow 65 \ rightarrow 2}$ (computando como acima).

${\ displaystyle = f ^ {65} (1)}$

Uma vez que f é estritamente crescente ,

${\ displaystyle f ^ {64} (1) <f ^ {64} (4) <f ^ {64} (27)}$

qual é a desigualdade dada.

Com setas encadeadas, é muito fácil especificar um número muito maior do que , por exemplo ,. ${\ displaystyle G}$${\ displaystyle 3 \ rightarrow 3 \ rightarrow 3 \ rightarrow 3}$

${\ displaystyle 3 \ rightarrow 3 \ rightarrow 3 \ rightarrow 3}$

${\ displaystyle = 3 \ rightarrow 3 \ rightarrow (3 \ rightarrow 3 \ rightarrow 27 \ rightarrow 2) \ rightarrow 2 \,}$

${\ displaystyle = f ^ {3 \ rightarrow 3 \ rightarrow 27 \ rightarrow 2} (1)}$

${\ displaystyle = f ^ {f ^ {27} (1)} (1)}$

que é muito maior do que o número de Graham, porque o número é muito maior do que . ${\ displaystyle 3 \ rightarrow 3 \ rightarrow 27 \ rightarrow 2}$ ${\ displaystyle = f ^ {27} (1)}$${\ displaystyle 65}$

Função CG

Conway e Guy criaram uma função simples de argumento único que diagonaliza toda a notação, definida como:

${\ displaystyle cg (n) = \ underbrace {n \ rightarrow n \ rightarrow n \ rightarrow \ dots \ rightarrow n \ rightarrow n \ rightarrow n} _ {n}}$

o que significa que a sequência é:

${\ displaystyle cg (1) = 1}$

${\ displaystyle cg (2) = 2 \ a 2 = 2 ^ {2} = 4}$

${\ displaystyle cg (3) = 3 \ a 3 \ a 3 = 3 \ uparrow \ uparrow \ uparrow 3}$

${\ displaystyle cg (4) = 4 \ a 4 \ a 4 \ a 4}$

${\ displaystyle cg (5) = 5 \ a 5 \ a 5 \ a 5 \ a 5}$

...

Essa função, como se poderia esperar, cresce extraordinariamente rápido.

Extensão por Peter Hurford

Peter Hurford, um desenvolvedor web e estatístico, definiu uma extensão para esta notação:

${\ displaystyle a \ rightarrow _ {b} c = \ underbrace {a \ rightarrow _ {b-1} a \ rightarrow _ {b-1} a \ rightarrow _ {b-1} \ dots \ rightarrow _ {b- 1} a \ rightarrow _ {b-1} a \ rightarrow _ {b-1} a} _ {c {\ text {setas}}}}$

${\ displaystyle a \ rightarrow _ {1} b = a \ rightarrow b}$

Todas as regras normais permanecem inalteradas de outra forma.

${\ displaystyle a \ rightarrow _ {2} (a-1)}$já é igual ao mencionado acima , e a função é de crescimento muito mais rápido que a de Conway e Guy . ${\ displaystyle cg (a)}$${\ displaystyle f (n) = n \ rightarrow _ {n} n}$${\ displaystyle cg (n)}$

Observe que expressões como são ilegais se e forem números diferentes; uma cadeia deve ter apenas um tipo de seta para a direita. ${\ displaystyle a \ rightarrow _ {b} c \ rightarrow _ {d} e}$${\ displaystyle b}$${\ displaystyle d}$

No entanto, se modificarmos isso ligeiramente, de modo que:

${\ displaystyle a \ rightarrow _ {b} c \ rightarrow _ {d} e = a \ rightarrow _ {b} \ underbrace {c \ rightarrow _ {d-1} c \ rightarrow _ {d-1} c \ rightarrow _ {d-1} \ dots \ rightarrow _ {d-1} c \ rightarrow _ {d-1} c \ rightarrow _ {d-1} c} _ {e {\ text {setas}}}}$

então, não apenas se torna legal, mas a notação como um todo se torna muito mais forte. ${\ displaystyle a \ rightarrow _ {b} c \ rightarrow _ {d} e}$

Veja também

• Notação Steinhaus-Moser
• Criando sistematicamente sequências cada vez mais rápidas

Referências

links externos

• Factoids> grandes números
• Grandes Números de Robert Munafo
• O Livro dos Números de JH Conway e RK Guy