Knuths pilnotation

Knuths pilnotation (symbol ↑) är en matematisk metod som gör det möjligt att beskriva mycket stora heltal. Metoden introducerades av Donald Knuth 1976 och är starkt relaterad till Ackermanntalen. Idén bygger på upprepade exponenter på samma sätt som exponenter är upprepade multiplikationer, och multiplikationer är upprepad addition. Knuth nöjde sig dock inte med att bara skapa en operator för nästa nivå, utan skapade även ett generellt skrivsätt för att täcka alla efterföljande nivåer.

Introduktion

Multiplikation med naturliga tal kan definieras som upprepad addition:

${\begin{matrix}ab&=&\underbrace {a+a+\dots +a} \\&&b{\mbox{ kopior av }}a\end{matrix}}.$

Till exempel,

${\begin{matrix}3\times 2&=&\underbrace {3+3} &=&6\\&&2{\mbox{ kopior av }}3\end{matrix}}.$

Exponenter för ett naturligt tal $b$ kan definieras som upprepad multiplikation:

${\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b{\mbox{ kopior av }}a\end{matrix}}.$

Till exempel,

${\begin{matrix}3\uparrow 2=3^{2}=&\underbrace {3\times 3} &=&9\\&2{\mbox{ kopior av }}3\end{matrix}}.$

Detta inspirerade Knuth att definiera en "dubbelpiloperator" för upprepade exponenter, eller tetraering:

${\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a\uparrow a\uparrow \dots \uparrow a} \\&&b{\mbox{ kopior av }}a&&b{\mbox{ kopior av }}a\end{matrix}}$

Till exempel,

${\begin{matrix}3\uparrow \uparrow 2&={\ ^{2}3}=&\underbrace {3^{3}} &=&\underbrace {3\uparrow 3} &=&27\\&&2{\mbox{ kopior av }}3&&2{\mbox{ kopior av }}3\end{matrix}}.$

Notationen utförs från höger till vänster (en så kallad höger-associativ operator):

Enligt denna definition,

$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}}$ (att skriva ut detta tal på vanligt sätt skulle kräva ungefär 1,37 terabyte lagringsutrymme, dvs ${\mbox{7 625 597 484 987}}\times {\frac {\log 3}{\log 2}}$ bitar)

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

etc.

Redan detta ger mycket stora tal, men Knuth utökade notationen. Han definierade en trippelpil-operator för upprepade användningar av "dubbelpil-operatorn" (även känd som pentaering):

${\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow a\uparrow \uparrow \dots \uparrow \uparrow a} \\&b{\mbox{ kopior av }}a\end{matrix}}$

följt av en fyrfaldig piloperator:

${\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow a} \\&b{\mbox{ kopior av }}a\end{matrix}}$

och så vidare. Den generella regeln är att en $n$-piloperator expanderas till en serie av ($n-1$)-piloperatorer. Symboliskt uttryckt,

${\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{ kopior av }}a\end{matrix}}$

Exempel:

$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{ kopior av }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&{\mbox{7 625 597 484 987 kopior av 3}}\end{matrix}}$

Användningsområden för Knuths piloperator rör sig främst kring rent matematiska tillämpningar. Inom matematiken är operatorn ett effektivt sätt att beskriva snabbt växande funktioner som exempelvis Ackermannfunktionen. Piloperatorn används också för att beskriva Grahams tal.