# Notação de Knuth

Em matemática, a Notação de Knuth (em inglês:Knuth's up-arrow notation) é um método de notação para inteiros muito grandes, introduzido por Donald Knuth em 1976 . É intimamente relacionada com a função de Ackermann e, especialmente, para a sequência de hiperoperações. A ideia é baseada no fato de que a multiplicação pode ser visto como uma adição iterada e a exponenciação como uma multiplicação iterada. Continuando desta forma se leva a exponenciação iterada (tetração) e para o restante da sequência de hiperoperação, que é comumente denotada pela notação da seta de Knuth.

## Introdução

As operações aritméticas simples de adição, multiplicação e exponenciação são naturalmente estendidas em uma sequência de hiperoperações como segue.
Multiplicação por um número natural pode ser definida como uma adição iterada:
    ${\begin{matrix}a\times b&=&\underbrace {a+a+\dots +a} \\&&b{\mbox{ cópias de }}a\end{matrix}}$
Por exemplo,
    ${\begin{matrix}4\times 3&=&\underbrace {4+4+4} &=&12\\&&3{\mbox{ cópias de }}4\end{matrix}}$
Exponenciação para uma potência natural $b$ pode ser definida como uma multiplicação iterada, denotada por Knuth por uma simples seta para cima:
    ${\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ cópias de }}a\end{matrix}}$
Por exemplo,
    ${\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3{\mbox{ cópias de }}4\end{matrix}}$
Para estender a sequência de operações para além exponenciação, Knuth definiu um operador “seta dupla” para denotar a exponenciação iterada (tetração):
    ${\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\&&b{\mbox{ cópias de }}a&&b{\mbox{ cópias de }}a\end{matrix}}$
Por exemplo,
    ${\begin{matrix}4\uparrow \uparrow 3&={\ ^{3}4}=&\underbrace {4^{4^{4}}} &=&\underbrace {4\uparrow (4\uparrow 4)} &=&4^{256}\approx 1.3\times 10^{154}\\&&3{\mbox{ cópias de }}4&&3{\mbox{ cópias de }}4\end{matrix}}$
Aqui e abaixo a avaliação é para ser realizada da direita para a esquerda, uma vez que os operadores de seta de Knuth (como exponenciação) são definidos para serem associativos à direita.
Segundo esta definição,
    $3\uparrow \uparrow 2=3^{3}=27$
    $3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7.625.597.484.987$
    $3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7625597484987}$
    $3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{7625597484987}}$
    etc.
Isso já leva a alguns números bastante grandes, mas Knuth estendeu a notação. Ele passou a definir um operador de seta "tripla" para a aplicação iterada do operador de seta dupla (também conhecido como pentação):
    ${\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b{\mbox{ cópias de }}a\end{matrix}}$
seguido por um operador de 'seta quádrupla':
    ${\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ cópias de }}a\end{matrix}}$
e assim por diante. A regra geral é que um operador-$n$ seta expande-se em uma série associativa à direita de ($n-1$)-operadores seta. Simbolicamente,
    ${\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\end{matrix}}$
Exemplos:
$3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7.625.597.484.987$
${\begin{matrix}3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3\uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow 3\uparrow 3)=&\underbrace {3_\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow 3\uparrow 3{\mbox{ cópias de }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_\uparrow 3\uparrow \dots \uparrow 3} \\&{\mbox{7.625.597.484.987 cópias de 3}}\end{matrix}}$
A notação $a\uparrow ^{n}b$ é comumente usada para denotar $a\uparrow \uparrow \dots \uparrow b$ com n setas.

## Notação

Em expressões tais como $a^{b}$, a notação para a exponenciação consiste geralmente em se escrever o expoente $b$ como um número sobrescrito em relação ao número base $a$. Mas muitos ambientes — tais como nos fontes de linguagens de programação e em textos em formato de texto simples como mensagens de e-mail - não dispõe deste formato bidimensional. As pessoas adotaram a notação linear $a\uparrow b$ para tais ambientes, a seta para cima sugere 'elevar à potência'. Se o conjunto de caracteres não contém uma seta para cima, o acento circunflexo ^ é usado em seu lugar.
A notação sobrescrita $a^{b}$ não se presta bem a generalização, o que explica a razão de Knuth optar por trabalhar a partir da notação cursiva $a\uparrow b$ em vez disso.

### Escrevendo a notação de seta para cima em termos de potências

A tentativa de se escrever $a\uparrow \uparrow b$ usando a notação familiar com números sobrescritos resulta em uma torre de potências.
    Por exemplo: $a\uparrow \uparrow 4=a\uparrow a\uparrow a\uparrow a=a^{a^{a^{a}}}$
Se b é uma variável (ou é muito grande), a torre de potências pode ser escrita usando pontos e uma nota indicando a altura da torre.
    $a\uparrow \uparrow b=\underbrace {a^{a^{.^{.^{.{a}}}}}} _{b}$
Continuando com esta notação, $a\uparrow \uparrow \uparrow b$ poderia ser escrita com uma pilha destas torres de potências, cada uma descrevendo o tamanho daquela que está acima de si.
    $a\uparrow \uparrow \uparrow 4=a\uparrow \uparrow a\uparrow \uparrow a\uparrow \uparrow a=\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{a}}}$
Novamente, se b é uma variável ou é muito grande, a pilha pode ser escrita usando pontos e uma nota indicando a sua altura.
    $a\uparrow \uparrow \uparrow b=\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\$
Além disso, $a\uparrow \uparrow \uparrow \uparrow b$ pode ser escrito usando-se várias colunas destas pilhas como torres de potências, cada coluna descrevendo o número de torres de potências na pilha à sua esquerda:
    $a\uparrow \uparrow \uparrow \uparrow 4=a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow a=\left.\left.\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\$
E de forma mais geral:
    $a\uparrow \uparrow \uparrow \uparrow b=\underbrace {\left.\left.\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\$
Isso pode ser realizado indefinidamente para representar $a\uparrow ^{n}b$ como uma exponenciação iterada de exponenciações iteradas para qualquer a,n e b(embora ele torna-se claramente bastante pesado).

#### Usando tetração

A notação de tetração $^{b}a$ nos permite fazer estes diagramas de forma um pouco mais simples, ainda empregando uma representação geométrica (que poderíamos chamar estas de torres de tetração).
    $a\uparrow \uparrow b=^{b}a$
    $a\uparrow \uparrow \uparrow b=\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{b}$
    $a\uparrow \uparrow \uparrow \uparrow b=\left.\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{\underbrace {^{^{^{^{^{a}.}.}.}a}a} _{\underbrace {\vdots } _{a}}}\right\$
Finalmente, a título de exemplo, o quarto número de Ackermann $4\uparrow ^{4}4$ poderia ser representado como:
    $\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{4}}}=\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{^{^{^{4}4}4}4}}$

## Generalizações

Alguns números são tão grandes que o uso de várias setas da notação de seta para cima de Knuth torna-se demasiado pesado; então um operador n-seta$\uparrow ^{n}$ é útil (e também para as descrições com um número variável de setas), ou de forma equivalente, hiper operadores.
Alguns números são tão grandes que até mesmo esta notação não é suficiente. O número de Graham é um exemplo. A Notação de seta encadeada de Conway pode ser usada: uma cadeia de três elementos é equivalente ao de outras notações, mas uma cadeia de quatro ou mais é ainda mais poderosa.
    ${\begin{matrix}a\uparrow ^{n}b&=&{\mbox{hyper}}(a,n+2,b)&=&a\to b\to n\\{\mbox{(Knuth)}}&&&&{\mbox{(Conway)}}\end{matrix}}$
Em geral, é sugerido que a seta de Knuth deva ser usada para números de menor magnitude, e a seta encadeada de Conway ou hiper operadores para os de maior magnitude.

## Definição

A notação de seta para cima é formalmente definida por
    $a\uparrow ^{n}b=\left\{{\begin{matrix}a^{b},&{\mbox{se }}n=1;\\1,&{\mbox{se }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\mbox{em outro caso}}\end{matrix}}\right.$
para todos inteiros $a,b,n$ com $b\geq 0,n\geq 1$.
Todos os operadores de seta para cima (incluindo a exponenciação normal, $a\uparrow b$) são associativos à direita, ou seja, a avaliação é realizada da direita para a esquerda em uma expressão que contém dois ou mais desses operadores. Por exemplo, $a\uparrow b\uparrow c=a\uparrow (b\uparrow c)$, e não $(a\uparrow b)\uparrow c$; por exemplo $3\uparrow \uparrow 3=3^{3^{3}}$ é $3^{(3^{3})}=3^{27}=7625597484987$ e não $\left(3^{3}\right)^{3}=27^{3}=19683.$
Há uma boa razão para a escolha desta ordem de avaliação da direita para à esquerda. Se usássemos a avaliação da esquerda para a direita, então $a\uparrow \uparrow b$ seria igual a $a\uparrow (a\uparrow (b-1))$, de modo que $\uparrow \uparrow$ não seria uma operação essencialmente nova. A associatividade à direita também é natural porque nós podemos reescrever a expressão de seta iterada $a\uparrow ^{n}\cdots \uparrow ^{n}a$ que aparece na expansão de $a\uparrow ^{n+1}b$ como $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$, de forma que todos os $a$s aparecem como operandos à esquerda dos operadores de seta. Isto é significativo uma vez que os operadores de seta não são comutativos.
Escrevendo $(a\uparrow ^{m})^{b}$ para a b-ésima potência funcional da função $f(x)=a\uparrow ^{m}x$ nós temos $a\uparrow ^{n}b=(a\uparrow ^{n-1})^{b}1$.
A definição poderia ser extrapolada um passo, começando com $a\uparrow ^{n}b=ab$ se n = 0, porque exponenciação é uma multiplicação repetida iniciando em 1. Extrapolando mais um passo, escrevendo a multiplicação como uma adição repetida, não é tão simples, porque a multiplicação é a adição repetida a partir de 0 ao invés de 1. "Extrapolando" novamente um passo a mais, além de escrever n como adições repetidas de 1, se requer o começo com o número a. Compare com a definição de operador hiperoperador, onde os valores de partida para a adição e multiplicação também são especificados separadamente.

## Tabelas de valores

A Computação de $2\uparrow ^{m}n$ pode ser reafirmada em termos de uma tabela infinita. Nós colocamos os números 2 $n$ na linha superior, e preenchemos a coluna da esquerda com valores 2. Para determinar um número na tabela, pegamos o número imediatamente à esquerda, em seguida, procuramos o número necessário na linha anterior, na posição dada pelo número acabamos de tomar.
Valores de $2\uparrow ^{m}n$ = hiper(2, m + 2, n) = 2 → n → m :
| m\n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | formula |
| 0 | 2 | 4 | 6 | 8 | 10 | 12 | 14 | $2n$ |
| 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | $2^{n}$ |
| 2 | 2 | 4 | 16 | 65536 | $2^{65536}\approx 2.0\times 10^{19,729}$ | $2^{2^{65536}}\approx 10^{6.0\times 10^{19,728}}$ | $2^{2^{2^{65536}}}\approx 10^{10^{6.0\times 10^{19,728}}}$ | $2\uparrow \uparrow n$ |
| 3 | 2 | 4 | 65536 | ${\begin{matrix}\underbrace {2_^{2^{^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ cópias de }}2\end{matrix}}\approx (10\uparrow )^{65531}(6.0\times 10^{19,728})$ | | | | $2\uparrow \uparrow \uparrow n$ |
| 4 | 2 | 4 | ${\begin{matrix}\underbrace {2_^{2^{^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ cópias de }}2\end{matrix}}$ | | | | | $2\uparrow \uparrow \uparrow \uparrow n$ |
Nota: $(10\uparrow )^{k}$ denota uma função de potência da função $f(n)=10^{n}$ (A função também é expressa pelo sufixo-plex como em googolplex).
A tabela é a mesma que a da função de Ackermann, com exceção de uma mudança em $m$ e $n$, e um acréscimo de 3 a todos os valores.
Computando $3\uparrow ^{m}n$
Nós colocamos os números 3 $n$ na linha superior, e preenchemos a coluna da esquerda com valores 3. Para determinar um número na tabela, pegue o número imediatamente à esquerda, em seguida, procura-se o número necessário na linha anterior, na posição dada pelo número acabado de tomar.
Valores de $3\uparrow ^{m}n$ = hiper(3, m + 2, n) = 3 → n → m :
| m\n | 1 | 2 | 3 | 4 | 5 | fórmula |
| 0 | 3 | 6 | 9 | 12 | 15 | $3n$ |
| 1 | 3 | 9 | 27 | 81 | 243 | $3^{n}$ |
| 2 | 3 | 27 | 7.625.597.484.987 | $3^{7.625.597.484.987}$ | | $3\uparrow \uparrow n$ |
| 3 | 3 | 7.625.597.484.987 | ${\begin{matrix}\underbrace {3_^{3^{^{.\,^{.\,^{.\,^{3}}}}}}} \\7.625.597.484.987{\mbox{ cópias de }}3\end{matrix}}$ | | | $3\uparrow \uparrow \uparrow n$ |
| 4 | 3 | ${\begin{matrix}\underbrace {3_^{3^{^{.\,^{.\,^{.\,^{3}}}}}}} \\7.625.597.484.987{\mbox{ cópias de }}3\end{matrix}}$ | | | | $3\uparrow \uparrow \uparrow \uparrow n$ |
Computando $10\uparrow ^{m}n$
Colocamos os números 10 $n$ na linha superior, e preenchemos a coluna da esquerda com valores 10. Para determinar um número na tabela, se pega o número imediatamente à esquerda, em seguida, procura-se o número necessário na linha anterior, na posição dada pelo número que se acabou de tomar.
Valores de $10\uparrow ^{m}n$ = hiper(10, m + 2, n) = 10 → n → m :
| m\n | 1 | 2 | 3 | 4 | 5 | fórmula |
| 0 | 10 | 20 | 30 | 40 | 50 | $10n$ |
| 1 | 10 | 100 | 1.000 | 10.000 | 100.000 | $10^{n}$ |
| 2 | 10 | 10.000.000.000 | $10^{10.000.000.000}$ | $10^{10^{10.000.000.000}}$ | $10^{10^{10^{10.000.000.000}}}$ | $10\uparrow \uparrow n$ |
| 3 | 10 | ${\begin{matrix}\underbrace {10_^{10^{^{.\,^{.\,^{.\,^{10}}}}}}} \\10{\mbox{ cópias de }}10\end{matrix}}$ | ${\begin{matrix}\underbrace {10_^{10^{^{.\,^{.\,^{.\,^{10}}}}}}} \\10^{10}{\mbox{ cópias de }}10\end{matrix}}$ | ${\begin{matrix}\underbrace {10_^{10^{^{.\,^{.\,^{.\,^{10}}}}}}} \\10^{10^{10}}{\mbox{ cópias de }}10\end{matrix}}$ | | $10\uparrow \uparrow \uparrow n$ |
| 4 | 10 | ${\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10{\mbox{ cópias de }}10\end{matrix}}$ | ${\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10^{10}{\mbox{ cópias de }}10\end{matrix}}$ | | | $10\uparrow \uparrow \uparrow \uparrow n$ |
Observe que, para 2 ≤ n ≤ 9 a ordem numérica dos números $10\uparrow ^{m}n$ é a ordem lexicográfica com m como o número mais significativo, assim, para os números dessas 8 colunas a ordem numérica é simplesmente linha por linha. O mesmo se aplica para os números das 97 colunas com 3 ≤ n ≤ 99, e se começarmos a partir de m = 1, mesmo para 3 ≤ n ≤ 9.999.999.999.

## Sistemas de Numeração com base na sequência de hiperoperações

Goodstein [1947], com um sistema de notação diferente da notação de setas de Knuth, usou a sequência de hiperoperadores aqui denotada por $(+,\ \times ,\ \uparrow ,\ \uparrow \uparrow ,\ \dots )\,\!$ para criar sistemas de numeração para os inteiros não negativos. Deixando sobrescritos $\quad (^{(1)},\ ^{(2)},\ ^{(3)},\ ^{(4)},\ \dots )\,\!$ denotando os respectivos hiperoperadores $(+,\ \times ,\ \uparrow ,\ \uparrow \uparrow ,\ \dots )\,\!$, a assim chamada representação hereditária completa do inteiro n, ao nível k e base b, pode ser expresso da seguinte forma usando apenas os k primeiros hiperoperadores e utilizando-se como dígitos apenas 0, 1, ...,b-1:
* Para 0 ≤ n ≤ b-1, n é representado simplesmente por o dígito correspondente.
* Para n > b-1, a representação de n é encontrada de forma recursiva, em primeiro lugar representando n na forma
    $b^{(k)}{x_{k}}^{(k-1)}{x_{k-1}}^{(k-2)}\dots {x_{2}}^{(1)}x_{1}$
    onde x$_k$, ..., x$_1$ são os maiores números inteiros que satisfazem (no turno)
    $b^{(k)}x_{k}\leq n$
    $b^{(k)}{x_{k}}^{(k-1)}x_{k-1}\leq n$
    $b^{(k)}{x_{k}}^{(k-1)}{x_{k-1}}^{(k-2)}\dots {x_{2}}^{(1)}x_{1}\leq n$.
    Qualquer x$_i$ excedendo b-1 é então re-expressado da mesma forma, e assim por diante, repetindo este procedimento até que a forma resultante contenha apenas os dígitos 0, 1, ..., b-1.
O restante desta seção usará $(+,\ \times ,\ \uparrow ,\ \uparrow \uparrow ,\ \uparrow \uparrow \uparrow ,\ \dots )$, ao invés de sobrescritos, para denotar o hiperoperadores.
Parênteses desnecessários podem ser evitados, dando maior precedência para operadores de maior nível na ordem de avaliação; assim,
representações de nível-1 têm a forma $b+X$, com X também desta forma;
representações de nível-2 têm a forma $b\times X+Y$, com X,Y também desta forma;
representações de nível-3 têm a forma $b\uparrow X\times Y+Z$, com X,Y,Z também desta forma;
representações de nível-4 têm a forma $b\uparrow \uparrow X\uparrow Y\times Z+T$, com X,Y,Z,T também desta forma;
e assim por diante.
As representações podem ser abreviadas, omitindo-se todas as instâncias de $+0,\ \times 1,\uparrow 1,\ \uparrow \uparrow 1,$ etc.; por exemplo, a representação de nível-3 base-2 do número 6 é $2\uparrow (2\uparrow 1\times 1+0)\times 1+(2\uparrow 1\times 1+0)$, que abrevia a $2\uparrow 2+2$.
Exemplos: As únicas representações base-2 do número 266, nos níveis 1, 2, 3, 4, e 5 são as seguintes:
    ${\text{Nível 1:}}\ \ 266=2+2+\dots +2\ \ {\text{(com 133 2s)}}$
    ${\text{Nível 2:}}\ \ 266=2\times (2\times (2\times (2\times 2\times 2\times 2\times 2+1))+1)$
    ${\text{Nível 3:}}\ \ 266=2\uparrow 2\uparrow (2+1)+2\uparrow (2+1)+2$
    ${\text{Nível 4:}}\ \ 266=2\uparrow \uparrow (2+1)\uparrow 2+2\uparrow \uparrow 2\times 2+2$
    ${\text{Nível 5:}}\ \ 266=2\uparrow \uparrow \uparrow 2\uparrow \uparrow 2+2\uparrow \uparrow \uparrow 2\times 2+2$.