Knuths pilnotation

Från Rilpedia

Version från den 6 oktober 2008 kl. 22.04 av Arnef (Diskussion)

(skillnad) ← Äldre version | Nuvarande version (skillnad) | Nyare version → (skillnad)

Hoppa till: navigering, sök

Texten från svenska Wikipedia

Knuts pilnotation ä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. Knut 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} a b & = & \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 exepmel,

$\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\uparrow2=3^3=27$

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

$3\uparrow\uparrow4=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\uparrow5=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\uparrow2 = 3\uparrow\uparrow3 = 3^{3^3} = 3^{27}=\mbox{7 625 597 484 987}$

$\begin{matrix} 3\uparrow\uparrow\uparrow3 = 3\uparrow\uparrow3\uparrow\uparrow3 = 3\uparrow\uparrow(3\uparrow3\uparrow3) = & \underbrace{3_{}\uparrow 3\uparrow\dots\uparrow 3} \\ & 3\uparrow3\uparrow3\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}$

Knuths pilnotation

Från Rilpedia

Introduktion

Visningar

Personliga verktyg

Sök

Navigering

Bibeln

Övrigt

Verktygslåda

På andra språk