Knuth pilnotation

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 5 september 2021; kontroller kräver 5 redigeringar .

Inom matematiken är Knuths pilnotation en metod för att skriva stora tal. Dess idé är baserad på det faktum att multiplikation är multipel addition , exponentiering är multipel multiplikation. Det föreslogs av Donald Knuth 1976 [ 1] . Nära relaterad till Ackermann-funktionen och sekvensen av hyperoperatorer .

Tetration , skriven med Knuths pilnotation:

{\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{. \,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\&&b&&b\end{matris}}

Pentation i Knuths notation:

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b\ slut{matris}}

I den angivna notationen finns b operander, som var och en är lika med a respektive, operationerna upprepas gånger. $b-1$

Introduktion

De vanliga aritmetiska operationerna – addition, multiplikation och exponentiering – kan naturligtvis utökas till en sekvens av hyperoperatorer enligt följande:

Multiplikation av naturliga tal kan definieras genom en upprepad additionsoperation ("lägg till b kopior av talet a "):

{\begin{matrix}a\times b&=&\underbrace {a+a+\dots +a} \\&&b\end{matrix}}

Till exempel,

{\begin{matrix}4\times 3&=&\underbrace {4+4+4} &=&12\\&&3\end{matrix}}

Att höja a till b kan definieras som en upprepad multiplikationsoperation ("multiplicera b kopior av a "), och i Knuths notation ser denna notation ut som en enkel pil som pekar uppåt:

{\begin{matrix}a\uparrow b=a^{b}=&\underbrace {a\times a\times \dots \times a} \\&b\end{matrix}}

Till exempel,

{\begin{matrix}4\uparrow 3=4^{3}=&\underbrace {4\times 4\times 4} &=&64\\&3\end{matrix))

En sådan enkel uppåtpil användes som en gradikon i programmeringsspråket Algol .

Donald Knuth fortsatte med operationssekvensen bortom exponentieringen och introducerade konceptet med operatorn "dubbelpil" för att skriva tetration (multipel exponentiering).

{\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{. \,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\dots \uparrow a))} \\&&b&&b\end{matris}}

Till exempel,

{\begin{matrix}4\uparrow \uparrow 3&={\ ^{3}4}=&\underbrace {4^{4^{4))} &=&\underbrace {4\uparrow (4) \uparrow 4)} &=&4^{256}\approx 1{,}3\times 10^{154}\\&&3&&3\end{matris}}

Här och nedan går utvärderingen av uttrycket alltid från höger till vänster, även Knuths piloperatorer (liksom exponentieringsoperationen) har per definition högerassociativitet (höger-till-vänster-ordning). Enligt denna definition,

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

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

3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7\,625\,597\,484\,987}\ca 1{,}3\ gånger 10^{3\,638\,334\,640\,024}

3\uparrow \uparrow 5=3^{3^{3^{3^{3))))=3^{3^{7\,625\,597\,484\,987}}

och så vidare.

Detta leder redan till ganska stora siffror, men notationen slutar inte där. Operatorn "trippelpil" används för att skriva upprepad exponentiering av operatorn "dubbelpil" (även känd som " pentation "):

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b\ slut{matris}}

sedan operatorn "fyrdubbel pil":

{\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\dots \uparrow \uparrow \uparrow a))} \\&b\end{matris}}

och så vidare. Som en allmän regel fortsätter den n :te piloperatorn, enligt högerassociativitet , till höger in i en sekventiell serie av n -1 piloperatorer. Symboliskt kan detta skrivas på följande sätt,

{\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\end{matris}}

Till exempel:

3\uparrow \uparrow \uparrow 2=3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=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\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \ uppåtpil 3} \\&7625597484987\end{matris}}

Notationsformen används vanligtvis för att skriva med n pilar. $a\uparrow ^{n}b$ $a\uparrow \uparrow \dots \uparrow b$

Notationssystem

I uttryck som , är det vanligt att skriva exponenten som den övre skriften av basen för att beteckna exponentiering . Men många andra miljöer - som programmeringsspråk och e-post - stöder inte denna tvådimensionella konfiguration. Därför bör användare använda den linjära notationen för sådana miljöer; uppåtpilen föreslår att du höjer till kraften . Om det inte finns någon uppåtpil bland de tillgängliga tecknen, används det korrigerande infogningsmärket "^" istället . $a^{b}$ $b$ $a$ $a\uparrow b$ $a^{b}$ $a\uparrow b$

Beteckning "↑"

Ett försök att skriva ett uttryck med den välbekanta notationen med exponenter genererar ett torn av potenser. Till exempel: $a\uparrow \uparrow b$

a\uparrow \uparrow 4=a\uparrow a\uparrow a\uparrow a=a^{{a^{{a^{a}}}}}.

Om b är variabel (eller mycket stor) kan gradertornet skrivas med hjälp av punkter och med en notation som anger tornets höjd

a\uparrow \uparrow b=\underbrace {a^{{a^{{.^{{.^{{.{a}}}}}}}}}_{{b}}.

Med denna form av notation kan uttrycket skrivas som en uppsättning ( stack ) av sådana krafttorn, som vart och ett indikerar graden av det överliggande $a\uparrow \uparrow \uparrow b$

a\uparrow \uparrow \uparrow 4=a\uparrow \uparrow a\uparrow a\uparrow \uparrow a=\underbrace {a^{{a^{{.^{{.^{{.{a}} }})))}}}}_{{\underbrace {a^{{a^{{.^{{.^{{.{a}}}}}}}}}_{{\underbrace { a ^{{a^{{.^{{.^{{.{a}}}}}}}}}}_{{a}}}}}}.

Och igen, om b är variabel (eller mycket stor), kan en uppsättning sådana krafttorn skrivas med hjälp av punkter och märkas för att indikera deras höjder

a\uparrow \uparrow \uparrow b=\left.\underbrace {a^{{a^{{.^{{.^{{.{a))))))))))_{{\underbrace { a^{{a^{{.^{{.^{{.{a))))))))))_({\underbrace {\vdots }_{{a))))))\right \}b.

Dessutom kan uttrycket skrivas med flera kolumner med liknande krafttorn, där varje kolumn anger antalet krafttorn i uppsättningen till vänster $a\uparrow \uparrow \uparrow \uparrow b$

a\uparrow \uparrow \uparrow \uparrow 4=a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow a=\left.\left.\left.\underbrace {a^{{ a^{{.^{{.^{{.{a}}}}}}}}}}_{{\underbrace {a^{{a^{{.^{{.^{{.{a )))))))))))_{{\underbrace {\vdots }_{{a))))))\right\}\underbrace {a^{{a^{{.^{{. ^ {{.{a}}}}}}}}}}_{{\underbrace {a^{{a^{{.^{{.^{{.{a}}}}}}}}} } _{{\underbrace {\vdots }_{{a))))))\right\}\underbrace {a^{{a^{{.^{{.^{{.{a))))) } )))))_{{\underbrace {a^{{a^{{.^{{.^{{.{a)))))))))))_{{\underbrace {\vdots } _ {{a}}}}}}\right\}a.

Mer allmänt:

a\uparrow \uparrow \uparrow \uparrow b=\underbrace {\left.\left.\left.\underbrace {a^{{a^{{.^{{.^{{.{a))))} )))))_{{\underbrace {a^{{a^{{.^{{.^{{.{a)))))))))))_{{\underbrace {\vdots }_ {{a}}}}}}\right\}\underbrace {a^{{a^{{.^{{.^{{.{a}}}}}}}}}}_{{\underbrace {a^{{a^{{.^{{.^{{.{a))))))))))_({\underbrace {\vdots }_{{a)))))))) \ right\}\cdots \right\}a}_{{b}}.

Detta kan skrivas i all oändlighet för att representeras som en iteration av exponentiering för alla a , n och b (även om det är tydligt att detta också blir ganska krångligt). $a\uparrow ^{n}b$

Användning av tetration

Tetrationsbeteckningen gör det möjligt att förenkla sådana scheman, samtidigt som man fortsätter att använda en geometrisk representation (vi kan kalla dem tetrationstorn ). $^{{b}}a$

a\uparrow \uparrow b={}^{{b}}a,

a\uparrow \uparrow \uparrow b=\underbrace {^{{^{{^{{^{{^{{a}}.}}.}}.}}a}}a}_{{b}} ,

a\uparrow \uparrow \uparrow \uparrow b=\left.\underbrace {^{{^{{^{{^{{^{{{a}}.}}.}}.}}a}}a} _ {{\underbrace {^{{^{{^{{^{^{{{a}}.}}.}}.}}a}}a}_{{\underbrace {\vdots }_{ {a }}}}}}\right\}b.

Slutligen, som ett exempel, kan det fjärde Ackermann-numret skrivas som: $4\uparrow ^{4}4$

\underbrace {^{{^{{^{{^{{^{{4}}.}}.}}.}}4}}4}_({\underbrace {^{{^{{^{{ ^{{^{{4}}.}}.}}.}}4}}4}_{{\underbrace {^{{^{{^{{^{{^{{4}}.}} .}}.}}4}}4}_{{4}}}}}}=\underbrace {^{{^{{^{{^{^{{4}}.}}.}}. }}4}}4}_{{\underbrace {^{{^{{^{{^{{^{{4}}.}}.}}.}}4}}4}_{{^{ {^{{^{{4}}4}}4}}4}}}}.

Generalisering

Vissa siffror är så stora att även att skriva med Knuths pilar blir för krångligt; i detta fall är användningen av n -arrow- operatorn att föredra (och även för en beskrivning med ett variabelt antal pilar), eller motsvarande, framför hyperoperatorerna . Men vissa siffror är så enorma att ens en sådan notation inte räcker. Till exempel Graham-numret . En Conway-kedja kan användas för att skriva det : en kedja av tre element motsvarar en annan notation, men en kedja av fyra eller fler element är en mer kraftfull form av notation. $\uparrow ^{n}$

{\begin{matrix}a\uparrow ^{n}b&=&{\mbox{hyper}}(a,n+2,b)&=&a\to b\to n\\{\mbox{ (Knut)))&&&&{\mbox{(Conway)))\end{matrix}}

Det är vanligt att använda Knuths pilnotation för små tal, och kedjepilar eller hyperoperatorer för stora tal.

Definition

Uppåtpilen definieras formellt som

a\uparrow ^{n}b=\left\{{\begin{matrix}a^{b},&{\mbox{if }}n=1;\\1,&{\mbox{if }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\mbox{annars}}\end{matrix}}\right .

för alla heltal där . $a,b,n$ $b\geq 0,n\geq 1$

Alla piloperatorer (inklusive vanlig exponentiering, ) är högerassociativa , det vill säga de utvärderas från höger till vänster om uttrycket innehåller två eller flera liknande operatorer. Till exempel, $a\uparrow b$

a\uparrow b\uparrow c=a\uparrow (b\uparrow c)

, men inte ;

(a\uparrow b)\uparrow c

3\uparrow \uparrow 3=3^{{3^{3}}}

lika men inte

3^{{(3^{3})}}=3^{{27}}=7625597484987

\left(3^{3}\right)^{3}=27^{3}=19683.

Det finns en god anledning till detta val av höger-till-vänster beräkningsriktning. Om vi skulle använda beräkningsmetoden från vänster till höger, så skulle den vara lika med , och då skulle det egentligen inte vara en ny operator. $a\uparrow \uparrow b$ $a\uparrow (a\uparrow (b-1))$ $\uparrow \uparrow$

Rätt associativitet är också naturlig av följande anledning. Vi kan skriva om de upprepade piluttrycken som visas när de expanderas som , där alla a blir vänsteroperander för piloperatorerna. Detta är viktigt eftersom piloperatorer inte är kommutativa . $a\uparrow ^{n}\cdots \uparrow ^{n}a,$ $a\uparrow ^{{n+1}}b$ $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$

Om vi skriver som en funktionell exponent b för funktionen får vi . $(a\uparrow ^{m})^{b}$ $f(x)=a\uparrow ^{m}x,$ $a\uparrow ^{n}b=(a\uparrow ^{{n-1}})^{b}1$

Definitionen kan fortsätta ett steg till, med början för n = 0, eftersom exponentiering är upprepad multiplikation, med start från 1. Att extrapolera ytterligare ett steg, skriva multiplikation som upprepad addition, är inte helt korrekt, eftersom multiplikation är upprepad addition, med början kl. 0 istället för 1. Att "extrapolera" ett steg igen, skriva det inkrementella n som en upprepad tillägg av 1, kräver att man börjar med siffran a . Denna skillnad betonas också i definitionen av hyperoperatorn , där de initiala värdena för addition och multiplikation ges separat. $a\uparrow ^{n}b=ab$

Värdetabell

Beräkningen kan omformuleras i termer av en oändlig tabell. Vi placerar siffrorna i den översta raden och fyller kolumnen till vänster med siffran 2. För att bestämma numret i tabellen, ta numret närmast till vänster, hitta sedan det önskade numret överst i föregående rad, i positionen som ges av det nyss mottagna värdet. $2\uparrow ^{m}n$ $2^{n}$

Värden = hyper (2, m + 2, n ) = 2 → n → m

2\uparrow ^{m}n

m \ n	ett	2	3	fyra	5	6	Formel
ett	2	fyra	åtta	16	32	64	$2^{n}$
2	2	fyra	16	65536	$2^{65536}\approx 2{,}0\times 10^{19 729}$	$2^{2^{65536}}\approx 10^{6{,}0\times 10^{19 728}}$	$2\uparrow \uparrow n$
3	2	fyra	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matris}}$			$2\uparrow \uparrow \uparrow n$
fyra	2	fyra	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matris}}$				$2\uparrow \uparrow \uparrow \uparrow n$

Tabellen är densamma som i Ackerman-funktionsartikeln , förutom förskjutningen av värdena för och , och utöver 3 till alla värden. $m$ $n$

Beräkning $3\uparrow ^{m}n$

Vi placerar siffrorna i den översta raden och fyller kolumnen till vänster med siffran 3. För att bestämma numret i tabellen, ta numret närmast till vänster, hitta sedan det önskade numret överst i föregående rad, i positionen som ges av det nyss mottagna värdet. $3^n$

Värden = hyper (3, m + 2, n ) = 3 → n → m

3\uparrow ^{m}n

m \ n	ett	2	3	fyra	5	Formel
ett	3	9	27	81	243	$3^n$
2	3	27	7,625,597,484,987	$3^{{7,625,597,484,987}}$		$3\uparrow \uparrow n$
3	3	7,625,597,484,987	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3))))))} \\7,625,597,484,987 \end{matris}}$			$3\uparrow \uparrow \uparrow n$
fyra	3	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3))))))} \\7,625,597,484,987 \end{matris}}$				$3\uparrow \uparrow \uparrow \uparrow n$

Beräkning $10\uparrow ^{m}n$

Vi placerar siffrorna i den översta raden och fyller kolumnen till vänster med siffran 10. För att bestämma numret i tabellen, ta siffran närmast till vänster, hitta sedan det önskade numret överst i föregående rad, i positionen som ges av det nyss mottagna värdet. $10^{n}$

Värden = hyper (10, m + 2, n ) = 10 → n → m

10\uparrow ^{m}n

m \ n	ett	2	3	fyra	5	Formel
ett	tio	100	1000	10 000	100 000	$10^{n}$
2	tio	10 000 000 000	$10^{{10.000.000.000}}$	$10^{{10^{{10.000.000.000}}}}$	$10^{{10^{{10^{{10.000.000.000}}}}}}$	$10\uparrow \uparrow n$
3	tio	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 \end{matris}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 ^{10}\end{matris}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 ^{10^{10}}\end{matris}}$		$10\uparrow \uparrow \uparrow n$
fyra	tio	${\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10\end{matrix))$	${\begin{matrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10^{10}\end{matrix))$			$10\uparrow \uparrow \uparrow \uparrow n$

För 2 ≤ n ≤ 9 är den numeriska ordningen den lexikografiska ordningen med m som det mest signifikanta talet, så ordningen på numren i dessa 8 kolumner är bara rad för rad. Detsamma gäller för siffror i 97 kolumner med 3 ≤ n ≤ 99, och vi börjar med m = 1 även för 3 ≤ n ≤ 9 999 999 999. $10\uparrow ^{m}n$

Anteckningar

↑ Knuth, Donald E. Matematik och datavetenskap: Coping with Finiteness // Vetenskap: journal. - 1976. - Vol. 194 . - P. 1235-1242 . - doi : 10.1126/science.194.4271.1235 .

Länkar

Weisstein, Eric W. Knuth Up-Arrow Notation (engelska) på Wolfram MathWorlds webbplats .

Stora siffror
Tal	googol Shannon nummer Googolplex Skeves nummer Moser nummer Graham nummer TRÄD(3) Rayo nummer
Funktioner	Ackermann funktion Veblen funktion Psi-funktioner för Buchholz tetration Pentation Hyperoperator Snabbväxande hierarki Långsamt växande hierarki Härlig hierarki
Noteringar	Steinhaus-Moser notation Knuth pilnotation Conway pil notation Massiv Bowers Notation