Notación flecha de Knuth

En matemáticas, la notación flecha de Knuth es un método de notación para enteros muy grandes, introducido por Donald Knuth en 1976.​ Está estrechamente relacionada con la función de Ackermann y especialmente a la sucesión de hiperoperaciones. La idea está basada en el hecho de que la multiplicación puede ser vista como una adición iterada y la potenciación como una multiplicación iterada. Continuando de esta manera, se llega a la potenciación iterada (tetración) y al resto de la sucesión de hiperoperaciones, la cual es generalmente denotada usando la notación flecha de Knuth.

Introducción

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:

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

Por ejemplo,

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

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

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

Por ejemplo,

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

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

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

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

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

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

$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 $n$operador flecha se expande hacia una asociativa por derecha de la serie de ($n-1$)operadores-flecha. Simbólicamente,

Ejemplos:

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

La notación $a\uparrow ^{n}b$ se utiliza comúnmente para denotar $a\uparrow \uparrow \dots \uparrow b$ con n flechas. De hecho, $a\uparrow ^{n}b$ es a [n+2] b con hiperoperación. Por ejemplo, $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, $77\uparrow ^{77}77=$ 77 [79] 77 en lugar de 77 [77] 77.

Notación

En expresiones como a $a^{b}$, la notación de la potenciación es usualmente es por lo general escribir el exponente $b$ como superíndice de la base $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 $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 $a^{b}$ no se presta bien a la generalización, lo que explica por qué Knuth eligió desarrollar la notación flecha $a\uparrow b$ en su lugar.

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

Escribir la notación flecha en términos de potencias

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

Por ejemplo: $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.

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

Continuando con esta notación, $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.

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

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

Por otra parte, $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:

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

Referencias

• Datos: Q908427