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{array}{ccc}a\times b& =& \underbrace{a+a+\dots +a}\\ & & b\text{ veces }a\end{array}$

Por ejemplo,

$\begin{array}{ccccc}4\times 3& =& \underbrace{4+4+4}& =& 12\\ & & 3\text{ veces }4\end{array}$

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

$\begin{array}{cc}a\uparrow b=a^b=& \underbrace{a\times a\times \dots \times a}\\ & b\text{ veces}a\end{array}$

Por ejemplo,

$\begin{array}{cccc}4\uparrow 3=4^3=& \underbrace{4\times 4\times 4}& =& 64\\ & 3\text{ veces }4\end{array}$

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

Por ejemplo,

$\begin{array}{cccccccccc}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\text{ veces }4& & 3\text{ veces }4\end{array}$

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

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