Notació flecha de Knuth

En matemàtiques, la notació flecha de Knuth és un método de notació per a sancers molt grans, introduït per Donald Knuth en 1976. Està estretament relacionada en la funció de Ackermann i especialment a la successió de hiperoperaciones. L'idea està basada en el fet de que la multiplicació pot ser vista com una adició iterada i la potenciació com una multiplicació iterada. Continuant d'esta manera, s'aplega a la potenciació iterada (tetración) i al restant de la successió de hiperoperaciones, la qual és generalment denotada usant la notació flecha de Knuth.

Introducció

Les operacions aritmètiques normals d'adició, multiplicació, i potenciació és naturalment estesa a una successió de hiperoperaciones com seguix.

La multiplicació per un número natural està definida com una adició iterada:

$\begin{array}{ccc}a\times b& =& \underbrace{a+a+\dots +a}\\ & & b\text{ veces }a\end{array}$

Per eixemple,

$\begin{array}{ccccc}4\times 3& =& \underbrace{4+4+4}& =& 12\\ & & 3\text{ veces }4\end{array}$

La potenciació per a un exponent natural $b$ es definix com una multiplicació iterada, que Knuth denota per una sola flecha dalt:

$\begin{array}{cc}a\uparrow b=a^b=& \underbrace{a\times a\times \dots \times a}\\ & b\text{ veces }a\end{array}$

Per eixemple,

$\begin{array}{cccc}4\uparrow 3=4^3=& \underbrace{4\times 4\times 4}& =& 64\\ & 3\text{ veces }4\end{array}$

Per a ampliar la seqüència d'operacions més allà de la potenciació, Knuth va definir un operador "doble flecha" per a denotar la potenciació iterada (tetración):

$\begin{array}{ccccc}a\uparrow \uparrow b& ={}^{b}a=& \underbrace{a^{a^{{}^{.{}^{.{}^{.{}^a}}}}}}& =& \underbrace{a\uparrow (a\uparrow (\dots \uparrow a))}\\ & & b\text{ veces }a& & b\text{ veces }a\end{array}$

Per eixemple,

$\begin{array}{cccccccccc}4\uparrow \uparrow 3& ={}^{3}4=& \underbrace{4^{4^4}}& =& \underbrace{4\uparrow (4\uparrow 4)}& =& 4^{256}& \approx & 1.34078079\times 10^{154}& \\ & & 3\text{ veces }4& & 3\text{ veces }4\end{array}$

Ací i a continuació l'evaluació es portarà a terme de dreta a esquerra, aixina els operadors flecha de Knuth (com la potenciació) es definixen com a associatius per dreta.

D'acort a esta definició,

$3\uparrow \uparrow 2=3^3=27$

$3\uparrow \uparrow 3=3^{3^3}=3^{27}=7625597484987\approx 7.6\times 10^{12}$

$3\uparrow \uparrow 4=3^{3^{3^3}}=3^{3^{27}}=3^{7625597484987}\approx 1.2580740420492718971\times 10^{3638334640024}$

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

etc.

Açò conduïx ya a uns números prou grans, pero Knuth ampliat de la notació. Va passar a definir un operador "triple flecha" per a tetración iterada (pentación):

seguit per un operador "cuádruple flecha" per a definir la pentación iterada (hexación):

i aixina successivament. La regla general és que un $n$operador flecha s'expandix cap a una associativa per dreta de la série de ($n-1$)operadors-flecha. Simbòlicament,

Eixemples:

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

La notació $a{\uparrow }^{n}b$ s'utilisa comunament per a denotar $a\uparrow \uparrow \dots \uparrow b$ en n fleches. De fet, $a{\uparrow }^{n}b$ és a [n+2] b en hiperoperación. Per eixemple, $39\uparrow \uparrow 14$ també pot ser escrit com 39 [4] 14, la "[4]" significa tetración, pero no igual a 39 [2] 14 = 39 × 14 = 546, de la mateixa manera, $77{\uparrow }^{77}77=$ 77 [79] 77 en lloc de 77 [77] 77.

Notació

En expressions com a $a^b$, la notació de la potenciació és usualment és per lo general escriure l'exponent $b$ com superíndex de la base $a$. Pero en molts entorns — com en els llenguages de programació i i-mails de text pla — no són compatibles en composició tipogràfica de superíndex. La gent ha adoptat la notació llineal $a\uparrow b$ per a tals entorns; la flecha cap a dalt sugerix «elevat a» l'exponent indicat. Si el joc de caràcters no conté una flecha cap a dalt, el caret (^) s'utilisa en el seu lloc.

La notació de superíndex $a^b$ no es presta be a la generalisació, lo que explica per qué Knuth va elegir desenrollar la notació flecha $a\uparrow b$ en el seu lloc.

$a{\uparrow }^{n}b$ és una notació alternativa més curta per a n fleches. Aixina $a{\uparrow }^{4}b=a\uparrow \uparrow \uparrow \uparrow b$.

Escriure la notació flecha en térmens de potències

Intentar escriure $a\uparrow \uparrow b$ usant la familiar notació de superíndex dona una torre de potències.

Per eixemple: $a\uparrow \uparrow 4=a\uparrow (a\uparrow (a\uparrow a))=a^{a^{a^a}}$

Si b és una variable (o és massa gran), la torre de potències podria ser escrita utilisant punts i una nota que indique l'altura de la torre.

$a\uparrow \uparrow b=\underset{b}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}$

Continuant en esta notació, $a\uparrow \uparrow \uparrow b$ pot ser escrit en una pila de tals torres de potències, cada u descrivint el tamany de la pila que està per damunt d'ella.

$a\uparrow \uparrow \uparrow 4=a\uparrow \uparrow (a\uparrow \uparrow (a\uparrow \uparrow a))=\underset{\underset{\underset{a}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}$

De nou, si b és una variable o és massa gran, la pila podria ser escrita utilisant punts i una nota indicant la seua altura.

$a\uparrow \uparrow \uparrow b=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}b$

Per una atra part, $a\uparrow \uparrow \uparrow \uparrow b$ podria escriure's usant vàries columnes de dites piles de torres de potències, cada columna descriu el número de torres de potències en la pila a la seua esquerra:

$a\uparrow \uparrow \uparrow \uparrow 4=a\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow a))=\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}\underset{\underset{\underset{a}{\underbrace{⋮}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}}{\underbrace{a^{a^{{.}^{{.}^{.a}}}}}}\}a$