Knuth pil notation

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 5. september 2021; checks kræver 5 redigeringer .

I matematik er Knuths pilnotation en metode til at skrive store tal. Dens idé er baseret på det faktum, at multiplikation er multiplikation , eksponentiering er multiplikation. Det blev foreslået af Donald Knuth i 1976 [1] . Nært forbundet med Ackermann-funktionen og sekvensen af hyperoperatorer .

Tetration , skrevet 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{matrix}}

Pentation i Knuths notation:

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

I den angivne notation er der b operander, som hver er lig med henholdsvis a , operationerne gentages gange. $b-1$

Introduktion

De sædvanlige aritmetiske operationer – addition, multiplikation og eksponentiering – kan naturligvis udvides til en sekvens af hyperoperatorer som følger:

Multiplikation af naturlige tal kan defineres gennem en gentagen additionsoperation ("tilføj b kopier af tallet a "):

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

For eksempel,

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

At hæve a til potensen af b kan defineres som en gentagen multiplikationsoperation ("multiplicer b kopier af a "), og i Knuths notation ser denne notation ud som en enkelt pil, der peger opad:

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

For eksempel,

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

Sådan en enkelt pil op blev brugt som et gradikon i programmeringssproget Algol .

For at fortsætte sekvensen af operationer ud over eksponentiering, introducerede Donald Knuth konceptet med "dobbeltpil" -operatoren til at skrive tetration (multipel eksponentiering).

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

For eksempel,

{\begin{matrix}4\uparrow \uparrow 3&={\ ^{3}4}=&\underbrace {4^{4^{4))} &=&\underbrace {4\uparrow (4 \uparrow 4)} &=&4^{256}\ca. 1{,}3\gange 10^{154}\\&&3&&3\end{matrix}}

Her og nedenfor går evalueringen af udtrykket altid fra højre mod venstre, også Knuths piloperatorer (samt eksponentieringsoperationen) har per definition højre associativitet (højre-til-venstre rækkefølge). Ifølge denne 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\ gange 10^{3\,638\,334\,640\,024}

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

og så videre.

Dette fører allerede til ret store tal, men notationen slutter ikke der. "Tredobbelt pil"-operatoren bruges til at skrive gentagen eksponentiering af "dobbeltpil"-operatoren (også kendt som " pentation "):

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

derefter "firedobbelt pil"-operatoren:

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

osv. Som en generel regel fortsætter den n'te piloperator, ifølge højre associativitet , til højre ind i en sekventiel serie af n -1 pileoperatorer. Symbolsk kan dette skrives som følger,

{\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{matrix}}

For eksempel:

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\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 \ uparrow 3} \\&7625597484987\end{matrix}}

Notationsformen bruges normalt til at skrive med n pile. $a\uparrow ^{n}b$ $a\uparrow \uparrow \dots \uparrow b$

Notationssystem

I udtryk som , er det almindeligt at skrive eksponenten som den hævede skrift af grundtallet for at betegne eksponentiering . Men mange andre miljøer - såsom programmeringssprog og e-mail - understøtter ikke denne todimensionelle konfiguration. Derfor bør brugere bruge den lineære notation til sådanne miljøer; pil op foreslår at hæve til styrken af . Hvis der ikke er nogen opadgående pil blandt de tilgængelige tegn, bruges det korrigerende indsættelsesmærke "^" i stedet for . $a^{b}$ $b$ $-en$ $a\uparrow b$ $a^{b}$ $a\uparrow b$

Betegnelse "↑"

Et forsøg på at skrive et udtryk ved hjælp af den velkendte notation med eksponenter genererer et tårn af potenser. For eksempel: $a\uparrow \uparrow b$

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

Hvis b er variabel (eller meget stor), kan tårnet af grader skrives ved hjælp af prikker og med en notation, der angiver tårnets højde

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

Ved at bruge denne form for notation kan udtrykket skrives som et sæt ( stak ) af sådanne krafttårne, som hver angiver graden af den overliggende $a\uparrow \uparrow \uparrow b$

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

Og igen, hvis b er variabel (eller meget stor), kan et sæt af sådanne krafttårne skrives ved hjælp af punkter og mærkes for at angive deres højder

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

Ydermere kan udtrykket skrives ved hjælp af flere kolonner af lignende eltårne, hvor hver kolonne angiver antallet af eltårne i sættet til venstre $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=\venstre.\venstre.\venstre.\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.

Mere generelt:

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}}.

Dette kan skrives i det uendelige for at blive repræsenteret som en iteration af eksponentiering for enhver a , n og b (selvom det er klart, at dette også bliver ret besværligt). $a\uparrow ^{n}b$

Brug af tetration

Tetrationsnotationen gør det muligt at forenkle sådanne skemaer, mens man fortsætter med at bruge en geometrisk repræsentation (vi kan kalde dem tetrationstårne ) . $^{{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.

Endelig, som et eksempel, kan det fjerde Ackermann-nummer skrives 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

Nogle tal er så store, at selv at skrive med Knuths pile bliver for besværligt; i dette tilfælde er brugen af n -pil- operatoren at foretrække (og også for en beskrivelse med et variabelt antal pile) eller tilsvarende frem for hyperoperatorerne . Men nogle tal er så store, at selv en sådan notation ikke er nok. For eksempel Graham-nummeret . En Conway-kæde kan bruges til at skrive det : en kæde af tre elementer svarer til en anden notation, men en kæde af fire eller flere elementer er en mere kraftfuld form for 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 er almindeligt at bruge Knuths pilnotation for små tal, og kædepile eller hyperoperatorer for store tal.

Definition

Pil op-notationen er formelt defineret 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{ellers}}\end{matrix}}\right .

for alle heltal hvor . $a,b,n$ $b\geq 0,n\geq 1$

Alle pileoperatorer (inklusive almindelig eksponentiering, ) er højreassociative , det vil sige, at de evalueres fra højre mod venstre, hvis udtrykket indeholder to eller flere lignende operatorer. For eksempel, $a\uparrow b$

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

, men ikke ;

(a\uparrow b)\uparrow c

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

lige men ikke

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

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

Der er en god grund til dette valg af højre-til-venstre-beregningsretning. Hvis vi skulle bruge venstre-til-højre-beregningsmetoden, så ville den være lig med , og ville så ikke rigtig være en ny operator. $a\uparrow \uparrow b$ $a\uparrow (a\uparrow (b-1))$ $\uparrow \uparrow$

Den rigtige associativitet er også naturlig af følgende grund. Vi kan omskrive de gentagne pileudtryk , der vises, når de udvides som , hvor alle a bliver venstre operander af piloperatorerne. Dette er vigtigt, da pileoperatorer ikke er kommutative . $a\uparrow ^{n}\cdots \uparrow ^{n}a,$ $a\uparrow ^{{n+1}}b$ $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$

Hvis vi skriver som en funktionel eksponent b for 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ættes et trin mere, startende med for n = 0, da eksponentiering er gentagen multiplikation, startende fra 1. Ekstrapolering af et trin mere, skrivning af multiplikation som gentagen addition, er ikke helt korrekt, da multiplikation er gentagen addition, startende kl. 0 i stedet for 1. "Ekstrapolering" et trin igen, skrivning af det inkrementelle n som en gentagen tilføjelse af 1, kræver at man starter med tallet a . Denne forskel understreges også i definitionen af hyperoperatoren , hvor startværdierne for addition og multiplikation er givet separat. $a\uparrow ^{n}b=ab$

Tabel over værdier

Beregningen kan omformuleres i form af en uendelig tabel. Vi placerer tallene i den øverste række og udfylder kolonnen til venstre med tallet 2. For at bestemme tallet i tabellen skal du tage det tal, der er tættest på venstre, og derefter finde det ønskede tal øverst i den forrige række, i positionen givet af den netop modtagne værdi. $2\uparrow ^{m}n$ $2^{n}$

Værdier = hyper (2, m + 2, n ) = 2 → n → m

2\uparrow ^{m}n

m \ n	en	2	3	fire	5	6	Formel
en	2	fire	otte	16	32	64	$2^{n}$
2	2	fire	16	65536	$2^{65536}\ca. 2{,}0\ gange 10^{19.729}$	$2^{2^{65536}}\ca. 10^{6{,}0\ gange 10^{19.728}}$	$2\uparrow \uparrow n$
3	2	fire	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matrix}}$			$2\uparrow \uparrow \uparrow n$
fire	2	fire	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matrix}}$				$2\uparrow \uparrow \uparrow \uparrow n$

Tabellen er den samme som i Ackerman-funktionsartiklen , bortset fra ændringen i værdierne af og , og i tillæg af 3 til alle værdier. $m$ $n$

Beregning $3\uparrow ^{m}n$

Vi placerer tallene i den øverste række og udfylder kolonnen til venstre med tallet 3. For at bestemme tallet i tabellen skal du tage det tal, der er tættest på venstre, og derefter finde det ønskede tal øverst i den forrige række, i positionen givet af den netop modtagne værdi. $3^n$

Værdier = hyper (3, m + 2, n ) = 3 → n → m

3\uparrow ^{m}n

m \ n	en	2	3	fire	5	Formel
en	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{matrix}}$			$3\uparrow \uparrow \uparrow n$
fire	3	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3))))))} \\7,625,597,484,987 \end{matrix}}$				$3\uparrow \uparrow \uparrow \uparrow n$

Beregning $10\uparrow ^{m}n$

Vi placerer tallene i den øverste række og udfylder kolonnen til venstre med tallet 10. For at bestemme tallet i tabellen skal du tage det tal, der er tættest på venstre, og derefter finde det ønskede tal øverst i den forrige række, i positionen givet af den netop modtagne værdi. $10^{n}$

Værdier = hyper (10, m + 2, n ) = 10 → n → m

10\uparrow ^{m}n

m \ n	en	2	3	fire	5	Formel
en	ti	100	1000	10.000	100.000	$10^{n}$
2	ti	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	ti	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 \end{matrix}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 ^{10}\end{matrix}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 ^{10^{10}}\end{matrix}}$		$10\uparrow \uparrow \uparrow n$
fire	ti	${\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$

For 2 ≤ n ≤ 9 er den numeriske rækkefølge den leksikografiske rækkefølge med m som det mest signifikante tal, så rækkefølgen af tallene i disse 8 kolonner er blot linje for linje. Det samme gælder for tal i 97 kolonner med 3 ≤ n ≤ 99, og vi starter med m = 1 selv for 3 ≤ n ≤ 9.999.999.999. $10\uparrow ^{m}n$

Noter

↑ Knuth, Donald E. Mathematics and Computer Science: Coping with Finiteness // Science : journal. - 1976. - Bd. 194 . - S. 1235-1242 . - doi : 10.1126/science.194.4271.1235 .

Links

Weisstein, Eric W. Knuth Up-Arrow Notation (engelsk) på Wolfram MathWorld -webstedet .

Store tal
Tal	google Shannon nummer Googolplex Skæv nummer Moser nummer Graham nummer TRÆ(3) Rayo nummer
Funktioner	Ackermann funktion Veblen funktion Psi-funktioner af Buchholz tetration Pentation Hyperoperator Hurtigt voksende hierarki Langsomt voksende hierarki Hardy hierarki
Notationer	Steinhaus-Moser notation Knuth pil notation Conway pil notation Massive Bowers-notation