Notación de flecha hacia arriba de Knuth

En matemáticas , la notación de flecha hacia arriba de Knuth es un método de notación para enteros muy grandes , introducido por Donald Knuth en 1976. ^{[ 1 ]}

En su artículo de 1947, ^{[ 2 ]} RL Goodstein introdujo la secuencia específica de operaciones que ahora se denominan hiperoperaciones . Goodstein también sugirió los nombres griegos tetración , pentación, etc., para las operaciones extendidas más allá de la exponenciación . La secuencia comienza con una operación unaria (la función sucesora con n = 0) y continúa con las operaciones binarias de suma ( n = 1 ), multiplicación ( n = 2 ), exponenciación ( n = 3 ), tetración ( n = 4 ), etc. Se han utilizado diversas notaciones para representar las hiperoperaciones. Una de estas notaciones es${\displaystyle H_{n}(a,b)}$Notación de flecha hacia arriba de Knuth${\displaystyle \uparrow }$es otro. Por ejemplo:

• la flecha única${\displaystyle \uparrow }$representa la exponenciación (multiplicación iterada)$${\displaystyle 2\uparrow 4=H_{3}(2,4)=2\times (2\times (2\times 2))=2^{4}=16}$$
• la flecha doble${\displaystyle \uparrow \uparrow }$representa la tetración (exponenciación iterada)$${\displaystyle 2\uparrow \uparrow 4=H_{4}(2,4)=2\uparrow (2\uparrow (2\uparrow 2))=2^{2^{2^{2}}}=2^{16}=65,536}$$
• la triple flecha${\displaystyle \uparrow \uparrow \uparrow }$representa la pentación (tetración iterada)$${\displaystyle {\begin{aligned}2\uparrow \uparrow \uparrow 4&=H_{5}(2,4)\\&=2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow \uparrow 2))\\&=2\uparrow \uparrow (2\uparrow \uparrow (2\uparrow 2))\\&=2\uparrow \uparrow (2\uparrow \uparrow 4)\\&=\underbrace {2\uparrow (2\uparrow (2\uparrow \cdots ))} \;=\;\underbrace {\;2^{2^{\cdots ^{2}}}} \\&\;\;\;\;\;2\uparrow \uparrow 4{\text{ copies of }}2\;\;\;\;\;{\text{65,536 2's}}\\\end{aligned}}}$$

La definición general de la notación de flecha hacia arriba es la siguiente (para${\displaystyle a\geq 0,n\geq 1,b\geq 0}$): $${\displaystyle a\uparrow ^{n}b=H_{n+2}(a,b)=a[n+2]b.}$$ Aquí,${\displaystyle \uparrow ^{n}}$representa n flechas, por ejemplo $${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 3=2\uparrow ^{4}3,}$$ y los corchetes utilizados en la expresión del extremo derecho son otra notación para hiperoperaciones.

Las hiperoperaciones extienden de forma natural las operaciones aritméticas de suma y multiplicación de la siguiente manera.

La suma de un número natural se define como un incremento iterativo:

${\displaystyle {\begin{matrix}H_{1}(a,b)=a+b=&a+\underbrace {1+1+\dots +1} \\&b{\mbox{ copies of }}1\end{matrix}}}$

La multiplicación por un número natural se define como una suma iterada:

${\displaystyle {\begin{matrix}H_{2}(a,b)=a\times b=&\underbrace {a+a+\dots +a} \\&b{\mbox{ copies of }}a\end{matrix}}}$

Por ejemplo,

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

Exponenciación para una potencia natural${\displaystyle b}$se define como multiplicación iterada, que Knuth denotó con una sola flecha hacia arriba:

${\displaystyle {\begin{matrix}a\uparrow b=H_{3}(a,b)=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ copies of }}a\end{matrix}}}$

Por ejemplo,

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

La tetración se define como exponenciación iterada, que Knuth denotó mediante una "doble flecha":

${\displaystyle {\begin{matrix}a\uparrow \uparrow b=H_{4}(a,b)=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\cdots \uparrow a))} \\&b{\mbox{ copies of }}a&&b{\mbox{ copies of }}a\end{matrix}}}$

Por ejemplo,

${\displaystyle {\begin{matrix}4\uparrow \uparrow 3=&\underbrace {4^{4^{4}}} &=&\underbrace {4\uparrow (4\uparrow 4)} &=&4^{256}&&\\&3{\mbox{ copies of }}4&&3{\mbox{ copies of }}4\end{matrix}}}$

Las expresiones se evalúan de derecha a izquierda, ya que los operadores están definidos como asociativos por la derecha .

Según esta definición,

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

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

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

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

etc.

Esto ya da lugar a números bastante grandes, pero la secuencia de hiperoperadores no termina aquí. La pentación, definida como tetración iterada, está representada por la "flecha triple":

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=H_{5}(a,b)=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\cdots \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

La hexación, definida como pentación iterada, está representada por la "flecha cuádruple":

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=H_{6}(a,b)=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\cdots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

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

${\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\cdots \!\!\uparrow } _{n}\ b=\underbrace {a\ \underbrace {\uparrow \!\!\cdots \!\!\uparrow } _{n-1}\ (a\ \underbrace {\uparrow _{}\!\!\cdots \!\!\uparrow } _{n-1}\ (\cdots \ \underbrace {\uparrow _{}\!\!\cdots \!\!\uparrow } _{n-1}\ a))} _{b{\text{ copies of }}a}\end{matrix}}}$

Ejemplos:

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

${\displaystyle {\begin{aligned}3\uparrow \uparrow \uparrow 3&=3\uparrow \uparrow (3\uparrow \uparrow 3)\\&=3\uparrow \uparrow (3\uparrow 3\uparrow 3)\\&={\begin{matrix}\underbrace {3\uparrow 3\uparrow \cdots \uparrow 3} \\3\uparrow 3\uparrow 3{\mbox{ copies of }}3\end{matrix}}\\&={\begin{matrix}\underbrace {3\uparrow 3\uparrow \cdots \uparrow 3} \\{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}\\&={\begin{matrix}\underbrace {3^{3^{3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}}}} \\{\mbox{7,625,597,484,987 copies of 3}}\end{matrix}}\end{aligned}}}$

En expresiones como${\displaystyle a^{b}}$, la notación para la exponenciación suele ser escribir el exponente${\displaystyle b}$como superíndice del número base${\displaystyle a}$Pero muchos entornos , como los lenguajes de programación y el correo electrónico de texto plano , no admiten la composición tipográfica en superíndice . La gente ha adoptado la notación lineal.${\displaystyle a\uparrow b}$Para este tipo de entornos, la flecha hacia arriba sugiere "elevar a la potencia de". Si el conjunto de caracteres no incluye una flecha hacia arriba, se utiliza el acento circunflejo (^).

La notación en superíndice${\displaystyle a^{b}}$no se presta bien a la generalización, lo que explica por qué Knuth optó por trabajar con la notación en línea.${\displaystyle a\uparrow b}$en cambio.

${\displaystyle a\uparrow ^{n}b}$es una notación alternativa más corta para n flechas hacia arriba. Por lo tanto${\displaystyle a\uparrow ^{4}b=a\uparrow \uparrow \uparrow \uparrow b}$.

Algunos números son tan grandes que las múltiples flechas de la notación de flecha hacia arriba de Knuth se vuelven demasiado engorrosas; entonces se utiliza un operador de n flechas. ${\displaystyle \uparrow ^{n}}$es útil (y también para descripciones con un número variable de flechas), o equivalentemente, hiperoperadores .

Algunos números son tan grandes que incluso esa notación resulta insuficiente. En ese caso, se puede utilizar la notación de flechas encadenadas de Conway : una cadena de tres elementos es equivalente a las demás notaciones, pero una cadena de cuatro o más es aún más potente.

${\displaystyle {\begin{matrix}a\uparrow ^{n}b&=&a[n+2]b&=&a\to b\to n\\{\text{(Knuth)}}&&{\text{(hyperoperation)}}&&{\text{(Conway)}}\end{matrix}}}$

${\displaystyle 6\uparrow \uparrow 4=\underbrace {6^{6^{.^{.^{.^{6}}}}}} _{4}}$, Desde${\displaystyle 6\uparrow \uparrow 4=6^{6^{6^{6}}}=6^{6^{46,656}}}$, Por lo tanto, el resultado es${\displaystyle \underbrace {6^{6^{.^{.^{.^{6}}}}}} _{4}}$

${\displaystyle 10\uparrow (3\times 10\uparrow (3\times 10\uparrow 15)+3)=\underbrace {100000\ldots 000} _{\underbrace {300000\ldots 003} _{\underbrace {300000\ldots 000} _{15}}}}$o${\displaystyle 10^{3\times 10^{3\times 10^{15}}+3}}$

Incluso las funciones de crecimiento más rápido se pueden categorizar utilizando un análisis ordinal llamado jerarquía de crecimiento rápido . La jerarquía de crecimiento rápido utiliza iteración y diagonalización sucesivas de funciones para crear sistemáticamente funciones de crecimiento más rápido a partir de alguna función base.${\displaystyle f(x)}$Para la jerarquía estándar de rápido crecimiento que utiliza${\displaystyle f_{0}(x)=x+1}$,${\displaystyle f_{2}(x)}$ya muestra un crecimiento exponencial,${\displaystyle f_{3}(x)}$es comparable al crecimiento tetracional y está acotado superiormente por una función que involucra los primeros cuatro hiperoperadores;. Entonces,${\displaystyle f_{\omega }(x)}$es comparable a la función de Ackermann ,${\displaystyle f_{\omega +1}(x)}$ya está fuera del alcance de las flechas indexadas pero se puede utilizar para aproximar el número de Graham y${\displaystyle f_{\omega ^{2}}(x)}$es comparable a la notación de flechas encadenadas de Conway de longitud arbitraria.

Todas estas funciones son computables. Las funciones computables más rápidas, como la secuencia de Goodstein y la secuencia TREE , requieren el uso de ordinales grandes y pueden aparecer en ciertos contextos combinatorios y de teoría de la demostración. Existen funciones que crecen a una velocidad incalculable, como la del "Busy Beaver" , que por su propia naturaleza estarán completamente fuera del alcance de cualquier análisis basado en flechas ascendentes o incluso en ordinales.

Sin referencia a la hiperoperación, los operadores de flecha hacia arriba pueden definirse formalmente mediante

${\displaystyle a\uparrow ^{n}b={\begin{cases}a^{b},&{\text{if }}n=1;\\1,&{\text{if }}n>1{\text{ and }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\text{otherwise }}\end{cases}}}$

para todos los números enteros${\displaystyle a,b,n}$con${\displaystyle a\geq 0,n\geq 1,b\geq 0}$. ^{[ nb 1 ]}

Esta definición utiliza la exponenciación.${\displaystyle (a\uparrow ^{1}b=a\uparrow b=a^{b})}$como caso base y tetración${\displaystyle (a\uparrow ^{2}b=a\uparrow \uparrow b)}$como exponenciación repetida. Esto es equivalente a la secuencia de hiperoperaciones excepto que omite las tres operaciones más básicas de sucesión , suma y multiplicación .

También se puede elegir la multiplicación.${\displaystyle (a\uparrow ^{0}b=a\times b)}$como caso base y a partir de ahí iterar. Entonces la exponenciación se convierte en multiplicación repetida. La definición formal sería

${\displaystyle a\uparrow ^{n}b={\begin{cases}a\times b,&{\text{if }}n=0;\\1,&{\text{if }}n>0{\text{ and }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\text{otherwise }}\end{cases}}}$

para todos los números enteros${\displaystyle a,b,n}$con${\displaystyle a\geq 0,n\geq 0,b\geq 0}$.

Sin embargo, tenga en cuenta que Knuth no definió la "flecha nula" (${\displaystyle \uparrow ^{0}}$). Se podría extender la notación a índices negativos (n ≥ -2) de tal manera que coincida con toda la secuencia de hiperoperaciones, excepto por el retraso en la indexación:

${\displaystyle H_{n}(a,b)=a[n]b=a\uparrow ^{n-2}b{\text{ for }}n\geq 0.}$

La operación de flecha hacia arriba es una operación asociativa derecha , es decir,${\displaystyle a\uparrow b\uparrow c}$se entiende que es${\displaystyle a\uparrow (b\uparrow c)}$, en lugar de${\displaystyle (a\uparrow b)\uparrow c}$Si la ambigüedad no es un problema, a veces se omiten los paréntesis.

• Recursión primitiva
• Notación de barras de Cutler
• Notación de Steinhaus-Moser

• Weisstein, Eric W. "Notación de flecha hacia arriba de Knuth" . MathWorld .
• Robert Munafo, Grandes números: hiperoperadores superiores