Notación flecha de Knuth

Las operaciones aritméticas normales de adición, multiplicación, y potenciación es naturalmente extendida a una sucesión de hiperoperaciones como sigue.

La multiplicación por un número natural está definida como una adición iterada:

${\displaystyle {\begin{matrix}a\times b&=&\underbrace {a+a+\dots +a} \\&&b{\mbox{ veces }}a\end{matrix}}}$

Por ejemplo,

${\displaystyle {\begin{matrix}4\times 3&=&\underbrace {4+4+4} &=&12\\&&3{\mbox{ veces }}4\end{matrix}}}$

La potenciación para un exponente natural ${\displaystyle b}$ se define como una multiplicación iterada, que Knuth denota por una sola flecha arriba:

${\displaystyle {\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ veces }}a\end{matrix}}}$

Por ejemplo,

${\displaystyle {\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3{\mbox{ veces }}4\end{matrix}}}$

Para ampliar la secuencia de operaciones más allá de la potenciación, Knuth definió un operador "doble flecha" para denotar la potenciación iterada (tetración):

${\displaystyle {\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\&&b{\mbox{ veces }}a&&b{\mbox{ veces }}a\end{matrix}}}$

Por ejemplo,

${\displaystyle {\begin{matrix}4\uparrow \uparrow 3&={\ ^{3}4}=&\underbrace {4^{4^{4}}} &=&\underbrace {4\uparrow (4\uparrow 4)} &=&4^{256}&\approx &1.34078079\times 10^{154}&\\&&3{\mbox{ veces }}4&&3{\mbox{ veces }}4\end{matrix}}}$

Aquí y a continuación la evaluación se llevará a cabo de derecha a izquierda, así los operadores flecha de Knuth (como la potenciación) se definen como asociativos por derecha.

De acuerdo a esta definición,

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

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7625597484987\approx 7.6\times 10^{12}}$

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580740420492718971\times 10^{3638334640024}}$

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}}$

etc.

Esto conduce ya a unos números bastante grandes, pero Knuth ampliado de la notación. Pasó a definir un operador "triple flecha" para tetración iterada (pentación):

seguido por un operador "cuádruple flecha" para definir la pentación iterada (hexación):

y así sucesivamente. La regla general es que un ${\displaystyle n}$operador flecha se expande hacia una asociativa por derecha de la serie de (${\displaystyle n-1}$)operadores-flecha. Simbólicamente,

Ejemplos:

${\displaystyle 3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7,625,597,484,987}$

La notación ${\displaystyle a\uparrow ^{n}b}$ se utiliza comúnmente para denotar ${\displaystyle a\uparrow \uparrow \dots \uparrow b}$ con n flechas. De hecho, ${\displaystyle a\uparrow ^{n}b}$ es a [n+2] b con hiperoperación. Por ejemplo, ${\displaystyle 39\uparrow \uparrow 14}$ también puede ser escrito como 39 [4] 14, la "[4]" significa tetración, pero no igual a 39 [2] 14 = 39 × 14 = 546, del mismo modo, ${\displaystyle 77\uparrow ^{77}77=}$ 77 [79] 77 en lugar de 77 [77] 77.

En expresiones como a ${\displaystyle a^{b}}$, la notación de la potenciación es usualmente es por lo general escribir el exponente ${\displaystyle b}$ como superíndice de la base ${\displaystyle a}$. Pero en muchos entornos — como en los lenguajes de programación y e-mails de texto plano — no son compatibles con composición tipográfica de superíndice. La gente ha adoptado la notación lineal ${\displaystyle a\uparrow b}$ para tales entornos; la flecha hacia arriba sugiere «elevado a» el exponente indicado. Si el juego de caracteres no contiene una flecha hacia arriba, el caret (^) se utiliza en su lugar.

La notación de superíndice ${\displaystyle a^{b}}$ no se presta bien a la generalización, lo que explica por qué Knuth eligió desarrollar la notación flecha ${\displaystyle a\uparrow b}$ en su lugar.

${\displaystyle a\uparrow ^{n}b}$ es una notación alternativa más corta para n flechas. Así ${\displaystyle a\uparrow ^{4}b=a\uparrow \uparrow \uparrow \uparrow b}$.

Intentar escribir ${\displaystyle a\uparrow \uparrow b}$ usando la familiar notación de superíndice da una torre de potencias.

Por ejemplo: ${\displaystyle a\uparrow \uparrow 4=a\uparrow (a\uparrow (a\uparrow a))=a^{a^{a^{a}}}}$

Si b es una variable (o es demasiado grande), la torre de potencias podría ser escrita utilizando puntos y una nota que indique la altura de la torre.

${\displaystyle a\uparrow \uparrow b=\underbrace {a^{a^{.^{.^{.{a}}}}}} _{b}}$

Continuando con esta notación, ${\displaystyle a\uparrow \uparrow \uparrow b}$ puede ser escrito con una pila de tales torres de potencias, cada uno describiendo el tamaño de la pila que está por encima de ella.

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

De nuevo, si b es una variable o es demasiado grande, la pila podría ser escrita utilizando puntos y una nota indicando su altura.

${\displaystyle a\uparrow \uparrow \uparrow b=\left.\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {a^{a^{.^{.^{.{a}}}}}} _{\underbrace {\vdots } _{a}}}\right\}b}$

Por otra parte, ${\displaystyle a\uparrow \uparrow \uparrow \uparrow b}$ podría escribirse usando varias columnas de dichas pilas de torres de potencias, cada columna describe el número de torres de potencias en la pila a su izquierda:

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