Notação de seta encadeada de Conway

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

A Notação de seta encadeada de Conway, criada pelo matemático John Horton Conway, é um meio de expressar certas 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[editar | editar código-fonte]

Uma 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 n+1.

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:

  1. A cadeia p representa o número p.
  2. p \to q representa a expressão exponencial p^q.
  3. X \to p \to 1 é equivalente a X \to p.
  4. X \to p \to (q + 1) é equivalente a X \to ( X \to ( \dots (X \to ( X ) \to q)\dots ) \to q ) \to q
    (with p copias de X, p - 1 copias de q, e p - 1 pares de parentesis; aplica-se para q > 0).

Note-se que a última regra pode ser atualizada de forma recursiva para evitar elipses:

4a. X \to 1 \to (q + 1) = X
4b. X \to (p + 1) \to (q + 1) = X \to (X \to p \to (q+1)) \to q

Propriedades[editar | editar código-fonte]

  1. Uma cadeia de comprimento 3 corresponde à notação de seta para cima de Knuth e hiperoperadores:


\begin{matrix}
p \to q \to r = \mbox{hyper}(p,r+2,q) = p \!\!\! & \underbrace{ \uparrow \dots \uparrow } & \!\!\! q = p\uparrow^r q.\\
& \!\!\! r \mbox{ arrows} \!\!\!
\end{matrix}

  1. a cadeia X→Y é da forma X→p; conseqüentemente:
  2. a cadeia iniciando com a é uma potência de a
  3. a cadeia 1→Y é igual a 1
  4. a cadeia X→1→Y é igual a X
  5. a cadeia 2→2→Y é igual a 4
  6. a cadeia X→2→2 é igual a X→(X) (cadeia X com o seu valor concatenado a ela)

Interpretação[editar | editar código-fonte]

É 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, 2^{3^4} da direita para a esquerda, que não é o caso com a seta de Conway.

Por exemplo:

  • 2\rightarrow3\rightarrow2 = 2\uparrow\uparrow3 = 2^{2^2} = 16
  • 2\rightarrow\left(3\rightarrow2\right) = 2^{(3^2)} = 2^{3^2} = 512
  • \left(2\rightarrow3\right)\rightarrow2 = \left(2^3\right)^2 = 64

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

Exemplos 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: 4 \uparrow \uparrow 3 = 4 \uparrow 4 \uparrow 4 = 4^{256}

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)
= 2^{2^{\dots^2}} (uma torre com 216 = 65536 andares)

Com as setas de Knuth: 2 \uparrow \uparrow \uparrow 4 = 2 \uparrow \uparrow 2\uparrow \uparrow 2 \uparrow \uparrow 2=2 \uparrow \uparrow 2 \uparrow \uparrow 2 \uparrow 2=2\uparrow \uparrow 2 \uparrow \uparrow 4=2 \uparrow \uparrow 2 \uparrow 2 \uparrow 2 \uparrow 2 = 2 \uparrow \uparrow 65536.

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: 2 \uparrow^6 2 \uparrow^5 2 \uparrow^4 2 \uparrow^3 2 \uparrow^2 65536.

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: 3 \uparrow^8 3.

Exemplos sistemáticos[editar | editar código-fonte]

Os casos mais simples, com quatro termos (contendo pelo menos dois inteiros) são:

  • a \to b \to 2 \to 2 = a \to b \to 2 \to (1 + 1) = a \to b \to (a \to b) \to 1 = a \to b \to a^b = a \uparrow^{a^b} b
(também na sequência da última propriedade citada)
  • a \to b \to 3 \to 2 = a \to b \to 3 \to (1 + 1)
     = a \to b \to (a \to b \to (a \to b) \to 1) \to 1 = a \to b \to (a \to b \to a^b) = a \uparrow^{a \to b \to 2 \to 2} b
  • a \to b \to 4 \to 2 = a \to b \to (a \to b \to (a \to b \to a^b)) = a \uparrow^{a \to b \to 3 \to 2} b

Podemos ver um padrão aqui. Se, para qualquer cadeia X, nós fazemos f(p) = X \to p então X \to p \to 2 = f^p(1) (ver potências de funções).

Aplicando isto com X = a \to b, então f(p) = a \uparrow^p b e a \to b \to p \to 2 = a \uparrow^{a \to b \to (p-1) \to 2} b = f^p(1)

Assim, por exemplo, 10 \to 10 \to 3\to 2 = 10 \uparrow ^{10 \uparrow ^{10^{10}} 10} 10 \!.

Prosseguindo:

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

De novo podemos generalizar. Quendo escrevemos g_q(p) = X \to p \to q nós temos X \to p \to q+1 = g_q^p(1), isto é, g_{q+1}(p) = g_q^p(1). No caso acima, g_2(p) = a \to b \to p \to 2 = f^p(1) e g_3(p) = g_2^p(1), assim 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 de Ackermann[editar | editar código-fonte]

A 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 → nm = 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[editar | editar código-fonte]

O Número de Graham G \! 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 f(n) = 3 \rightarrow 3 \rightarrow n \!, nós temos: G = f^{64}(4)\, , e 3 \rightarrow 3 \rightarrow 64 \rightarrow 2 < G < 3 \rightarrow 3 \rightarrow 65 \rightarrow 2\,

Prova: Aplicando para a definição, a regra 3, e a regra 4, temos:

f^{64}(1)\,

= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\dots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 1))\dots ))\, (com 64 3 \rightarrow 3's)
= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\dots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3) \rightarrow 1) \dots ) \rightarrow 1) \rightarrow 1\,
= 3 \rightarrow 3 \rightarrow 64 \rightarrow 2;\,

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

= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\dots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 4))\dots ))\, (com 64 3 \rightarrow 3's)

f^{64}(27)\,

= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\dots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 27))\dots ))\, (com 64 3 \rightarrow 3's)
= 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (\dots (3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow (3 \rightarrow 3)))\dots ))\, (com 65 3 \rightarrow 3's)
= 3 \rightarrow 3 \rightarrow 65 \rightarrow 2\, (computação como acima).

Desde que f é estritamente crescente,

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

que é a desigualdade dada.

Com as setas encadeadas é muito fácil se especificar um número muito maior. Por exemplo, note que

 3 \rightarrow 3 \rightarrow 3 \rightarrow 3 ~~ = ~~ 3 \rightarrow 3 \rightarrow (3 \rightarrow 3 \rightarrow 27 \rightarrow 2) \rightarrow 2\,

que é muito maior do que o número Graham

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]