Knuthin nuolen merkintä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 5.9.2021 tarkistetusta versiosta . tarkastukset vaativat 5 muokkausta .

Matematiikassa Knuthin nuolen merkintä on tapa kirjoittaa suuria lukuja. Sen ajatus perustuu siihen, että kertolasku on moninkertainen yhteenlasku , eksponentio on monikerto. Sitä ehdotti Donald Knuth vuonna 1976 [1] . Liittyy läheisesti Ackermann - funktioon ja hyperoperaattorien järjestykseen .

Tetraatio , kirjoitettu käyttäen Knuthin nuolta:

{\displaystyle {\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{. '

Pentaatio Knuthin notaatiossa:

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\pisteet \uparrow \uparrow a))} \\&b\ loppu{matriisi}}

Esitetyssä merkinnässä on b operandia, joista kukin on yhtä suuri kuin a , operaatiot toistetaan vastaavasti . $b-1$

Johdanto

Tavalliset aritmeettiset operaatiot - yhteen-, kertolasku ja eksponentio - voidaan luonnollisesti laajentaa hyperoperaattoreiden sarjaksi seuraavasti:

Luonnollisten lukujen kertolasku voidaan määrittää toistuvalla summausoperaatiolla ("lisää b kopiot luvusta a "):

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

Esimerkiksi,

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

A:n nostaminen b :n potenssiin voidaan määritellä toistuvaksi kertolaskuoperaatioksi ("kertoja b kopiot a : sta "), ja Knuthin merkinnöissä tämä merkintä näyttää yhdeltä ylöspäin osoittavalta nuolelta:

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

Esimerkiksi,

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

Tällaista yhtä ylöspäin osoittavaa nuolta käytettiin Algol - ohjelmointikielessä astekuvakkeena .

Jatkaen edelleen operaatioiden sarjaa eksponentioinnin jälkeen, Donald Knuth esitteli "kaksoisnuoli" -operaattorin käsitteen tetration (multiple eksponentio) kirjoittamiseen.

{\displaystyle {\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{. '

Esimerkiksi,

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

Tässä ja alla lausekkeen arviointi etenee aina oikealta vasemmalle, myös Knuthin nuolioperaattoreilla (sekä eksponentiooperaatiolla) on määritelmän mukaan oikea assosiaatio (oikealta vasemmalle järjestys). Tämän määritelmän mukaan

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

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

ja niin edelleen.

Tämä johtaa jo melko suuriin lukuihin, mutta merkintä ei lopu tähän. "Kolmoinen nuoli" -operaattoria käytetään "kaksoisnuoli"-operaattorin (tunnetaan myös nimellä " pentation ") toistuva eksponentio:

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\pisteet \uparrow \uparrow a))} \\&b\ loppu{matriisi}}

sitten "neljännin nuoli"-operaattori:

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

ja niin edelleen. Yleissääntönä n :s nuolioperaattori , oikean assosiatiivisuuden mukaan, jatkaa oikealle n -1 nuolioperaattorin peräkkäiseen sarjaan. Symbolisesti tämä voidaan kirjoittaa seuraavasti:

{\begin{matrix}a\ \underbrace {\uparrow _{}\uparrow \!\!\dots \!\!\uparrow } \ b=a\ \underbrace {\uparrow \!\!\dots ' !\dots \!\!\uparrow } \ a\\\quad \ \ \,n\qquad \ \ \ \underbrace {\quad n_{}\!-\!\!1\quad \ \,n\! -\!\!1\qquad \quad \ \ \ \,n\!-\!\!1\ \ \ } \\\qquad \qquad \quad \ \ b\end{matriisi}}

Esimerkiksi:

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)=&\uparrow {3_ {}\uparrow 3\uparrow \dots \uparrow 3} \\&3\uparrow 3\uparrow 3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \ arrow 3} \\&7625597484987\end{matrix}}

Merkintämuotoa käytetään yleensä n - nuolella kirjoittamiseen . $a\uparrow ^{n}b$ $a\uparrow \uparrow \dots \uparrow b$

Merkintäjärjestelmä

Lausekkeissa, kuten , on yleistä kirjoittaa eksponentti kantaluvun yläindeksiksi osoittamaan eksponentiota . Mutta monet muut ympäristöt - kuten ohjelmointikielet ja sähköposti - eivät tue tätä kaksiulotteista konfiguraatiota. Siksi käyttäjien tulee käyttää lineaarista merkintää tällaisissa ympäristöissä; ylöspäin osoittava nuoli ehdottaa nostamista tehoon . Jos käytettävissä olevien merkkien joukossa ei ole ylöspäin osoittavaa nuolta , sen sijaan käytetään korjaavaa lisäysmerkkiä ”^” . $a^{b}$ $b$ $a$ $a\uparrow b$ $a^{b}$ $a\uparrow b$

Nimitys "↑"

Yritys kirjoittaa lauseke käyttämällä tuttua merkintää eksponenteilla luo potenssien tornin. Esimerkiksi: $a\uparrow \uparrow b$

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

Jos b on muuttuva (tai erittäin suuri), astetorni voidaan kirjoittaa pisteillä ja tornin korkeutta osoittavalla merkinnällä

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

Tätä merkintätapaa käyttämällä lauseke voidaan kirjoittaa joukoksi ( pinoksi ) sellaisia voimatorneja, joista kukin ilmaisee peiton asteen. $a\uparrow \uparrow \uparrow b$

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

Ja jälleen, jos b on muuttuva (tai erittäin suuri), joukko tällaisia voimatorneja voidaan kirjoittaa käyttämällä pisteitä ja merkitä niiden korkeuden osoittamiseksi.

a\uparrow \uparrow \uparrow b=\left.\alijaviiva {a^{{a^{{.^{{.^{{.{a))))))))))_{{\alleviivamerkki { a^{{a^{{.^{.^{{.{a))))))))))_({\aliviiva {\vdots }_{{a))))))\oikea \}b.

Lisäksi lauseke voidaan kirjoittaa useilla samankaltaisten voimatornien sarakkeilla, joissa jokainen sarake osoittaa vasemmalla olevan sarjan voimatornien lukumäärän $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.\alabaari {a^{{ a^{{.^{{{.^{{.{a}}}}}}}}}}_{{\underbrace {a^{{a^{{.^{{.^{{.{a ))))))))))))_{{\aliviiva {\vdots }_{{a))))))\oikea\}\alleviivausmerkki {a^{{a^{{.^{{. ^ {{.{a}}}}}}}}}}_{{\alijaviiva {a^{{a^{{.^{{.^{{.{a}}}}}}}}}} } _{{\aliviiva {\vdots }_{{a))))))\oikea\}\aliviiva {a^{{a^{{.^{{.^{{.{a)))) } ))))))_{{\aliviiva {a^{{a^{{.^{{.^{{.{a))))))))))_{{\aliviiva {\vdots } _ {{a}}}}}}\right\}a.

Yleisemmin:

a\uparrow \uparrow \uparrow \uparrow b=\uparrow {\left.\left.\left.\underbarce {a^{{a^{{.^{{.^{{.{a))))} )))))))_{{\alijalisäke {a^{{a^{{.^{{.^{{.{a))))))))))_{{\aliviiva {\vdots }_ {{a}}}}}}\oikea\}\aliviiva {a^{{a^{{.^{{.^{{.{a}}}}}}}}}}_{{\aliviiva {a^{{a^{{.^{{.^{{.{a))))))))))_({\alaviiva {\vdots }_{{a))))))) \ right\}\cdots \right\}a}_{{b}}.

Tämä voidaan kirjoittaa loputtomiin, jotta se voidaan esittää minkä tahansa a :n , n: n ja b :n eksponentioimisen iteraationa (vaikka on selvää, että tämäkin tulee melko hankalaksi). $a\uparrow ^{n}b$

Tetration käyttö

Tetraation merkintä mahdollistaa tällaisten kaavioiden yksinkertaistamisen jatkaen samalla geometrisen esityksen käyttöä (voimme kutsua niitä tetratiotorneiksi ). $^{{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} _ {{\aliviiva {^{{^{{^{{^{{^{{{a}}.}}.}}.}}a}}a}_{{\alijaviiva {\vdots }_{ {a }}}}}}\oikea\}b.

Lopuksi esimerkkinä neljäs Ackermann-luku voidaan kirjoittaa seuraavasti: $4\uparrow ^{4}4$

\aliviiva {^{{^{{^{{^{{^{{4}}.}}.}}.}}.}}4}}4}_({\aliviiva {^{{^{{^{{ ^{{^{{4}}.}}.}}.}}4}}4}_{{\alaviiva {^{{^{{^{{^{{^{{4}}.}} .}}.}}4}}4}_{{{4}}}}}}=\alaviiva {^{{^{{^{{^{{^{{4}}.}}.}}. }}4}}4}_{{\aliviivamerkki {^{{^{{^{{^{{^{{4}}.}}.}}.}}4}}4}_{{^{ {^{{^{{4}}4}}4}}4}}}}.

Yleistys

Jotkut luvut ovat niin suuria, että jopa Knuthin nuolilla kirjoittamisesta tulee liian vaivalloista; tässä tapauksessa n - nuolioperaattorin käyttö on parempi (ja myös kuvauksessa, jossa on vaihteleva määrä nuolia) tai vastaavasti hyperoperaattoreille . Mutta jotkut luvut ovat niin suuria, että edes tällainen merkintä ei riitä. Esimerkiksi Grahamin numero . Sen kirjoittamiseen voidaan käyttää Conway-ketjua : kolmen elementin ketju vastaa toista merkintää, mutta neljän tai useamman elementin ketju on tehokkaampi merkintätapa. $\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}}

On yleistä käyttää Knuthin nuolimerkintää pienille luvuille ja ketjunuolia tai hyperoperaattoreita suurille numeroille.

Määritelmä

Ylösnuolimerkintä on muodollisesti määritelty

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

kaikille kokonaisluvuille missä . $a,b,n$ $b\geq 0, n\geq 1$

Kaikki nuolioperaattorit (mukaan lukien tavallinen eksponentio, ) ovat oikealle assosiatiivisia , eli ne lasketaan oikealta vasemmalle, jos lauseke sisältää kaksi tai useampia samankaltaisia operaattoreita. Esimerkiksi, $a\uparrow b$

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

, mutta ei ;

(a\uparrow b)\uparrow c

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

tasa -arvoinen mutta ei

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

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

Tälle oikealta vasemmalle suuntautuvalle laskentasuunnalle on hyvä syy. Jos käyttäisimme vasemmalta oikealle -laskentatapaa, se olisi yhtä suuri kuin , eikä se olisi oikeastaan uusi operaattori. $a\uparrow \uparrow b$ $a\uparrow (a\uparrow (b-1))$ $\uparrow \uparrow$

Oikea assosiaatio on luonnollista myös seuraavasta syystä. Voimme kirjoittaa uudelleen toistuvat nuolilausekkeet , jotka näkyvät laajennettaessa muodossa , jossa kaikista a tulee nuolioperaattoreiden vasemmista operandeista. Tämä on tärkeää, koska nuolioperaattorit eivät ole kommutatiivisia . $a\uparrow ^{n}\cdots \uparrow ^{n}a,$ $a\uparrow ^{{n+1}}b$ $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$

Kirjoittamalla funktion funktionaaliseksi eksponenttiksi b , saamme . $(a\uparrow ^{m})^{b}$ $f(x)=a\uparrow ^{m}x,$ $a\uparrow ^{n}b=(a\uparrow ^{{n-1}})^{b}1$

Määrittelyä voidaan jatkaa vielä yhdellä askeleella, alkaen arvolla n = 0, koska eksponentiointi on toistuvaa kertolaskua alkaen 1:stä. Vielä yhden askeleen ekstrapolointi, kertolasku toistuvana yhteenlaskuna, ei ole täysin oikein, koska kertolasku on toistuvaa yhteenlaskua alkaen pisteestä. 0 1:n sijasta. Yhden askeleen "ekstrapolointi" uudelleen, inkrementaalin n kirjoittaminen toistuvana 1:n lisäyksenä vaatii aloittamista numerosta a . Tämä ero korostuu myös hyperoperaattorin määritelmässä , jossa yhteen- ja kertolaskujen alkuarvot annetaan erikseen. $a\uparrow ^{n}b=ab$

Arvotaulukko

Laskelma voidaan muotoilla uudelleen äärettömäksi taulukoksi. Asetamme numerot ylimmälle riville ja täytämme vasemmanpuoleisen sarakkeen numerolla 2. Määrittääksesi taulukon luvun ottamalla lähimpänä vasemmalla oleva numero ja etsi sitten edellisen rivin ylhäältä haluamasi numero. juuri saadun arvon antama sijainti. $2\uparrow ^{m}n$ $2^{n}$

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

2\uparrow ^{m}n

m \ n	yksi	2	3	neljä	5	6	Kaava
yksi	2	neljä	kahdeksan	16	32	64	$2^{n}$
2	2	neljä	16	65536	$2^{65536}\noin 2{,}0\kertaa 10^{19 729}$	$2^{2^{65536}}\noin 10^{6{,}0\kertaa 10^{19 728}}$	$2\uparrow \uparrow n$
3	2	neljä	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matrix}}$			$2\uparrow \uparrow \uparrow n$
neljä	2	neljä	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{matrix}}$				$2\uparrow \uparrow \uparrow \uparrow n$

Taulukko on sama kuin Ackerman-funktion artikkelissa , lukuun ottamatta ja arvojen muutosta ja 3:n lisäksi kaikkiin arvoihin. $m$ $n$

Laskeminen $3\uparrow ^{m}n$

Asetamme numerot ylimmälle riville ja täytämme vasemmanpuoleisen sarakkeen numerolla 3. Määrittääksesi taulukon luvun ottamalla lähimpänä vasemmalla oleva numero ja etsi sitten edellisen rivin ylhäältä haluamasi numero. juuri saadun arvon antama sijainti. $3^n$

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

3\uparrow ^{m}n

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

Laskeminen $10\uparrow ^{m}n$

Asetamme luvut ylimmälle riville ja täytämme vasemmanpuoleisen sarakkeen numerolla 10. Määrittääksesi taulukon luvun ottamalla lähimpänä vasemmalla oleva numero ja etsi sitten edellisen rivin ylhäältä tarvittava numero. juuri saadun arvon antama sijainti. $10^{n}$

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

10\uparrow ^{m}n

m \ n	yksi	2	3	neljä	5	Kaava
yksi	kymmenen	100	1000	10 000	100 000	$10^{n}$
2	kymmenen	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	kymmenen	${\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$
neljä	kymmenen	${\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$

Kun 2 ≤ n ≤ 9, numeerinen järjestys on leksikografinen järjestys , jossa m on merkittävin luku, joten näiden 8 sarakkeen numerojärjestys on vain rivi riviltä. Sama koskee lukuja 97 sarakkeessa, joissa 3 ≤ n ≤ 99, ja aloitamme m = 1, vaikka 3 ≤ n ≤ 9 999 999 999. $10\uparrow ^{m}n$

Muistiinpanot

↑ Knuth, Donald E. Mathematics and Computer Science: Coping with Finiteness // Science : Journal. - 1976. - Voi. 194 . - s. 1235-1242 . - doi : 10.1126/tiede.194.4271.1235 .

Linkit

Weisstein, Eric W. Knuth Up-Arrow Notation (englanniksi) Wolfram MathWorld -verkkosivustolla .

Isoja lukuja
Numerot	googol Shannonin numero Googolplex Skewesin numero Moser numero Grahamin numero PUU(3) Rayo numero
Toiminnot	Ackermann-toiminto Veblen-toiminto Buchholzin Psi-funktiot tetration Pentation Hyperoperaattori Nopeasti kasvava hierarkia Hierarkia kasvaa hitaasti Kova hierarkia
Merkinnät	Steinhaus-Moser-merkintä Knuthin nuolen merkintä Conway-nuolen merkintä Massiivinen Bowers-merkintä