Knuthin nuolinotaatio

Luonnollisten lukujen kertolasku voidaan esittää peräkkäisinä yhteenlaskuina:

${\displaystyle {\begin{matrix}ab&=&\underbrace {a+a+\dots +a} \\&&a{\mbox{ lisätään itseensä }}b{\mbox{ kertaa }}\end{matrix}}.}$

Esimerkiksi,

${\displaystyle {\begin{matrix}3\times 2&=&\underbrace {3+3} &=&6\\&&3{\mbox{ lisätään itseensä }}2{\mbox{ kertaa }}\end{matrix}}.}$

Eksponentti ${\displaystyle b}$ voidaan esittää kertolaskuna:

${\displaystyle {\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&a{\mbox{ kerrotaan itsellään }}b{\mbox{ kertaa }}\end{matrix}}.}$

Esimerkiksi,

${\displaystyle {\begin{matrix}3\uparrow 2=3^{2}=&\underbrace {3\times 3} &=&9\\&3{\mbox{ kerrotaan itsellään }}2{\mbox{ kertaa }}\end{matrix}}.}$

Knuth esitti “kaksoisnuolet” osoittamaan iteroitua potenssiinkorotusta (tetraatiota):

${\displaystyle {\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow a\uparrow \dots \uparrow a} \\&&b{\mbox{ kpl }}a{\mbox{:ta }}&&b{\mbox{ kpl }}a{\mbox{:ta }}\end{matrix}}}$

Esimerkiksi,

${\displaystyle {\begin{matrix}3\uparrow \uparrow 2&={\ ^{2}3}=&\underbrace {3^{3}} &=&\underbrace {3\uparrow 3} &=&27\\&&2{\mbox{ kpl }}3{\mbox{:a }}&&2{\mbox{ kpl }}3{\mbox{:a }}\end{matrix}}.}$

Merkintätapaa luetaan oikealta vasemmalle:

Tämän mukaan,

${\displaystyle 3\uparrow \uparrow 2=3^{3}=27}$

${\displaystyle 3\uparrow \uparrow 3=3^{3^{3}}=3^{27}={\mbox{7 625 597 484 987}}}$

${\displaystyle 3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{\mbox{7 625 597 484 987}}}$

${\displaystyle 3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{\mbox{7 625 597 484 987}}}}$

jne.

Jo tällä päästään suhteellisen suuriin lukuihin, mutta Knuth jatkoi merkintätapaa pidemmälle. Hän määritteli “kolmoisnuoli” -operaattorin “kaksoisnuolten” iteroimiseksi edelleen (pentaatio):

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow a\uparrow \uparrow \dots \uparrow \uparrow a} \\&b{\mbox{ kpl }}a{\mbox{:ta }}\end{matrix}}}$

jota seuraa nelinkertainen nuolitus:

${\displaystyle {\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow a} \\&b{\mbox{ kpl }}a{\mbox{:ta }}\end{matrix}}}$

ja niin edelleen. Pääsääntönä on, että ${\displaystyle n}$-nuolioperaattori laajenee oikealtaluettavaksi (${\displaystyle n-1}$)-nuolioperaattoriksi. Symboleilla,

${\displaystyle {\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{\mbox{ kpl }}a{\mbox{:ta }}\end{matrix}}}$

Esimerkki:

${\displaystyle 3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}={\mbox{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{ kpl }}3{\mbox{:a}}\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&{\mbox{7 625 597 484 987 kpl }}3{\mbox{:a}}\end{matrix}}}$

Merkintätapaa ${\displaystyle a\uparrow ^{n}b}$ käytetään kuvaamaan ${\displaystyle a\uparrow \uparrow \dots \uparrow b}$ jossa on n nuolta.

Merkintätavan avulla voi tehokkaasti esittää nopeasti suurenevia funktioita, kuten Ackermannin funktiota tai Grahamin lukua.