Notación de flecha Knuth

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 5 de septiembre de 2021; las comprobaciones requieren 5 ediciones .

En matemáticas , la notación de flechas de Knuth es un método para escribir números grandes. Su idea se basa en el hecho de que la multiplicación es una suma múltiple , la exponenciación es una multiplicación múltiple. Fue propuesto por Donald Knuth en 1976 [1] . Estrechamente relacionado con la función de Ackermann y la secuencia de hiperoperadores .

Tetration , escrito usando la notación de flecha de Knuth:

{\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{. \,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\&&b&&b\end{matriz}}

Pentación en la notación de Knuth:

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b\ fin {matriz}}

En la notación indicada, existen b operandos, cada uno de los cuales es igual a a , respectivamente, las operaciones se repiten veces. ${\ estilo de visualización b-1}$

Introducción

Las operaciones aritméticas habituales (suma, multiplicación y exponenciación) pueden extenderse naturalmente a una secuencia de hiperoperadores de la siguiente manera:

La multiplicación de números naturales se puede definir mediante una operación de suma repetitiva (“sumar b copias del número a ”):

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

Por ejemplo,

{\begin{matriz}4\times 3&=&\underbrace {4+4+4} &=&12\\&&3\end{matriz}}

Elevar a a la potencia de b puede definirse como una operación de multiplicación repetida ("multiplicar b copias de a "), y en la notación de Knuth, esta notación parece una sola flecha apuntando hacia arriba:

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

Por ejemplo,

{\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3\end{matrix))

Una sola flecha hacia arriba de este tipo se usaba como un icono de grado en el lenguaje de programación Algol .

Continuando con la secuencia de operaciones más allá de la potenciación, Donald Knuth introdujo el concepto del operador de "doble flecha" para escribir tetración (potenciación múltiple).

{\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{. \,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\&&b&&b\end{matriz}}

Por ejemplo,

{\begin{matrix}4\uparrow \uparrow 3&={\ ^{3}4}=&\underbrace {4^{4^{4))} &=&\underbrace {4\uparrow (4) \uparrow 4)} &=&4^{256}\aprox. 1{,}3\times 10^{154}\\&&3&&3\end{matriz}}

Aquí y más abajo, la evaluación de la expresión siempre va de derecha a izquierda, también los operadores de flecha de Knuth (así como la operación de exponenciación) por definición tienen asociatividad derecha (ordenación de derecha a izquierda). Según esta definición,

3\flecha arriba \flecha arriba 2=3^{3}=27

3\flecha arriba \flecha arriba 3=3^{3^{3}}=3^{27}=7\,625\,597\,484\,987

3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}\aprox. 1{,}3\times 10^{3\,638\,334\,640\,024}

3\uparrow \uparrow 5=3^{3^{3^{3^{3))))=3^{3^{7\,625\,597\,484\,987}}

y así.

Esto ya conduce a números bastante grandes, pero la notación no termina ahí. El operador de "flecha triple" se usa para escribir exponenciaciones repetidas del operador de "flecha doble" (también conocido como " pentación "):

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b\ fin {matriz}}

luego el operador de "flecha cuádruple":

{\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))} \\&b\end{matriz}}

y así sucesivamente Como regla general, el operador de flecha n , según la asociatividad derecha , continúa hacia la derecha en una serie secuencial de n -1 operadores de flecha. Simbólicamente, esto se puede escribir de la siguiente manera,

{\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } \ b=a\ \underbrace {\uparrow \!\!\dots \!\!\uparrow } \ a\ \underbrace {\uparrow _{}\!\!\dots \!\!\uparrow } \ a\ \dots \ a\ \underbrace {\uparrow _{}\!\ !\dots \!\!\uparrow } \ a\\\quad \ \ \,n\qquad \ \ \ \underbrace {\quad n_{}\!-\!\!1\quad \ \,n\! -\!\!1\qquad \quad \ \ \ \,n\!-\!\!1\ \ \ } \\\qquad \qquad \quad \ \ b\end{matriz}}

Por ejemplo:

3\flecha arriba \flecha arriba \flecha arriba 2=3\flecha arriba \flecha arriba 3=3^{3^{3}}=3^{27}=7\,625\,597\,484\,987

{\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\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \ flecha arriba 3} \\&7625597484987\end{matriz}}

La forma de notación se usa generalmente para escribir con n flechas. $a\flecha arriba ^{n}b$ $a \ flecha arriba \ flecha arriba \ puntos \ flecha arriba b$

Sistema de notación

En expresiones como , es común escribir el exponente como superíndice de la base para denotar exponenciación . Pero muchos otros entornos, como los lenguajes de programación y el correo electrónico , no admiten esta configuración bidimensional. Por lo tanto, los usuarios deben usar la notación lineal para tales entornos; la flecha hacia arriba sugiere elevar a la potencia de . Si no hay una flecha hacia arriba entre los caracteres disponibles, entonces se usa la marca de inserción correctiva “^” en su lugar . $un ^ {b}$ $b$ $a$ $a\flecha arriba b$ $un ^ {b}$ $a\flecha arriba b$

Designación "↑"

Un intento de escribir una expresión usando la notación familiar con exponentes genera una torre de potencias. Por ejemplo: $a \ flecha arriba \ flecha arriba b$

a\uparrow \uparrow 4=a\uparrow a\uparrow a\uparrow a=a^{{a^{{a^{a}}}}}.

Si b es variable (o muy grande), la torre de grados se puede escribir con puntos y con una notación que indique la altura de la torre.

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

Usando esta forma de notación, la expresión se puede escribir como un conjunto ( pila ) de dichas torres de energía, cada una de las cuales indica el grado de la superposición. $a \ flecha arriba \ flecha arriba \ flecha arriba b$

a\uparrow \uparrow \uparrow 4=a\uparrow \uparrow a\uparrow \uparrow a\uparrow \uparrow a=\underbrace {a^{{a^{{.^{{.^{{.{a}} }})))}}}}_{{\soporte {a^{{a^{{.^{{.^{{.{a}}}}}}}}}}_{{\soporte { a ^{{a^{{.^{{.^{{.{a}}}}}}}}}}_{{a}}}}}}.

Y nuevamente, si b es variable (o muy grande), un conjunto de tales torres de energía puede escribirse usando puntos y rotularse para indicar sus alturas.

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

Además, la expresión se puede escribir usando varias columnas de torres de energía similares, donde cada columna indica el número de torres de energía en el conjunto de la izquierda. $a \ flecha arriba \ flecha arriba \ flecha arriba \ flecha arriba b$

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}}}}}}}}}}_{{\soporte {a^{{a^{{.^{{.^{{.{a )))))))))))_{{\underbrace {\vdots }_{{a))))))\right\}\underbrace {a^{{a^{{.^{{. ^ {{.{a}}}}}}}}}}_{{\soporte inferior {a^{{a^{{.^{{.^{{.{a}}}}}}}}} }_{{\soporte {\vdots}_{{a))))))\right\}\soporte {a^{{a^{{.^{{.^{{.{a)))) } )))))_{{\soporte {a^{{a^{{.^{{.^{{.{a))))))))))_{{\soporte {\vdots} _ {{a}}}}}}\derecho\}a.

Más generalmente:

a\uparrow \uparrow \uparrow \uparrow b=\underbrace {\left.\left.\left.\underbrace {a^{{a^{{.^{{.^{{.{a))))} )))))_{{\soporte {a^{{a^{{.^{{.^{{.{a))))))))))_{{\soporte {\vdots}_ {{a}}}}}}\right\}\underbrace {a^{{a^{{.^{{.^{{.{a}}}}}}}}}}_{{\underbrace {a^{{a^{{.^{{.^{{.{a))))))))))_({\underbrace {\vdots}_{{a))))))) \right\}\cdots\right\}a}_{{b}}.

Esto se puede escribir indefinidamente para representarlo como una iteración de exponenciación para cualquier a , n y b (aunque está claro que esto también se vuelve bastante engorroso). $a\flecha arriba ^{n}b$

Uso de tetración

La notación de tetración permite simplificar dichos esquemas, sin dejar de utilizar una representación geométrica (podemos llamarlos torres de tetración ). $^{{b}}a$

a\flecha arriba \flecha arriba b={}^{b}}a,

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

a\uparrow \uparrow \uparrow \uparrow b=\left.\underbrace {^{{^{{^{{^{{^{{{a}}.}}.}}.}}a}}a} _ {{\soporte {^{{^{{^{{^{{^{{{a}}.}}.}}.}}a}}a}_{{\soporte {\vdots}_{ {a }}}}}}\derecho\}b.

Finalmente, como ejemplo, el cuarto número de Ackermann se puede escribir como: $4\flecha arriba ^{4}4$

\soporte {^{{^{{^{{^{{^{{4}}.}}.}}.}}4}}4}_({\soporte {^{{^{{^{{ ^{{^{{4}}.}}.}}.}}4}}4}_{{\soporte {^{{^{{^{{^{{^{{4}}.}} .}}.}}4}}4}_{{4}}}}}}=\soporte {^{{^{{^{{^{{^{{4}}.}}.}}. }}4}}4}_{{\soporte {^{{^{{^{{^{{^{{4}}.}}.}}.}}4}}4}_{{^{ {^{{^{{4}}4}}4}}4}}}}.

Generalización

Algunos números son tan grandes que incluso escribir con las flechas de Knuth se vuelve demasiado engorroso; en este caso, es preferible el uso del operador n - arrow (y también para una descripción con un número variable de flechas), o equivalentemente, a los hiperoperadores . Pero algunos números son tan grandes que incluso esa notación no es suficiente. Por ejemplo, el número de Graham . Se puede usar una cadena de Conway para escribirlo : una cadena de tres elementos es equivalente a otra notación, pero una cadena de cuatro o más elementos es una forma de notación más poderosa. $\ flecha arriba ^ {n}$

{\begin{matrix}a\uparrow ^{n}b&=&{\mbox{hiper}}(a,n+2,b)&=&a\to b\to n\\{\mbox{ (Knut)))&&&&{\mbox{(Conway)))\end{matriz}}

Es común usar la notación de flechas de Knuth para números pequeños y flechas en cadena o hiperoperadores para números grandes.

Definición

La notación de flecha hacia arriba se define formalmente como

a\uparrow ^{n}b=\left\{{\begin{matrix}a^{b},&{\mbox{if }}n=1;\\1,&{\mbox{if }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\mbox{de lo contrario}}\end{matriz}}\right .

para todos los enteros donde . $a, b, n$ $b\geq 0,n\geq 1$

Todos los operadores de flecha (incluida la exponenciación ordinaria ) son asociativos por la derecha , es decir, se evalúan de derecha a izquierda si la expresión contiene dos o más operadores similares. Por ejemplo, $a\flecha arriba b$

a\flecha arriba b\flecha arriba c=a\flecha arriba (b\flecha arriba c)

, pero no ;

(a\flecha arriba b)\flecha arriba c

3\flecha arriba \flecha arriba 3=3^{{3^{3}}}

igual pero no

3^{{(3^{3})}}=3^{{27}}=7625597484987

\left(3^{3}\right)^{3}=27^{3}=19683.

Hay una buena razón para esta elección de dirección de cálculo de derecha a izquierda. Si usáramos el método de cálculo de izquierda a derecha, entonces sería igual a , y entonces no sería realmente un nuevo operador. $a \ flecha arriba \ flecha arriba b$ $a\flecha arriba (a\flecha arriba (b-1))$ $\flecha arriba \flecha arriba$

La asociatividad correcta también es natural por la siguiente razón. Podemos reescribir las expresiones de flecha repetidas que aparecen cuando se expanden como , donde todos se convierten en los operandos izquierdos de los operadores de flecha. Esto es importante ya que los operadores de flecha no son conmutativos . $a\uparrow ^{n}\cdots \uparrow ^{n}a,$ $a\flecha arriba ^{{n+1}}b$ $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$

Escribiendo como exponente funcional b de la función, obtenemos . $(a\flecha arriba ^{m})^{b}$ $f(x)=a\flecha arriba ^{m}x,$ $a\flecha arriba ^{n}b=(a\flecha arriba ^{{n-1}})^{b}1$

La definición se puede continuar un paso más, comenzando con para n = 0, ya que la exponenciación es una multiplicación repetida, comenzando desde 1. Extrapolar un paso más, escribiendo la multiplicación como suma repetida, no es del todo correcto, ya que la multiplicación es una suma repetida, comenzando en 0 en lugar de 1. "Extrapolar" un paso nuevamente, escribiendo el n incremental como una suma repetida de 1, requiere comenzar en el número a . Esta diferencia también se enfatiza en la definición del hiperoperador , donde los valores iniciales para la suma y la multiplicación se dan por separado. $a\flecha arriba ^{n}b=ab$

Tabla de valores

El cálculo 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 el número 2. Para determinar el número en la tabla, tome el número más cercano a la izquierda, luego busque el número requerido en la parte superior de la fila anterior, en la posición dada por el valor recién recibido. $2\flecha arriba ^{m}n$ $2^{n}$

Valores = hiper (2, m + 2, n ) = 2 → n → m

2\flecha arriba ^{m}n

m \ n	una	2	3	cuatro	5	6	Fórmula
una	2	cuatro	ocho	dieciséis	32	64	$2^{n}$
2	2	cuatro	dieciséis	65536	$2^{65536}\aproximadamente 2{,}0\times 10^{19,729}$	$2^{2^{65536}}\aproximadamente 10^{6{,}0\times 10^{19,728}}$	$2\flecha arriba \flecha arriba n$
3	2	cuatro	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matriz}}$			$2\flecha arriba \flecha arriba \flecha arriba n$
cuatro	2	cuatro	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matriz}}$				$2\flecha arriba \flecha arriba \flecha arriba \flecha arriba n$

La tabla es la misma que en el artículo de la función de Ackerman , excepto por el cambio en los valores de y , y además de 3 a todos los valores. $metro$ $norte$

Cálculo $3\flecha arriba ^{m}n$

Colocamos los números en la fila superior y llenamos la columna de la izquierda con el número 3. Para determinar el número en la tabla, tome el número más cercano a la izquierda, luego busque el número requerido en la parte superior de la fila anterior, en la posición dada por el valor recién recibido. $3^n$

Valores = hiper (3, m + 2, n ) = 3 → n → m

3\flecha arriba ^{m}n

m \ n	una	2	3	cuatro	5	Fórmula
una	3	9	27	81	243	$3^n$
2	3	27	7.625.597.484.987	$3^{{7,625,597,484,987}}$		$3\flecha arriba \flecha arriba n$
3	3	7.625.597.484.987	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3))))))} \\7,625,597,484,987 \end{matriz}}$			$3\flecha arriba \flecha arriba \flecha arriba n$
cuatro	3	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3))))))} \\7,625,597,484,987 \end{matriz}}$				$3\flecha arriba \flecha arriba \flecha arriba \flecha arriba n$

Cálculo $10\flecha arriba ^{m}n$

Colocamos los números en la fila superior y llenamos la columna de la izquierda con el número 10. Para determinar el número en la tabla, tome el número más cercano a la izquierda, luego busque el número requerido en la parte superior de la fila anterior, en la posición dada por el valor recién recibido. $10^{n}$

Valores = hiper (10, m + 2, n ) = 10 → n → m

10\flecha arriba ^{m}n

m \ n	una	2	3	cuatro	5	Fórmula
una	diez	100	1000	10,000	100,000	$10^{n}$
2	diez	10,000,000,000	$10^{{10,000,000,000}}$	$10^{{10^{{10,000,000,000}}}}$	$10^{{10^{{10^{{10,000,000,000}}}}}}$	$10\flecha arriba \flecha arriba n$
3	diez	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 \end{matriz}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 ^{10}\end{matriz}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 ^{10^{10}}\end{matriz}}$		$10\flecha arriba \flecha arriba \flecha arriba n$
cuatro	diez	${\begin{matriz}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10\end{matriz))$	${\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10^{10}\end{matrix))$			$10\flecha arriba \flecha arriba \flecha arriba \flecha arriba n$

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

Notas

↑ Knuth, Donald E. Matemáticas y Ciencias de la Computación: Hacer frente a la finitud // Ciencia: revista. - 1976. - vol. 194 . - P. 1235-1242 . -doi : 10.1126 / ciencia.194.4271.1235 .

Enlaces

Weisstein, Eric W. Knuth Up-Arrow Notation (inglés) en el sitio web de Wolfram MathWorld .

Grandes números
Números	gogol Número de Shannon googolplex número de sesgos número de Moser número de graham ÁRBOL(3) Número de Rayo
Funciones	Función de Ackermann Función Veblen Funciones psi de Buchholz tetración pentación hiperoperador Jerarquía de rápido crecimiento Jerarquía de crecimiento lento Jerarquía resistente
Notaciones	Notación de Steinhaus-Moser Notación de flecha Knuth Notación de flecha de Conway Notación masiva de Bowers