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\}b$

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\}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}a$

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\}\cdots \right\}a} _{b}$

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\}b$

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₁ 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$.

Ver também

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

Ligações externas

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