Notación de flecha hacia arriba de Knuth

Método de notación de números enteros muy grandes

En matemáticas , la notación de flecha hacia arriba de Knuth es un método de notación para números 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 adición ( n = 1), multiplicación ( n = 2), exponenciación ( n = 3), tetración ( n = 4), pentación ( n = 5), etc. Se han utilizado varias notaciones para representar hiperoperaciones. Una de esas notaciones es . La notación de flecha hacia arriba de Knuth es otra. Por ejemplo: ${\displaystyle H_{n}(a,b)}$ ${\displaystyle \uparrow }$

• La flecha única representa la exponenciación (multiplicación iterada) ${\displaystyle \uparrow }$ $${\displaystyle 2\uparrow 4=H_{3}(2,4)=2\times (2\times (2\times 2))=2^{4}=16}$$
• La flecha doble representa la tetración (exponenciación iterada). ${\displaystyle \uparrow \uparrow }$ $${\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 representa la pentación (tetración iterada). ${\displaystyle \uparrow \uparrow \uparrow }$ $${\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 \dots ))} \;=\;\underbrace {\;2^{2^{\cdots ^{2}}}} \\&\;\;\;\;\;2\uparrow \uparrow 4{\mbox{ copies of }}2\;\;\;\;\;{\mbox{65,536 2s}}\\\end{aligned}}}$$

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

Introducción

Las hiperoperaciones extienden naturalmente las operaciones aritméticas de adición y multiplicación de la siguiente manera. La adición por un número natural se define como incremento iterado:

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

La exponenciación de una potencia natural se define como una multiplicación iterada, que Knuth denota con una única flecha hacia arriba: ${\displaystyle b}$

${\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 denota con una “flecha doble”:

${\displaystyle {\begin{matrix}a\uparrow \uparrow b=H_{4}(a,b)=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \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}&\approx &1.34078079\times 10^{154}&\\&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 para ser asociativos a 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}\approx 1.2580143\times 10^{3638334640024}}$

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{3^{27}}}=3^{3^{7625597484987}}\approx 3^{1.2580143\times 10^{3638334640024}}}$

etc.

Esto ya conduce a algunos números bastante grandes, pero la secuencia de hiperoperadores no termina aquí.

La pentación , definida como tetración iterada, se representa mediante la “triple flecha”:

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

La hexación , definida como pentación iterada, se representa mediante 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 (\dots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

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

${\displaystyle {\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } _{n}\ b=\underbrace {a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } _{n-1}\ (a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } _{n-1}\ (\dots \ \underbrace {\uparrow _{}\!\!\dots \!\!\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{matrix}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{\mbox{ copies of }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \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}}}$

Notación

En expresiones como , la notación para la exponenciación es generalmente escribir el exponente como un superíndice al número base . Pero muchos entornos, como los lenguajes de programación y el correo electrónico de texto simple , no admiten la composición tipográfica en superíndice . La gente ha adoptado la notación lineal para dichos entornos; la flecha hacia arriba sugiere "elevar a la potencia de". Si el conjunto de caracteres no contiene una flecha hacia arriba, se utiliza el signo de intercalación (^) en su lugar. ${\displaystyle a^{b}}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle a\uparrow b}$

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

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

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

Intentar escribir utilizando la notación de superíndice familiar da como resultado una torre de potencia . ${\displaystyle a\uparrow \uparrow b}$

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

Si es una variable (o es demasiado grande), la torre de potencia podría escribirse utilizando puntos y una nota que indique la altura de la torre. ${\displaystyle b}$

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

Continuando con esta notación, se podría escribir con una pila de tales torres de energía, cada una describiendo el tamaño de la que está encima. ${\displaystyle a\uparrow \uparrow \uparrow b}$

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

Nuevamente, si es una variable o es demasiado grande, la pila podría escribirse usando puntos y una nota que indique su altura. ${\displaystyle b}$

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

Además, se podría escribir utilizando varias columnas de dichas pilas de torres de energía, cada columna describiendo el número de torres de energía en la pila a su izquierda: ${\displaystyle a\uparrow \uparrow \uparrow \uparrow b}$

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

Y de manera más general:

${\displaystyle a\uparrow \uparrow \uparrow \uparrow b=\underbrace {\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\}\cdots \right\}a} _{b}}$

Esto se puede llevar a cabo indefinidamente para representarlo como una exponenciación iterada de una exponenciación iterada para cualquier , , y (aunque claramente se vuelve bastante engorroso). ${\displaystyle a\uparrow ^{n}b}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle b}$

Usando tetración

La notación de Rudy Rucker para tetración nos permite hacer estos diagramas un poco más simples mientras aún empleamos una representación geométrica (podríamos llamarlas torres de tetración ). ${\displaystyle ^{b}a}$

${\displaystyle a\uparrow \uparrow b={}^{b}a}$

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

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

Finalmente, a modo de ejemplo, el cuarto número de Ackermann podría representarse como: ${\displaystyle 4\uparrow ^{4}4}$

${\displaystyle \underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{4}}}=\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{\underbrace {^{^{^{^{^{4}.}.}.}4}4} _{^{^{^{4}4}4}4}}}$

Generalizaciones

Algunos números son tan grandes que usar varias flechas de la notación de flecha hacia arriba de Knuth resulta demasiado engorroso; en ese caso, resulta útil un operador de n flechas (y también para descripciones con una cantidad variable de flechas) o, equivalentemente, hiperoperadores . ${\displaystyle \uparrow ^{n}}$

Algunos números son tan grandes que ni siquiera esa notación es suficiente. En ese caso, se puede utilizar la notación de flecha encadenada de Conway : una cadena de tres elementos es equivalente a las otras notaciones, pero una cadena de cuatro o más es aún más poderosa.

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

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

${\displaystyle 10\uparrow (3\times 10\uparrow (3\times 10\uparrow 15)+3)}$= o (Petillón) ${\displaystyle \underbrace {100000...000} _{\underbrace {300000...003} _{\underbrace {300000...000} _{15}}}}$ ${\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 iteraciones sucesivas de funciones y diagonalización para crear sistemáticamente funciones de crecimiento más rápido a partir de alguna función base . Para la jerarquía de crecimiento rápido estándar que utiliza , ya exhibe un crecimiento exponencial, es comparable al crecimiento tetracional y está acotado superiormente por una función que involucra los primeros cuatro hiperoperadores;. Entonces, es comparable a la función de Ackermann , ya está fuera del alcance de las flechas indexadas pero se puede utilizar para aproximar el número de Graham y es comparable a la notación de flecha encadenada de Conway de longitud arbitraria. ${\displaystyle f(x)}$ ${\displaystyle f_{0}(x)=x+1}$ ${\displaystyle f_{2}(x)}$ ${\displaystyle f_{3}(x)}$ ${\displaystyle f_{\omega }(x)}$ ${\displaystyle f_{\omega +1}(x)}$ ${\displaystyle f_{\omega ^{2}}(x)}$

Todas estas funciones son computables. Incluso funciones computables más rápidas, como la secuencia de Goodstein y la secuencia TREE que requieren el uso de ordinales grandes, pueden aparecer en ciertos contextos combinatorios y teóricos de demostración. Existen funciones que crecen a una velocidad incalculable, como la función Busy Beaver , cuya naturaleza misma estará completamente fuera del alcance de cualquier análisis basado en flechas hacia arriba o incluso de cualquier análisis basado en ordinales.

Definición

Sin referencia a la hiperoperación, los operadores de flecha hacia arriba se pueden definir 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 con ^{[nb 1]} . ${\displaystyle a,b,n}$ ${\displaystyle a\geq 0,n\geq 1,b\geq 0}$

Esta definición utiliza la exponenciación como caso base y la tetración 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 , adición y multiplicación . ${\displaystyle (a\uparrow ^{1}b=a\uparrow b=a^{b})}$ ${\displaystyle (a\uparrow ^{2}b=a\uparrow \uparrow b)}$

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

${\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 con . ${\displaystyle a,b,n}$ ${\displaystyle a\geq 0,n\geq 0,b\geq 0}$

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

${\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 hacia la derecha , es decir, se entiende que es , en lugar de . Si la ambigüedad no es un problema, a veces se omiten los paréntesis. ${\displaystyle a\uparrow b\uparrow c}$ ${\displaystyle a\uparrow (b\uparrow c)}$ ${\displaystyle (a\uparrow b)\uparrow c}$

Tablas de valores

Computación 0↑norte b

Calcular resultados en ${\displaystyle 0\uparrow ^{n}b=H_{n+2}(0,b)=0[n+2]b}$

0, cuando n = 0  ^{[nb 2]}

1, cuando n = 1 y b = 0   ^{[nb 1] [nb 3]}

0, cuando n = 1 y b > 0   ^{[nb 1] [nb 3]}

1, cuando n > 1 y b es par (incluido 0)

0, cuando n > 1 y b es impar

Computación 2↑norte b

La computación se puede replantear en términos de una tabla infinita. Colocamos los números en la fila superior y llenamos la columna izquierda con valores 2. Para determinar un número en la tabla, tomamos el número inmediatamente a la izquierda y luego buscamos el número requerido en la fila anterior, en la posición dada por el número recién tomado. ${\displaystyle 2\uparrow ^{n}b}$ ${\displaystyle 2^{b}}$

La tabla es la misma que la de la función de Ackermann , excepto por un desplazamiento en y , y una adición de 3 a todos los valores. ${\displaystyle n}$ ${\displaystyle b}$

Computación 3↑norte b

Colocamos los números en la fila superior y llenamos la columna de la izquierda con los valores 3. Para determinar un número en la tabla, tomamos el número inmediatamente a la izquierda, luego buscamos el número requerido en la fila anterior, en la posición dada por el número que acabamos de tomar. ${\displaystyle 3^{b}}$

Computación 4↑norte b

Colocamos los números en la fila superior y llenamos la columna de la izquierda con los valores 4. Para determinar un número en la tabla, tomamos el número inmediatamente a la izquierda, luego buscamos el número requerido en la fila anterior, en la posición dada por el número que acabamos de tomar. ${\displaystyle 4^{b}}$

Computación 10↑norte b

Colocamos los números en la fila superior y llenamos la columna de la izquierda con valores 10. Para determinar un número en la tabla, tomamos el número inmediatamente a la izquierda, luego buscamos el número requerido en la fila anterior, en la posición dada por el número que acabamos de tomar. ${\displaystyle 10^{b}}$

Para 2 ≤ b ≤ 9 el orden numérico de los números es el orden lexicográfico con n como el número más significativo, por lo que para los números de estas 8 columnas el orden numérico es simplemente línea por línea. Lo mismo se aplica para los números en las 97 columnas con 3 ≤ b ≤ 99, y si comenzamos desde n = 1 incluso para 3 ≤ b ≤ 9,999,999,999. ${\displaystyle 10\uparrow ^{n}b}$

Véase también

• Recursión primitiva
• Hiperoperación
• Castor ocupado
• Notación de barra de Cutler
• Tetración
• Pentación
• Función de Ackermann
• El número de Graham
• Notación Steinhaus-Moser

Notas

1. Para más detalles, véase Potencias de cero .
2. Tenga en cuenta que Knuth no definió el operador . ${\displaystyle \uparrow ^{0}}$
3. Para más detalles, véase Cero elevado a cero .

Referencias

1. Knuth, Donald E. (1976). "Matemáticas y Ciencias de la Computación: Cómo afrontar la finitud". Science . 194 (4271): 1235–1242. Bibcode :1976Sci...194.1235K. doi :10.1126/science.194.4271.1235. PMID  17797067. S2CID  1690489.
2. RL Goodstein (diciembre de 1947). "Ordinales transfinitos en la teoría de números recursivos". Journal of Symbolic Logic . 12 (4): 123–129. doi :10.2307/2266486. JSTOR  2266486. S2CID  1318943.

Enlaces externos

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