Notación flecha de Knuth

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda

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.[1]​ Está estrechamente relacionada a 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[editar]

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:

Por ejemplo,

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

Por ejemplo,

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):

Por ejemplo,

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,

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 operador flecha se expande hacia una asociativa por derecha de la serie de ()operadores-flecha. Simbólicamente,

Ejemplos:


La notación se utiliza comúnmente para denotar con n flechas. De hecho, es a [n+2] b con hiperoperación. Por ejemplo, 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 [79] 77 en lugar de 77 [77] 77.

Notación[editar]

En expresiones como a , la notación de la potenciación es usualmente es por lo general escribir el exponente como superíndice de la base . 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 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 no se presta bien a la generalización, lo que explica por qué Knuth eligió desarrollar la notación flecha en su lugar.

es una notación alternativa más corta para n flechas. Así .

Escribir la notación flecha en términos de potencias[editar]

Intentar escribir usando la familiar notación de superíndice da una torre de potencias.

Por ejemplo:

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.

Continuando con esta notación, 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.

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.

Por otra parte, 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:

Referencias[editar]

  1. Knuth, Donald E. (1976). «Mathematics and Computer Science: Coping with Finiteness». Science 194 (4271): 1235-1242. PMID 17797067. doi:10.1126/science.194.4271.1235.