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. Merkintätavan 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).

EsitysMuokkaa

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

 

Esimerkiksi,

 

Eksponentti   voidaan esittää kertolaskuna:

 

Esimerkiksi,

 

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

 

Esimerkiksi,

 

Merkintätapaa luetaan oikealta vasemmalle:

Tämän mukaan,

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

 

jota seuraa nelinkertainen nuolitus:

 

ja niin edelleen. Pääsääntönä on, että  -nuolioperaattori laajenee oikealtaluettavaksi ( )-nuolioperaattoriksi. Symboleilla,

 

Esimerkki:

 

 

Merkintätapaa   käytetään kuvaamaan   jossa on n nuolta.

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