Notação de Knuth

Predefinição:Sem-fontes 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{array}{ccc}a\times b& =& \underbrace{a+a+\dots +a}\\ & & b\text{ cópias de }a\end{array}$

Por exemplo,

$\begin{array}{ccccc}4\times 3& =& \underbrace{4+4+4}& =& 12\\ & & 3\text{ cópias de }4\end{array}$

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{array}{cc}a\uparrow b=a^b=& \underbrace{a\times a\times \dots \times a}\\ & b\text{ cópias de }a\end{array}$

Por exemplo,

$\begin{array}{cccc}4\uparrow 3=4^3=& \underbrace{4\times 4\times 4}& =& 64\\ & 3\text{ cópias de }4\end{array}$

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{array}{ccccc}a\uparrow \uparrow b& ={}^{b}a=& \underbrace{a^{a^{{}^{.{}^{.{}^{.{}^a}}}}}}& =& \underbrace{a\uparrow (a\uparrow (\dots \uparrow a))}\\ & & b\text{ cópias de }a& & b\text{ cópias de }a\end{array}$

Por exemplo,

$\begin{array}{ccccccc}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\text{ cópias de }4& & 3\text{ cópias de }4\end{array}$

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{array}{cc}a\uparrow \uparrow \uparrow b=& \underbrace{a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))}\\ & b\text{ cópias de }a\end{array}$

seguido por um operador de 'seta quádrupla':

$\begin{array}{cc}a\uparrow \uparrow \uparrow \uparrow b=& \underbrace{a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))}\\ & b\text{ cópias de }a\end{array}$

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{array}{c}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\\ n\underbrace{n_{}-1n-1n-1}\\ b\text{ cópias de }a\end{array}$

Exemplos:

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

$\begin{array}{cc}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\text{ cópias de }3\end{array}\begin{array}{cc}=& \underbrace{3_{}\uparrow 3\uparrow \dots \uparrow 3}\\ & \text{7.625.597.484.987 cópias de 3}\end{array}$

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=\underset{b}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}$

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=\underset{\underset{\underset{a}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{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=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}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=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}a$

E de forma mais geral:

$a\uparrow \uparrow \uparrow \uparrow b=\underset{b}{\underbrace{\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\cdots \}a}}$

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=\underset{b}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}$

$a\uparrow \uparrow \uparrow \uparrow b=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}}{\underbrace{{}^{{}^{{}^{{}^{{}^a.}.}.}a}a}}\}b$

Finalmente, a título de exemplo, o quarto número de Ackermann $4{\uparrow }^{4}4$ poderia ser representado como:

$\underset{\underset{\underset{4}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}=\underset{\underset{{}^{{}^{{}^{4}4}4}4}{\underbrace{{}^{{}^{{}^{{}^{{}^4.}.}.}4}4}}}{\underbrace{{}^{{}^{{}^{{}^{{}^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{array}{ccccc}a{\uparrow }^{n}b& =& \text{hyper}(a,n+2,b)& =& a\to b\to n\\ \text{(Knuth)}& & & & \text{(Conway)}\end{array}$

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=\{\begin{array}{cc}{a}^b,& \text{se }n=1;\\ 1,& \text{se }b=0;\\ a{\uparrow }^{n-1}(a{\uparrow }^n(b-1)),& \text{em outro caso}\end{array}$

para todos inteiros $a,b,n$ com $b\ge 0,n\ge 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{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\text{ cópias de }2\end{array}\approx (10\uparrow {)}^{65531}(6.0\times 10^{19,728})$				$2\uparrow \uparrow \uparrow n$
4	2	4	$\begin{array}{c}\underbrace{2_{}^{2^{{}^{.{}^{.{}^{.{}^2}}}}}}\\ 65536\text{ cópias de }2\end{array}$					$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{array}{c}\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}\\ 7.625.597.484.987\text{ cópias de }3\end{array}$			$3\uparrow \uparrow \uparrow n$
4	3	$\begin{array}{c}\underbrace{3_{}^{3^{{}^{.{}^{.{}^{.{}^3}}}}}}\\ 7.625.597.484.987\text{ cópias de }3\end{array}$				$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{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10\text{ cópias de }10\end{array}$	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10^{10}\text{ cópias de }10\end{array}$	$\begin{array}{c}\underbrace{10_{}^{10^{{}^{.{}^{.{}^{.{}^{10}}}}}}}\\ 10^{10^{10}}\text{ cópias de }10\end{array}$		$10\uparrow \uparrow \uparrow n$
4	10	$\begin{array}{c}\underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ 10\text{ cópias de }10\end{array}$	$\begin{array}{c}\underbrace{{}^{{}^{{}^{{}^{{}^{10}.}.}.}10}10}\\ 10^{10}\text{ cópias de }10\end{array}$			$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 ${(}^{(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\le n$

$b^{(k)}{x_k}^{(k-1)}{x}_{k-1}\le n$

...

$b^{(k)}{x_k}^{(k-1)}{x_{k-1}}^{(k-2)}\dots {x_2}^{(1)}{x}_1\le 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