Notação de seta encadeada de Conway
# 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

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:
* A cadeia $p$ representa o número p.
* $p\to q$ representa a expressão exponencial $p^{q}$.
* $X\to p\to 1$ é equivalente a $X\to p$.
* $X\to p\to (q+1)$ é equivalente a $X\to (X\to (\dots (X\to (X)\to q)\dots )\to q)\to q$ (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. $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

* 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}}$
* 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

É 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\rightarrow 3\rightarrow 2=2\uparrow \uparrow 3=2^{2^{2}}=16$
* $2\rightarrow \left(3\rightarrow 2\right)=2^{(3^{2})}=2^{3^{2}}=512$
* $\left(2\rightarrow 3\right)\rightarrow 2=\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

Exemplos ficam bastante complicado rapidamente, aqui são pequenos exemplos:
n
    = n (by rule 1)
p→q
    = p$^q$ (by rule 2)
    Thus 3→4 = 3$^4$ = 81
1→(qualquer expressão com setas)
    = 1 uma vez que a expressão inteira, eventualmente, se reduz a 1$^{number}$ = 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)
    = 4$^{256}$ ≈ 1.34078079299 × 10$^{154}$ 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 2$^{16}$ = 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

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

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 → 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

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