Notação de seta encadeada de Conway
A Notação de seta encadeada de Conway, criada pelo matemático John Horton Conway, é um meio de expressar certos números extremamente grandes. É simplesmente uma seqüência finita de inteiros positivos separados por setas para a direita, por exemplo, 2→3→4→5→6..
Como a maioria das simbologias combinatórias , a definição é recursiva. Neste caso, a notação eventualmente se resolve a ser o número mais à esquerda elevado a alguma potência inteira (geralmente enorme).
Definição e visão global
editarUma Cadeia de Conway (ou simplesmente cadeia) é definida como segue:
- Qualquer número inteiro positivo é uma cadeia de comprimento 1.
- Uma cadeia de comprimento n, seguida por uma seta para a direita → e um inteiro positivo, juntos, formam uma cadeia de comprimento .
Qualquer cadeia representa um número inteiro, de acordo com as quatro regras abaixo. Duas cadeias são ditas equivalentes se elas representam o mesma inteiro.
Se p e q são inteiros positivos, e X é uma subcadeia, então:
- A cadeia representa o número p.
- representa a expressão exponencial .
- é equivalente a .
- é equivalente a
(com p copias de X, p - 1 copias de q, e p - 1 pares de parêntesis; aplica-se para q > 0).
Note-se que a última regra pode ser atualizada de forma recursiva para evitar elipses:
- 4a.
- 4b.
Propriedades
editar- Uma cadeia de comprimento 3 corresponde à notação de seta para cima de Knuth e hiperoperadores:
- a cadeia X→Y é da forma X→p; conseqüentemente:
- a cadeia iniciando com a é uma potência de a
- a cadeia 1→Y é igual a 1
- a cadeia X→1→Y é igual a X
- a cadeia 2→2→Y é igual a 4
- a cadeia X→2→2 é igual a X→(X) (cadeia X com o seu valor concatenado a ela)
Interpretação
editarÉ preciso ter cuidado ao se tratar uma cadeia de setas como um todo. Cadeias de setas não descrevem a aplicação iterada de um operador binário. Considerando que as cadeias de outros símbolos infixados (por exemplo 3+4+5+6+7) podem muitas vezes ser considerados em fragmentos (por exemplo: (3+4)+5+(6+7)) sem uma mudança de significado (veja associatividade), ou pelo menos podem ser avaliadas, passo a passo em uma ordem prescrita, por exemplo, da direita para a esquerda, que não é o caso com a seta de Conway.
Por exemplo:
A quarta regra é a essência: uma cadeia de 3 ou mais elementos que terminam com 2 ou mais torna-se uma cadeia de mesmo comprimento, com um (geralmente vasto) penúltimo elemento aumentado . Mas o seu último elemento é diminuído, permitindo, eventualmente, a terceira regra encurtar a cadeia. Depois, parafraseando Knuth, "detalhes demais", a cadeia é reduzida a dois elementos e a segunda regra termina a recursividade.
Exemplos
editarExemplos ficam bastante complicado rapidamente, aqui são pequenos exemplos:
n
- = n (by rule 1)
p→q
- = pq (by rule 2)
- Thus 3→4 = 34 = 81
1→(qualquer expressão com setas)
- = 1 uma vez que a expressão inteira, eventualmente, se reduz a 1number = 1. (Na verdade, qualquer cadeia que contenha um 1 pode ser truncada logo antes deste 1; e.g. X→1→Y=X para todas as cadeias (incorporadas) X,Y.)
4→3→2
- = 4→(4→(4)→1)→1 (by 1) e, em seguida, trabalhando dos parênteses mais internos para os externos,
- = 4→(4→4→1)→1 (remove parênteses redundantes [rrp])
- = 4→(4→4)→1 (2)
- = 4→(256)→1 (3)
- = 4→256→1 (rrp)
- = 4→256 (2)
- = 4256 ≈ 1.34078079299 × 10154 aproximadamente (3)
Com setas de Knuth:
2→2→4
- = 2→(2)→3 (por 1)
- = 2→2→3 (rrp)
- = 2→2→2 (1, rrp)
- = 2→2→1 (1, rrp)
- = 2→2 (2)
- = 4 (3) (Na verdade, qualquer cadeia começando com dois 2s representa 4.)
2→4→3
- = 2→(2→(2→(2)→2)→2)→2 (by 1) As quatro cópias de X (que é 2 aqui) estão em negrito para distingui-las das três cópias de q (que é também 2)
- = 2→(2→(2→2→2)→2)→2 (rrp)
- = 2→(2→(4)→2)→2 (exemplo prévio)
- = 2→(2→4→2)→2 (rrp) (expressão expandida na equação seguinte mostra em negrito em ambas as linhas)
- = 2→(2→(2→(2→(2)→1)→1)→1)→2 (1)
- = 2→(2→(2→(2→2→1)→1)→1)→2 (rrp)
- = 2→(2→(2→(2→2)))→2 (2 repetidamente)
- = 2→(2→(2→(4)))→2 (3)
- = 2→(2→(16))→2 (3)
- = 2→65536→2 (3,rrp)
- = 2→(2→(2→(...2→(2→(2)→1)→1...)→1)→1)→1 (1) com 65535 conjuntos de parêntesis
- = 2→(2→(2→(...2→(2→(2))...)))) (2 repetidamente)
- = 2→(2→(2→(...2→(4))...)))) (3)
- = 2→(2→(2→(...16...)))) (3)
- = (uma torre com 216 = 65536 andares)
Com as setas de Knuth: .
2→3→2→2
- = 2→3→(2→3)→1 (by 1)
- = 2→3→8 (2 e 3) Com as setas de Knuth: 2 ↑8 3 (prop1)
- = 2→(2→2→7)→7 (1)
- = 2→4→7 (dois 2 iniciais dão 4 [prop6]) Com as setas de Knuth: 2 ↑7 4 (prop1)
- = 2→(2→(2→2→6)→6)→6 (1)
- = 2→(2→4→6)→6 (prop6)
- = 2→(2→(2→(2→2→5)→5)→5)→6 (1)
- = 2→(2→(2→4→5)→5)→6 (prop6)
- = 2→(2→(2→(2→(2→2→4)→4)→4)→5)→6 (1)
- = 2→(2→(2→(2→4→4)→4)→5)→6 (prop6)
- = 2→(2→(2→(2→(2→(2→2→3)→3)→3)→4) →5)→6 (1)
- = 2→(2→(2→(2→(2→4→3)→3)→4)→5)→6 (prop6)
- = 2→(2→(2→(2→(2→65536→2)→3)→4)→5)→6 (exemplo anterior)
- = muito maior do que o número anterior
Com as setas de Knuth:
3→2→2→2
- = 3→2→(3→2)→1 (1)
- = 3→2→9 (2 e 3)
- = 3→3→8 (1)
Com as setas de Knuth: .
Exemplos sistemáticos
editarOs casos mais simples, com quatro termos (contendo pelo menos dois inteiros) são:
- (também na sequência da última propriedade citada)
Podemos ver um padrão aqui. Se, para qualquer cadeia X, nós fazemos então (ver potências de funções).
Aplicando isto com , então e
Assim, por exemplo, .
Prosseguindo:
De novo podemos generalizar. Quendo escrevemos nós temos , isto é, . No caso acima, e , assim
Função de Ackermann
editarA Função de Ackermann pode ser expressada usando-se a Notação de seta encadeada de Conway:
- A(m, n) = (2 → (n+3) → (m − 2)) − 3 for m>2
daqui
- 2 → n → m = A(m+2,n-3) + 3 for n>2
(n=1 and n=2 corresponderia a A(m,-2)=-1 and A(m,-1)=1, que poderia logicamente ser adicionado).
Número de Graham
editarO Número de Graham em si não pode ser expresso de forma sucinta na notação de seta encadeada de Conway, mas pela definição da função intermediária , nós temos: , e
Prova: Aplicando para a definição, a regra 3, e a regra 4, temos:
- (com 64 's)
- (com 64 's)
- (com 64 's)
- (com 65 's)
- (computação como acima).
Desde que f é estritamente crescente,
que é a desigualdade dada.
Com as setas encadeadas é muito fácil se especificar um número muito maior. Por exemplo, note que
que é muito maior do que o número Graham
Ver também
editarLigações externas
editar