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 suma ( 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 doble flecha 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 flecha triple 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 ): ${\displaystyle a\geq 0,n\geq 1,b\geq 0}$

$${\displaystyle a\uparrow ^{n}b=H_{n+2}(a,b)=a[n+2]b.}$$

n ${\displaystyle \uparrow ^{n}}$

$${\displaystyle 2\uparrow \uparrow \uparrow \uparrow 3=2\uparrow ^{4}3.}$$

Introducción

Las hiperoperaciones naturalmente extienden las operaciones aritméticas de suma y multiplicación de la siguiente manera. La suma de 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 sola 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 una exponenciación iterada, que Knuth denota con una “doble flecha”:

${\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 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}\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 lleva a algunos números bastante grandes, pero la secuencia del hiperoperador no se detiene aquí.

La pentación , definida como tetración iterada, está representada por 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, 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 (\dots \uparrow \uparrow \uparrow a))} \\&b{\mbox{ copies of }}a\end{matrix}}}$

etcétera. 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 exponenciación suele ser escribir el exponente como un superíndice del número base . 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 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 (^). ${\displaystyle a^{b}}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle a\uparrow b}$

La notación en superíndice 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^{b}}$ ${\displaystyle a\uparrow b}$

${\displaystyle a\uparrow ^{n}b}$es una notación alternativa más corta para n uparrows. De este modo . ${\displaystyle a\uparrow ^{4}b=a\uparrow \uparrow \uparrow \uparrow b}$

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

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

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 energía podría escribirse usando 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, 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 b es una variable o es demasiado grande, la pila podría escribirse usando puntos y una nota que indique su altura.

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

Además, podría escribirse usando varias columnas de dichas pilas de torres de energía, describiendo cada columna 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 podría llevarse a cabo indefinidamente para representar como exponenciación iterada de exponenciación iterada para cualquier a , n y b (aunque claramente se vuelve bastante engorroso). ${\displaystyle a\uparrow ^{n}b}$

Usando tetración

La notación de Rudy Rucker para la tetración nos permite simplificar un poco estos diagramas sin dejar de emplear una representación geométrica (podríamos llamar a estas 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 las múltiples flechas de la notación de flecha hacia arriba de Knuth se vuelven demasiado engorrosas; entonces un operador de n flechas es útil (y también para descripciones con un número variable de flechas) o, de manera equivalente, hiperoperadores . ${\displaystyle \uparrow ^{n}}$

Algunos números son tan grandes que ni siquiera esa notación es suficiente. Entonces se puede utilizar la notación de flechas encadenadas 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 (Petillion) ${\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 mediante un análisis ordinal llamado jerarquía de rápido crecimiento . La jerarquía de rápido crecimiento utiliza iteraciones y diagonalizaciones sucesivas de funciones para crear sistemáticamente funciones de crecimiento más rápido a partir de alguna función base . Para la jerarquía estándar de rápido crecimiento , el uso de , ya muestra un crecimiento exponencial, es comparable al crecimiento tetracional y está limitado superiormente por una función que involucra a los primeros cuatro hiperoperadores;. Entonces, es comparable a la función de Ackermann , ya está más allá del alcance de las flechas indexadas, pero puede usarse para aproximar el número de Graham y es comparable a la notación de flechas encadenadas de Conway arbitrariamente larga. ${\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 ocurrir en ciertos contextos combinatorios y de teoría de prueba. Existen funciones que crecen incomputablemente rápido, como Busy Beaver , cuya naturaleza misma estará completamente fuera del alcance de cualquier análisis de flecha 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 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 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 , suma 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 desde allí. 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}$

Tenga en cuenta, sin embargo, que Knuth no definió la "flecha nula" ( ). Se podría extender la notación a índices negativos (n ≥ -2) de tal manera que concuerde con toda la secuencia de hiperoperación, excepto por el retraso 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 por la derecha , es decir, se entiende que es , en lugar de . Si la ambigüedad no es un problema, a veces se eliminan los paréntesis. ${\displaystyle a\uparrow b\uparrow c}$ ${\displaystyle a\uparrow (b\uparrow c)}$ ${\displaystyle (a\uparrow b)\uparrow c}$

Tablas de valores

Calculando 0 ↑ n  b

La computación da como resultado ${\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 ↑ n  b

La informática se puede reformular en términos de una tabla infinita. Colocamos los números en la fila superior y llenamos la columna de la izquierda con los valores 2. Para determinar un número en la tabla, tome el número inmediatamente a la izquierda, luego busque el número requerido en la fila anterior, en la posición dada por el número que acaba de tomar. ${\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 suma de 3 a todos los valores. ${\displaystyle n}$ ${\displaystyle b}$

Computación 3 ↑ n  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, tome el número inmediatamente a la izquierda, luego busque el número requerido en la fila anterior, en la posición dada por el número que acaba de tomar. ${\displaystyle 3^{b}}$

Computación 4 ↑ n  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, tome el número inmediatamente a la izquierda, luego busque el número requerido en la fila anterior, en la posición dada por el número que acaba de tomar. ${\displaystyle 4^{b}}$

Computación 10 ↑ n  b

Colocamos los números en la fila superior y llenamos la columna de la izquierda con los valores 10. Para determinar un número en la tabla, tome el número inmediatamente a la izquierda, luego busque el número requerido en la fila anterior, en la posición dada por el número que acaba 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 a los números de las 97 columnas con 3 ≤ b ≤ 99, y si partimos de n = 1 incluso para 3 ≤ b ≤ 9.999.999.999. ${\displaystyle 10\uparrow ^{n}b}$

Ver también

• recursividad 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 obtener más detalles, consulte Potencias de cero .
2. Tenga en cuenta que Knuth no definió al operador . ${\displaystyle \uparrow ^{0}}$
3. Para obtener más detalles, consulte Cero elevado a cero .

Referencias

1. Knuth, Donald E. (1976). "Matemáticas e Informática: afrontar la finitud". Ciencia . 194 (4271): 1235-1242. Código Bib : 1976 Ciencia... 194.1235K. doi : 10.1126/ciencia.194.4271.1235. PMID  17797067. S2CID  1690489.
2. RL Goodstein (diciembre de 1947). "Ordinales transfinitos en teoría de números recursivos". Revista de Lógica Simbólica . 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". MundoMatemático .
• Robert Munafo, Grandes números: hiperoperadores superiores