Notație cu săgeată Knuth

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 5 septembrie 2021; verificările necesită 5 modificări .

În matematică , notația săgeată a lui Knuth este o metodă de scriere a numerelor mari. Ideea sa se bazează pe faptul că înmulțirea este adunare multiplă , exponențiația este înmulțire multiplă. A fost propus de Donald Knuth în 1976 [1] . Strâns legat de funcția Ackermann și de succesiunea de hiperoperatori .

Tetrație , scrisă folosind notația săgeată a lui Knuth:

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

Pentație în notația lui Knuth:

{\begin{matrix}a\uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b\ sfârşit{matrice}}

În notația indicată, există b operanzi, fiecare fiind egal cu a , respectiv, operațiile sunt repetate de ori. $b-1$

Introducere

Operațiile aritmetice obișnuite - adunarea, înmulțirea și exponențiarea - pot fi extinse în mod natural într-o secvență de hiperoperatori , după cum urmează:

Înmulțirea numerelor naturale poate fi definită printr-o operație de adunare repetitivă („adăugați b copii ale numărului a ”):

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

De exemplu,

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

Ridicarea lui a la puterea lui b poate fi definită ca o operație de înmulțire repetată ("înmulțiți b copii ale lui a "), iar în notația lui Knuth această notație arată ca o singură săgeată îndreptată în sus:

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

De exemplu,

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

O astfel de săgeată în sus a fost folosită ca o pictogramă de grad în limbajul de programare Algol .

Continuând în continuare secvența operațiilor dincolo de exponențiere, Donald Knuth a introdus conceptul de operator „săgeată dublă” pentru scrierea tetrației (exponentiație multiplă).

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

De exemplu,

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

Aici și mai jos, evaluarea expresiei merge întotdeauna de la dreapta la stânga, de asemenea operatorii de săgeți ai lui Knuth (precum și operația de exponențiere) au prin definiție asociativitate la dreapta (ordonare de la dreapta la stânga). Conform acestei definitii,

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}\aprox 1{,}3\times 10^{3\,638\,334\,640\,024}

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

si asa mai departe.

Acest lucru duce deja la numere destul de mari, dar notația nu se termină aici. Operatorul „săgeată triplă” este folosit pentru a scrie exponențiarea repetată a operatorului „săgeată dublă” (cunoscut și ca „ pentație ”):

{\begin{matrix}a\uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\dots \uparrow \uparrow a))} \\&b\ sfârşit{matrice}}

apoi operatorul „săgeată cvadruplă”:

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

și așa mai departe. Ca regulă generală, operatorul săgeată al n -lea , conform asociativității la dreapta , continuă spre dreapta într-o serie secvențială de n -1 operatori săgeată. În mod simbolic, aceasta poate fi scrisă după cum urmează:

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

De exemplu:

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 \ în sus 3} \\&7625597484987\end{matrice}}

Forma de notație este de obicei folosită pentru scrierea cu săgeți n . $a\uparrow ^{n}b$ $a\uparrow \uparrow \dots \uparrow b$

Sistem de notație

În expresii precum , este obișnuit să scrieți exponentul ca superscript al bazei pentru a indica exponentiația . Dar multe alte medii - cum ar fi limbaje de programare și e-mail - nu acceptă această configurație bidimensională. Prin urmare, utilizatorii ar trebui să utilizeze notația liniară pentru astfel de medii; săgeata în sus sugerează ridicarea la puterea . Dacă nu există nicio săgeată în sus printre caracterele disponibile, atunci se folosește în schimb semnul de inserare corectiv „^” . $a^{b}$ $b$ $A$ $a\în sus b$ $a^{b}$ $a\în sus b$

Denumirea „↑”

O încercare de a scrie o expresie folosind notația familiară cu exponenți generează un turn de puteri. De exemplu: $a\uparrow \uparrow b$

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

Dacă b este variabilă (sau foarte mare), turnul de grade poate fi scris folosind puncte și cu o notație care indică înălțimea turnului

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

Folosind această formă de notație, expresia poate fi scrisă ca un set ( stivă ) de astfel de turnuri de putere, fiecare dintre acestea indicând gradul de suprafață. $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}}}}}}.

Și din nou, dacă b este variabilă (sau foarte mare), un set de astfel de turnuri de putere poate fi scris folosind puncte și etichetat pentru a indica înălțimile lor

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

Mai mult decât atât, expresia poate fi scrisă folosind mai multe coloane de turnuri de putere similare, unde fiecare coloană indică numărul de turnuri de putere din setul din stânga $a\uparrow \uparrow \uparrow \uparrow b$

a\uparrow \uparrow \uparrow \uparrow 4=a\susura \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}}}}}}\dreapta\}a.

Mai general:

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

Acest lucru poate fi scris la infinit pentru a fi reprezentat ca o iterație de exponențiere pentru orice a , n și b (deși este clar că și acest lucru devine destul de greoi). $a\uparrow ^{n}b$

Utilizarea tetrației

Notația de tetrare face posibilă simplificarea unor astfel de scheme, continuând să se utilizeze o reprezentare geometrică (le putem numi turnuri de tetrare ). $^{{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 }}}}}}\dreapta\}b.

În cele din urmă, ca exemplu, al patrulea număr Ackermann poate fi scris astfel: $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}}}}.

Generalizare

Unele numere sunt atât de mari încât chiar și scrierea cu săgețile lui Knuth devine prea greoaie; în acest caz, utilizarea operatorului n -arrow este de preferat (și, de asemenea, pentru o descriere cu un număr variabil de săgeți), sau echivalent, hiperoperatorilor . Dar unele numere sunt atât de mari încât nici măcar o astfel de notație nu este suficientă. De exemplu, numărul Graham . Un lanț Conway poate fi folosit pentru a-l scrie : un lanț de trei elemente este echivalent cu o altă notație, dar un lanț de patru sau mai multe elemente este o formă mai puternică de notație. $\uparrow ^{n}$

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

Este obișnuit să se folosească notația săgeată a lui Knuth pentru numere mici și săgeți în lanț sau hiperoperatori pentru numere mari.

Definiție

Notația săgeată în sus este definită formal ca

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

pentru toate numerele întregi unde . $a,b,n$ $b\geq 0,n\geq 1$

Toți operatorii săgeți (inclusiv exponentiația obișnuită, ) sunt asociativi la dreapta , adică sunt evaluați de la dreapta la stânga dacă expresia conține doi sau mai mulți operatori similari. De exemplu, $a\în sus b$

a\susura b\susura c=a\susura (b\susura c)

, dar nu ;

(a\susura b)\susura c

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

egale dar nu

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

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

Există un motiv întemeiat pentru această alegere a direcției de calcul de la dreapta la stânga. Dacă ar fi să folosim metoda de calcul de la stânga la dreapta, atunci ar fi egal cu , și atunci nu ar fi cu adevărat un operator nou. $a\uparrow \uparrow b$ $a\susuri (a\susuri (b-1))$ $\uparrow \uparrow$

Asociativitatea dreaptă este, de asemenea, firească din următorul motiv. Putem rescrie expresiile de săgeți repetate care apar atunci când sunt extinse ca , unde toți a devin operanzii din stânga ai operatorilor săgeți. Acest lucru este important deoarece operatorii săgeți nu sunt comutativi . $a\uparrow ^{n}\cdots \uparrow ^{n}a,$ $a\suparrow ^{{n+1}}b$ $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$

Scriind ca exponent funcțional b al funcției, obținem . $(a\sustă ^{m})^{b}$ $f(x)=a\uparrow ^{m}x,$ $a\susura ^{n}b=(a\susura ^{{n-1}})^{b}1$

Definiția poate fi continuată cu încă un pas, începând cu pentru n = 0, deoarece exponențiarea este o înmulțire repetată, începând de la 1. Extrapolarea încă un pas, scrierea înmulțirii ca adunare repetată, nu este în întregime corectă, deoarece înmulțirea este adunare repetată, începând de la 0 în loc de 1. „Extrapolarea” din nou cu un pas, scrierea incrementalului n ca o adăugare repetată a lui 1, necesită începerea de la numărul a . Această diferență este subliniată și în definiția hiperoperatorului , unde valorile inițiale pentru adunare și înmulțire sunt date separat. $a\uparrow ^{n}b=ab$

Tabel de valori

Calculul poate fi reformulat în termenii unui tabel infinit. Așezăm numerele în rândul de sus și completăm coloana din stânga cu numărul 2. Pentru a determina numărul din tabel, luăm numărul cel mai aproape din stânga, apoi găsim numărul necesar în partea de sus în rândul anterior, în pozitia data de valoarea tocmai primita. $2\uparrow ^{m}n$ $2^{n}$

Valori = hiper (2, m + 2, n ) = 2 → n → m

2\uparrow ^{m}n

m \ n	unu	2	3	patru	5	6	Formulă
unu	2	patru	opt	16	32	64	$2^{n}$
2	2	patru	16	65536	$2^{65536}\aprox 2{,}0\times 10^{19.729}$	$2^{2^{65536}}\aprox 10^{6{,}0\times 10^{19.728}}$	$2\uparrow \uparrow n$
3	2	patru	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2)))))}\\65536 \end{matrice}}$			$2\uparrow \uparrow \uparrow n$
patru	2	patru	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2)))))}\\65536 \end{matrice}}$				$2\uparrow \uparrow \uparrow \uparrow n$

Tabelul este același ca în articolul cu funcția Ackerman , cu excepția schimbării valorilor lui și și în plus față de 3 la toate valorile. $m$ $n$

Calcul $3\uparrow ^{m}n$

Așezăm numerele în rândul de sus și completăm coloana din stânga cu numărul 3. Pentru a determina numărul din tabel, luăm numărul cel mai aproape din stânga, apoi găsim numărul necesar în partea de sus în rândul anterior, în pozitia data de valoarea tocmai primita. $3^n$

Valori = hiper (3, m + 2, n ) = 3 → n → m

3\uparrow ^{m}n

m \ n	unu	2	3	patru	5	Formulă
unu	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{matrice}}$			$3\uparrow \uparrow \uparrow n$
patru	3	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3)))))}} \\7.625.597.484.987 \end{matrice}}$				$3\uparrow \uparrow \uparrow \uparrow n$

Calcul $10\uparrow ^{m}n$

Așezăm numerele în rândul de sus și completăm coloana din stânga cu numărul 10. Pentru a determina numărul din tabel, luăm numărul cel mai aproape din stânga, apoi găsim numărul necesar în partea de sus în rândul anterior, în pozitia data de valoarea tocmai primita. $10^{n}$

Valori = hiper (10, m + 2, n ) = 10 → n → m

10\uparrow ^{m}n

m \ n	unu	2	3	patru	5	Formulă
unu	zece	100	1000	10.000	100.000	$10^{n}$
2	zece	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	zece	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10))))))}} \\ 10 \end{matrice}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10))))))}} \\ 10 ^{10}\end{matrice}}$	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10))))))}} \\ 10 ^{10^{10}}\end{matrice}}$		$10\uparrow \uparrow \uparrow n$
patru	zece	${\begin{matrice}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10\end{matrice))$	${\begin{matrice}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10^{10}\end{matrice))$			$10\uparrow \uparrow \uparrow \uparrow n$

Pentru 2 ≤ n ≤ 9, ordinea numerică este ordinea lexicografică cu m ca număr cel mai semnificativ, deci ordinea numerelor acestor 8 coloane este doar linie cu linie. Același lucru este valabil și pentru numerele din 97 de coloane cu 3 ≤ n ≤ 99 și începem cu m = 1 chiar și pentru 3 ≤ n ≤ 9.999.999.999. $10\uparrow ^{m}n$

Note

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

Link -uri

Weisstein, Eric W. Knuth Notație cu săgeată în sus (engleză) pe site-ul web Wolfram MathWorld .

Cifre mari
Numerele	googol Numărul Shannon Googlelplex Număr înclinat numărul Moser Numărul Graham TREE(3) Numărul Rayo
Funcții	Funcția Ackermann Funcția Veblen Funcțiile Psi ale lui Buchholz tetrare Pentație Hiperoperator Ierarhie în creștere rapidă Ierarhie în creștere lent Ierarhie Hardy
Notații	Notația Steinhaus-Moser Notație cu săgeată Knuth Notație săgeată Conway Notație masivă Bowers