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.

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:

${\displaystyle {\begin{matrix}a\times b&=&\underbrace {a+a+\dots +a} \\&&b{\mbox{ cópias de }}a\end{matrix}}}$

Por exemplo,

${\displaystyle {\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 ${\displaystyle b}$ pode ser definida como uma multiplicação iterada, denotada por Knuth por uma simples seta para cima:

${\displaystyle {\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,

${\displaystyle {\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):

${\displaystyle {\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,

${\displaystyle {\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,

${\displaystyle 3\uparrow \uparrow 2=3^{3}=27}$

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7.625.597.484.987}$

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7625597484987}}$

${\displaystyle 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):

${\displaystyle {\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':

${\displaystyle {\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-${\displaystyle n}$ seta expande-se em uma série associativa à direita de (${\displaystyle n-1}$)-operadores seta. Simbolicamente,

${\displaystyle {\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:

${\displaystyle 3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7.625.597.484.987}$

${\displaystyle {\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 ${\displaystyle a\uparrow ^{n}b}$ é comumente usada para denotar ${\displaystyle a\uparrow \uparrow \dots \uparrow b}$ com n setas.

Em expressões tais como ${\displaystyle a^{b}}$, a notação para a exponenciação consiste geralmente em se escrever o expoente ${\displaystyle b}$ como um número sobrescrito em relação ao número base ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle a\uparrow b}$ em vez disso.

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${\displaystyle \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.

${\displaystyle {\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.

A notação de seta para cima é formalmente definida por

${\displaystyle 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 ${\displaystyle a,b,n}$ com ${\displaystyle b\geq 0,n\geq 1}$.

Todos os operadores de seta para cima (incluindo a exponenciação normal, ${\displaystyle 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, ${\displaystyle a\uparrow b\uparrow c=a\uparrow (b\uparrow c)}$, e não ${\displaystyle (a\uparrow b)\uparrow c}$; por exemplo
${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}}$ é ${\displaystyle 3^{(3^{3})}=3^{27}=7625597484987}$ e não ${\displaystyle \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 ${\displaystyle a\uparrow \uparrow b}$ seria igual a ${\displaystyle a\uparrow (a\uparrow (b-1))}$, de modo que ${\displaystyle \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 ${\displaystyle a\uparrow ^{n}\cdots \uparrow ^{n}a}$ que aparece na expansão de ${\displaystyle a\uparrow ^{n+1}b}$ como ${\displaystyle a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1}$, de forma que todos os ${\displaystyle 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 ${\displaystyle (a\uparrow ^{m})^{b}}$ para a b-ésima potência funcional da função ${\displaystyle f(x)=a\uparrow ^{m}x}$ nós temos ${\displaystyle a\uparrow ^{n}b=(a\uparrow ^{n-1})^{b}1}$.

A definição poderia ser extrapolada um passo, começando com ${\displaystyle 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.

A Computação de ${\displaystyle 2\uparrow ^{m}n}$ pode ser reafirmada em termos de uma tabela infinita. Nós colocamos os números 2 ${\displaystyle 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 ${\displaystyle 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	${\displaystyle 2n}$
1	2	4	8	16	32	64	128	${\displaystyle 2^{n}}$
2	2	4	16	65536	${\displaystyle 2^{65536}\approx 2.0\times 10^{19,729}}$	${\displaystyle 2^{2^{65536}}\approx 10^{6.0\times 10^{19,728}}}$	${\displaystyle 2^{2^{2^{65536}}}\approx 10^{10^{6.0\times 10^{19,728}}}}$	${\displaystyle 2\uparrow \uparrow n}$
3	2	4	65536	${\displaystyle {\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ cópias de }}2\end{matrix}}\approx (10\uparrow )^{65531}(6.0\times 10^{19,728})}$				${\displaystyle 2\uparrow \uparrow \uparrow n}$
4	2	4	${\displaystyle {\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ cópias de }}2\end{matrix}}}$					${\displaystyle 2\uparrow \uparrow \uparrow \uparrow n}$

Nota: ${\displaystyle (10\uparrow )^{k}}$ denota uma função de potência da função ${\displaystyle 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 ${\displaystyle m}$ e ${\displaystyle n}$, e um acréscimo de 3 a todos os valores.

Computando ${\displaystyle 3\uparrow ^{m}n}$

Nós colocamos os números 3 ${\displaystyle 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 ${\displaystyle 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	${\displaystyle 3n}$
1	3	9	27	81	243	${\displaystyle 3^{n}}$
2	3	27	7.625.597.484.987	${\displaystyle 3^{7.625.597.484.987}}$		${\displaystyle 3\uparrow \uparrow n}$
3	3	7.625.597.484.987	${\displaystyle {\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7.625.597.484.987{\mbox{ cópias de }}3\end{matrix}}}$			${\displaystyle 3\uparrow \uparrow \uparrow n}$
4	3	${\displaystyle {\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7.625.597.484.987{\mbox{ cópias de }}3\end{matrix}}}$				${\displaystyle 3\uparrow \uparrow \uparrow \uparrow n}$

Computando ${\displaystyle 10\uparrow ^{m}n}$

Colocamos os números 10 ${\displaystyle 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 ${\displaystyle 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	${\displaystyle 10n}$
1	10	100	1.000	10.000	100.000	${\displaystyle 10^{n}}$
2	10	10.000.000.000	${\displaystyle 10^{10.000.000.000}}$	${\displaystyle 10^{10^{10.000.000.000}}}$	${\displaystyle 10^{10^{10^{10.000.000.000}}}}$	${\displaystyle 10\uparrow \uparrow n}$
3	10	${\displaystyle {\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10{\mbox{ cópias de }}10\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10^{10}{\mbox{ cópias de }}10\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10^{10^{10}}{\mbox{ cópias de }}10\end{matrix}}}$		${\displaystyle 10\uparrow \uparrow \uparrow n}$
4	10	${\displaystyle {\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10{\mbox{ cópias de }}10\end{matrix}}}$	${\displaystyle {\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10^{10}{\mbox{ cópias de }}10\end{matrix}}}$			${\displaystyle 10\uparrow \uparrow \uparrow \uparrow n}$

Observe que, para 2 ≤ n ≤ 9 a ordem numérica dos números ${\displaystyle 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.

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 ${\displaystyle (+,\ \times ,\ \uparrow ,\ \uparrow \uparrow ,\ \dots )\,\!}$ para criar sistemas de numeração para os inteiros não negativos. Deixando sobrescritos ${\displaystyle \quad (^{(1)},\ ^{(2)},\ ^{(3)},\ ^{(4)},\ \dots )\,\!}$ denotando os respectivos hiperoperadores ${\displaystyle (+,\ \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

${\displaystyle b^{(k)}{x_{k}}^{(k-1)}{x_{k-1}}^{(k-2)}\dots {x_{2}}^{(1)}x_{1}}$

onde x_k, ..., x₁ são os maiores números inteiros que satisfazem (no turno)

${\displaystyle b^{(k)}x_{k}\leq n}$

${\displaystyle b^{(k)}{x_{k}}^{(k-1)}x_{k-1}\leq n}$

...

${\displaystyle 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á ${\displaystyle (+,\ \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 ${\displaystyle b+X}$, com X também desta forma;

representações de nível-2 têm a forma ${\displaystyle b\times X+Y}$, com X,Y também desta forma;

representações de nível-3 têm a forma ${\displaystyle b\uparrow X\times Y+Z}$, com X,Y,Z também desta forma;

representações de nível-4 têm a forma ${\displaystyle 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 ${\displaystyle +0,\ \times 1,\uparrow 1,\ \uparrow \uparrow 1,}$ etc.; por exemplo, a representação de nível-3 base-2 do número 6 é ${\displaystyle 2\uparrow (2\uparrow 1\times 1+0)\times 1+(2\uparrow 1\times 1+0)}$, que abrevia a ${\displaystyle 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:

${\displaystyle {\text{Nível 1:}}\ \ 266=2+2+\dots +2\ \ {\text{(com 133 2s)}}}$

${\displaystyle {\text{Nível 2:}}\ \ 266=2\times (2\times (2\times (2\times 2\times 2\times 2\times 2+1))+1)}$

${\displaystyle {\text{Nível 3:}}\ \ 266=2\uparrow 2\uparrow (2+1)+2\uparrow (2+1)+2}$

${\displaystyle {\text{Nível 4:}}\ \ 266=2\uparrow \uparrow (2+1)\uparrow 2+2\uparrow \uparrow 2\times 2+2}$

${\displaystyle {\text{Nível 5:}}\ \ 266=2\uparrow \uparrow \uparrow 2\uparrow \uparrow 2+2\uparrow \uparrow \uparrow 2\times 2+2}$.

• Hiperoperação
• Algoritmo do Castor
• Tetração

• Knuth, Donald E., "Coping With Finiteness", Science vol. 194 n. 4271 (Dec 1976), pp. 1235–1242.
• Robert Munafo, Large Numbers