Knuthova šipková notace

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 5. září 2021; kontroly vyžadují 5 úprav .

V matematice je Knuthova šipková notace metodou pro psaní velkých čísel. Jeho myšlenka je založena na skutečnosti, že násobení je vícenásobné sčítání , umocňování je vícenásobné násobení. To bylo navrženo Donaldem Knuthem v roce 1976 [1] . Úzce souvisí s Ackermannovou funkcí a sekvencí hyperoperátorů .

Tetration , zapsaný pomocí Knuthovy šipky:

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

Pentace v Knuthově notaci:

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\tečky \uparrow \uparrow a))} \\&b\ konec{matice}}

V uvedeném zápisu existuje b operandů, z nichž každý je roven a , respektive operace se opakují . $b-1$

Úvod

Obvyklé aritmetické operace – sčítání, násobení a umocňování – lze přirozeně rozšířit do sekvence hyperoperátorů takto:

Násobení přirozených čísel lze definovat pomocí operace opakovaného sčítání („přidej b kopie čísla a “):

{\begin{matrix}a\times b&=&\underbrace {a+a+\tečky +a} \\&&b\end{matrix}}

Například,

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

Zvýšení a na mocninu b lze definovat jako opakovanou operaci násobení („násobení b kopií a “) a v Knuthově zápisu vypadá tento zápis jako jedna šipka směřující nahoru:

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

Například,

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

Taková jediná šipka nahoru byla použita jako ikona stupně v programovacím jazyce Algol .

Donald Knuth pokračoval v dalším sledu operací za umocňováním a zavedl koncept operátoru „dvojité šipky“ pro zápis tetrace (vícenásobné umocňování).

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

Například,

{\begin{matrix}4\uparrow \uparrow 3&={\ ^{3}4}=&\underbrace {4^{4^{4))} &=&\underbrace {4\uparrow (4 \uparrow 4)} &=&4^{256}\cca 1{,}3\krát 10^{154}\\&&3&&3\end{matrix}}

Zde a níže probíhá vyhodnocení výrazu vždy zprava doleva, také Knuthovy šipkové operátory (stejně jako operace umocňování) mají ze své podstaty pravou asociativitu (řazení zprava doleva). Podle této definice,

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}\cca 1{,}3\krát 10^{3\,638\,334\,640\,024}

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

a tak dále.

To již vede k poměrně velkým číslům, ale tím zápis nekončí. Operátor „trojitá šipka“ se používá k zápisu opakovaného umocňování operátoru „dvojité šipky“ (také známého jako „ pentace “):

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\tečky \uparrow \uparrow a))} \\&b\ konec{matice}}

pak operátor „čtyři šipka“:

{\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\pod závorkou {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\tečky \uparrow \uparrow \uparrow a))} \\&b\end{matrix}}

atd. Obecným pravidlem je, že n-tý šipkový operátor podle pravé asociativity pokračuje doprava do sekvenční řady n - 1 šipkových operátorů. Symbolicky to lze napsat následovně:

{\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\tečky \!\!\uparrow } \ b=a\ \underbrace {\uparrow \!\!\tečky \!\!\uparrow } \ a\ \underbrace {\uparrow _{}\!\!\tečky \!\!\uparrow } \ a\ \tečky \ a\ \underbrace {\uparrow _{}\!\ !\tečky \!\!\uparrow } \ a\\\quad \ \ \,n\qquad \ \ \ \underbrace {\quad n_{}\!-\!\!1\quad \ \,n\! -\!\!1\qquad \quad \ \ \ \,n\!-\!\!1\ \ \ \ } \\\qquad \qquad \quad \ \ b\end{matrix}}

Například:

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)=&\pod závorkou {3_ {}\uparrow 3\uparrow \tečky \uparrow 3} \\&3\uparrow 3\uparrow 3\end{matrix}}{\begin{matrix}=&\pod závorkou {3_{}\uparrow 3\uparrow \tečky \ nahoru 3} \\&7625597484987\end{matrix}}

Forma zápisu se obvykle používá pro zápis s n šipkami. $a\uparrow ^{n}b$ $a\uparrow \uparrow \tečky \uparrow b$

Systém zápisu

Ve výrazech jako , je běžné psát exponent jako horní index základu k označení umocňování . Ale mnoho dalších prostředí - jako jsou programovací jazyky a e-mail - tuto dvourozměrnou konfiguraci nepodporuje. Proto by uživatelé měli pro taková prostředí používat lineární zápis; šipka nahoru naznačuje zvýšení na sílu . Pokud mezi dostupnými znaky není žádná šipka nahoru , použije se místo toho opravná značka pro vložení „^“ . $a^{b}$ $b$ $A$ $a\šipka b$ $a^{b}$ $a\šipka b$

Označení "↑"

Pokus o zápis výrazu pomocí známé notace s exponenty generuje věž mocnin. Například: $a\uparrow \uparrow b$

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

Pokud je b proměnné (nebo velmi velké), lze věž stupňů zapsat pomocí teček a se zápisem udávajícím výšku věže.

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

Pomocí této formy zápisu lze výraz zapsat jako množinu ( stohu ) takových energetických věží, z nichž každá udává stupeň překrytí $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}}}}}}.

A znovu, pokud je b proměnlivé (nebo velmi velké), lze sadu takových energetických věží zapsat pomocí bodů a označit jimi, aby označovaly jejich výšky.

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

Kromě toho lze výraz zapsat pomocí několika sloupců podobných energetických věží, kde každý sloupec označuje počet energetických věží v sadě vlevo $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.

Obecněji:

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

To může být zapsáno donekonečna, aby bylo reprezentováno jako iterace umocňování pro libovolné a , n a b (ačkoli je jasné, že se to také stává značně těžkopádným). $a\uparrow ^{n}b$

Použití tetrace

Tetrační notace umožňuje zjednodušit taková schémata a přitom nadále používat geometrickou reprezentaci (můžeme je nazvat tetovací věže ). $^{{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.

Nakonec, jako příklad, čtvrté Ackermannovo číslo lze zapsat jako: $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}}}}.

Generalizace

Některá čísla jsou tak velká, že i psaní Knuthovými šipkami je příliš těžkopádné; v tomto případě je výhodnější použití operátoru n - šipka (a také pro popis s proměnným počtem šipek), nebo ekvivalentně, než hyperoperátory . Některá čísla jsou ale tak obrovská, že ani takový zápis nestačí. Například Grahamovo číslo . K jeho zápisu lze použít Conwayův řetězec : řetězec tří prvků je ekvivalentní jinému zápisu, ale řetězec čtyř nebo více prvků je silnější forma zápisu. $\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}}

Pro malá čísla je běžné používat Knuthovu šipkovou notaci a pro velká čísla řetězové šipky nebo hyperoperátory.

Definice

Zápis šipky nahoru je formálně definován jako

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{jinak}}\end{matrix}}\right .

pro všechna celá čísla kde . $a,b,n$ $b\geq 0,n\geq 1$

Všechny šipkové operátory (včetně běžného umocňování, ) jsou asociativní vpravo , to znamená, že se vyhodnocují zprava doleva, pokud výraz obsahuje dva nebo více podobných operátorů. Například, $a\šipka b$

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

, ale ne ;

(a\šipka b)\šipka c

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

rovné , ale ne

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

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

Pro tuto volbu směru výpočtu zprava doleva existuje dobrý důvod. Pokud bychom použili metodu výpočtu zleva doprava, pak by se to rovnalo a ve skutečnosti by to nebyl nový operátor. $a\uparrow \uparrow b$ $a\uparrow (a\uparrow (b-1))$ $\uparrow \uparrow$

Pravá asociativita je také přirozená z následujícího důvodu. Můžeme přepsat opakované šipkové výrazy , které se objeví po rozbalení jako , kde všechna a se stanou levými operandy šipek. To je důležité, protože šipkové operátory nejsou komutativní . $a\uparrow ^{n}\cdots \uparrow ^{n}a,$ $a\uparrow ^{{n+1}}b$ $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$

Zápisem jako funkcionální exponent b funkce dostaneme . $(a\uparrow ^{m})^{b}$ $f(x)=a\šipka nahoru ^{m}x,$ $a\uparrow ^{n}b=(a\uparrow ^{{n-1}})^{b}1$

Definice může pokračovat ještě jedním krokem, počínaje pro n = 0, protože umocňování je opakované násobení, počínaje 1. Extrapolovat ještě jeden krok, psát násobení jako opakované sčítání, není zcela správné, protože násobení je opakované sčítání, počínaje od 0 místo 1. "Extrapolace" znovu o jeden krok, zápis přírůstku n jako opakované sčítání 1, vyžaduje začít od čísla a . Tento rozdíl je také zdůrazněn v definici hyperoperátoru , kde jsou počáteční hodnoty pro sčítání a násobení uvedeny samostatně. $a\uparrow ^{n}b=ab$

Tabulka hodnot

Výpočet lze přeformulovat do podoby nekonečné tabulky. Čísla umístíme do horního řádku a sloupec vlevo vyplníme číslem 2. Číslo v tabulce určíme tak, že vezmeme číslo nejblíže vlevo, pak najdeme požadované číslo nahoře v předchozím řádku, v pozice daná právě přijatou hodnotou. $2\uparrow ^{m}n$ $2^{n}$

Hodnoty = hyper (2, m + 2, n ) = 2 → n → m

2\uparrow ^{m}n

m \ n	jeden	2	3	čtyři	5	6	Vzorec
jeden	2	čtyři	osm	16	32	64	$2^{n}$
2	2	čtyři	16	65536	$2^{65536}\cca 2{,}0\times 10^{19,729}$	$2^{2^{65536}}\cca 10^{6{,}0\krát 10^{19,728}}$	$2\uparrow \uparrow n$
3	2	čtyři	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matrix}}$			$2\uparrow \uparrow \uparrow n$
čtyři	2	čtyři	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matrix}}$				$2\uparrow \uparrow \uparrow \uparrow n$

Tabulka je stejná jako v článku Ackerman function , s výjimkou posunu hodnot a a navíc 3 ke všem hodnotám. $m$ $n$

Výpočet $3\uparrow ^{m}n$

Čísla umístíme do horní řady a sloupec nalevo vyplníme číslem 3. Číslo v tabulce určíme tak, že vezmeme číslo nejblíže vlevo, požadované číslo pak najdeme nahoře v předchozím řádku, v pozice daná právě přijatou hodnotou. $3^n$

Hodnoty = hyper (3, m + 2, n ) = 3 → n → m

3\uparrow ^{m}n

m \ n	jeden	2	3	čtyři	5	Vzorec
jeden	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$
čtyři	3	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3))))))} \\7,625,597,484,987 \end{matrix}}$				$3\uparrow \uparrow \uparrow \uparrow n$

Výpočet $10\uparrow ^{m}n$

Čísla umístíme do horního řádku a sloupec nalevo vyplníme číslem 10. Číslo v tabulce určíme tak, že vezmeme číslo nejblíže vlevo, pak najdeme požadované číslo nahoře v předchozím řádku, v pozice daná právě přijatou hodnotou. $10^{n}$

Hodnoty = hyper (10, m + 2, n ) = 10 → n → m

10\uparrow ^{m}n

m \ n	jeden	2	3	čtyři	5	Vzorec
jeden	deset	100	1000	10 000	100 000	$10^{n}$
2	deset	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	deset	${\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$
čtyři	deset	${\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$

Pro 2 ≤ n ≤ 9 je číselné pořadí lexikografické pořadí s m jako nejvýznamnějším číslem, takže pořadí čísel těchto 8 sloupců je pouze řádek po řádku. Totéž platí pro čísla v 97 sloupcích s 3 ≤ n ≤ 99 a začínáme s m = 1 i pro 3 ≤ n ≤ 9 999 999 999. $10\uparrow ^{m}n$

Poznámky

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

Odkazy

Weisstein, Eric W. Knuth Up-Arrow Notation (anglicky) na webových stránkách Wolfram MathWorld .

Velká čísla
Čísla	googol Shannonovo číslo Googolplex Skewes číslo Moserovo číslo Grahamovo číslo STROM(3) Rayo číslo
Funkce	Ackermannova funkce Funkce Veblen Psi funkce Buchholze tetování Pentace Hyperoperátor Rychle rostoucí hierarchie Pomalu rostoucí hierarchie Hardyho hierarchie
Notace	Steinhaus-Moserova notace Knuthova šipková notace Notace Conwayovy šipky Masivní Bowers Notace