Knuthin nuolinotaatio

Knuthin nuolinotaatio (tai Knuthin ylänuolinotaatio) on matematiikassa käytetty menetelmä erittäin suurten potenssiinkorotusten esittämiseksi. Metodin esitteli Donald Knuth vuonna 1976 ja se liittyy voimakkaasti Ackermannin funktioon. Notaation idea liittyy siihen tosiasiaan, että kertolasku voidaan käsitellä iteroituina yhteenlaskuina ja potenssiinkorotus iteroituina kertolaskuina. Jatkamalla samalla menetelmällä päästään iteroituun potenssiinkorotukseen (tetraatioon).

Esitys

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

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

Esimerkiksi,

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

Eksponentti $b$ voidaan esittää kertolaskuna:

${\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,

${\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):

${\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,

${\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}}.$

Notaatiota luetaan oikealta vasemmalle:

Tämän mukaan,

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

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

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

$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 notaatiota pidemmälle. Hän määritteli “kolmoisnuoli” -operaattorin “kaksoisnuolten” iteroimiseksi edelleen (pentaatio):

${\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:

${\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ä $n$-nuolioperaattori laajenee oikealtaluettavaksi ($n-1$)-nuolioperaattoriksi. Symboleilla,

${\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:

$3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}={\mbox{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{\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}}$

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

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