Knuth nyíl jelölése

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. szeptember 5-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A matematikában a Knuth-féle nyíl jelölés egy módszer nagy számok írására. Elképzelése azon alapul, hogy a szorzás többszörös összeadás , a hatványozás többszörös szorzás. Donald Knuth javasolta 1976 - ban [1] . Szorosan kapcsolódik az Ackermann függvényhez és a hiperoperátorok sorrendjéhez .

Tetráció , a Knuth-féle nyíl jelöléssel írva:

{\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{. \,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\ponts \uparrow a))} \\&&b&&b\end{mátrix}}

Pentation Knuth jelölésével:

{\begin{mátrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\pontok \uparrow \uparrow a))} \\&b\ vége{mátrix}}

A jelzett jelölésben b operandus található, amelyek mindegyike egyenlő a -val, a műveletek ismétlődnek . $b-1$

Bevezetés

A szokásos aritmetikai műveletek – összeadás, szorzás és hatványozás – természetesen kiterjeszthetők hiperoperátorok sorozatára a következőképpen:

A természetes számok szorzása ismétlődő összeadási művelettel határozható meg ("add hozzá az a szám b másolatát "):

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

Például,

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

A b hatványra emelése ismételt szorzási műveletként definiálható ("a b másolatok szorzása " ) , és Knuth jelölésében ez a jelölés úgy néz ki, mint egy felfelé mutató nyíl:

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

Például,

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

Egy ilyen felfelé mutató nyíl az Algol programozási nyelvben fokozatikonként volt használva .

A hatványozáson túli műveletsort folytatva Donald Knuth bevezette a „kettős nyíl” operátor fogalmát a tetració (többszörös hatványozás) írásához.

{\begin{matrix}a\uparrow \uparrow b&={\ ^{b}a}=&\underbrace {a^{a^{{}^{.\,^{.\,^{. \,^{a}}}}}}} &=&\underbrace {a\uparrow (a\uparrow (\ponts \uparrow a))} \\&&b&&b\end{mátrix}}

Például,

{\begin{matrix}4\uparrow \uparrow 3&={\ ^{3}4}=&\underbrace {4^{4^{4))} &=&\underbrace {4\uparrow (4 \uparrow 4)} &=&4^{256}\körülbelül 1{,}3\szer 10^{154}\\&&3&&3\end{mátrix}}

Itt és lent a kifejezés kiértékelése mindig jobbról balra halad, a Knuth-féle nyíl operátorok is (valamint a hatványozási művelet) definíció szerint jobb asszociativitással (jobbról balra sorrend) rendelkeznek. E meghatározás szerint

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

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

stb.

Ez már elég nagy számokhoz vezet, de a jelölés nem ér véget. A "hármas nyíl" operátor a "kettős nyíl" operátor ismételt hatványozásának írására szolgál (más néven " pentation "):

{\begin{mátrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow (a\uparrow \uparrow (\pontok \uparrow \uparrow a))} \\&b\ vége{mátrix}}

majd a "négyszeres nyíl" operátor:

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow (a\uparrow \uparrow \uparrow (\pontok \uparrow \uparrow \uparrow a))} \\&b\end{mátrix}}

Általános szabály, hogy az n- edik nyíl operátor, a jobb asszociativitás szerint, jobbra folytatódik egy n -1 nyíl operátorból álló szekvenciális sorozatba. Szimbolikusan ezt a következőképpen írhatjuk le:

{\begin{mátrix}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{mátrix}}

Például:

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 \ felfelé nyíl 3} \\&7625597484987\end{mátrix}}

A jelölési formát általában n nyíllal történő íráshoz használják . $a\uparrow ^{n}b$ $a\uparrow \uparrow \ponts \uparrow b$

Jelölési rendszer

Az olyan kifejezésekben, mint a , gyakori, hogy a kitevőt az alap felső indexeként írják a hatványozás jelölésére . De sok más környezet – például a programozási nyelvek és az e-mail – nem támogatja ezt a kétdimenziós konfigurációt. Ezért a felhasználóknak lineáris jelölést kell használniuk az ilyen környezetekhez; a felfelé mutató nyíl azt sugallja , hogy a hatalmat kell emelni . Ha nincs felfelé mutató nyíl a rendelkezésre álló karakterek között, akkor a „^” javító beszúrási jel kerül felhasználásra . $a^{b}$ $b$ $a$ $a\uparrow b$ $a^{b}$ $a\uparrow b$

Megnevezés "↑"

Ha megpróbálunk egy kifejezést az ismerős jelöléssel kitevőkkel írni, hatványok tornyát hoz létre. Például: $a\uparrow \uparrow b$

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

Ha b változó (vagy nagyon nagy), a foktornyot pontokkal és a torony magasságát jelző jelöléssel írhatjuk fel.

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

Ezzel a jelölési formával a kifejezés felírható olyan erőtornyok halmazaként ( veremként ), amelyek mindegyike jelzi a fedőréteg mértékét. $a\uparrow \uparrow \uparrow b$

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

És ismét, ha b változó (vagy nagyon nagy), akkor az ilyen erőtornyok halmaza felírható pontok segítségével, és felcímkézhető a magasságuk jelzésére.

a\uparrow \uparrow \uparrow b=\left.\underbrace {a^{{a^{{.^{{.^{{.{a))))))))))_{{\bezárás { a^{{a^{{.^{.^{{.{a))))))))))_({\aláhúzás {\vdots }_{{a))))))\jobbra \}b.

Sőt, a kifejezés felírható több hasonló erőtornyok oszlopával is, ahol minden oszlop a bal oldali készletben lévő erőtornyok számát jelzi. $a\uparrow \uparrow \uparrow \uparrow b$

a\uparrow \uparrow \uparrow \uparrow \uparrow a^{{.^{{.^{{.{a}}}}}}}}}}_{{\underbrace {a^{{a^{{.^{{.^{{.{a )))))))))))))_{{\bezárás {\vdots }_{{a))))))\jobbra\}\bezárás {a^{{a^{{.^{{. ^ {{.{a}}}}}}}}}}_{{\underbrace {a^{{a^{{.^{{.^{{.{a}}}}}}}}} } _{{\zárójel {\vdots }_{{a))))))\jobbra\}\zárójel {a^{{a^{{.^{{.^{{.{a)))) } )))))_{{\kapcsos zárójel {a^{{a^{{.^{{.^{{.{a))))))))))_{{\zárójel {\vdots } _ {{a}}}}}}\jobbra\}a.

Általánosabban:

a\uparrow \uparrow \uparrow \uparrow b=\underbrace {\left.\left.\left.\underbrace {a^{{a^{{.^{{.^{{.{a))))} )))))))_{{\bezárás {a^{{a^{{.^{{.^{{.{a))))))))))_{{\zárójel {\vdots }_ {{a}}}}}}\jobbra\}\kapcsos zárójel {a^{{a^{{.^{{.^{{.{a}}}}}}}}}}_{{\zárójel {a^{{a^{{.^{{.^{{.{a))))))))))_({\aláhúzás {\vdots }_{{a))))))) \ right\}\cdots \right\}a}_{{b}}.

Ezt a végtelenségig felírhatjuk, hogy tetszőleges a , n és b hatványozási iterációjaként ábrázoljuk (bár nyilvánvaló, hogy ez is meglehetősen nehézkessé válik). $a\uparrow ^{n}b$

A tetració használata

A tetraciós jelölés lehetővé teszi az ilyen sémák egyszerűsítését, miközben továbbra is geometriai ábrázolást alkalmazunk (nevezhetjük tetraciós tornyoknak ). $^{{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} _ {{\alábrace {^{{^{{^{{^{{^{{{a}}.}}.}}.}}a}}a}_{{\aláhúzás {\vdots }_{ {a }}}}}}\jobbra\}b.

Végül példaként a negyedik Ackermann-számot a következőképpen írhatjuk fel: $4\uparrow ^{4}4$

\kapcsos zárójel {^{{^{{^{{^{{^{{4}}.}}.}}.}}.}}4}}4}_({\kapcsos zárójel {^{{^{{^{{ ^{{^{{4}}.}}.}}.}}4}}4}_{{\underbrace {^{{^{{^{{^{{^{{4}}.}} .}}.}}4}}4}_{{4}}}}}}=\zárójel {^{{^{{^{{^{{^{{4}}.}}.}}. }}4}}4}_{{\underbrace {^{{^{{^{{^{{^{{4}}.}}.}}.}}4}}4}_{{^{ {^{{^{{4}}4}}4}}4}}}}.

Általánosítás

Egyes számok olyan nagyok, hogy még Knuth nyilaival írni is túlságosan nehézkessé válik; ebben az esetben előnyben részesítjük az n -arrow operátort (és a változó számú nyilak leírásához is), vagy ezzel egyenértékű a hiperoperátorokkal szemben . De néhány szám olyan hatalmas, hogy még egy ilyen jelölés sem elegendő. Például a Graham-szám . Írásához Conway-lánc használható : a három elemből álló lánc egyenértékű egy másik jelöléssel, de a négy vagy több elemből álló lánc egy erősebb jelölési forma. $\uparrow ^{n}$

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

Gyakori a Knuth-féle nyíl jelölés kis számokhoz, és láncnyilak vagy hiperoperátorok nagy számokhoz.

Definíció

A felfelé mutató nyíl jelölése formálisan úgy van meghatározva

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{egyébként}}\end{mátrix}}\jobbra .

minden olyan egész számra, ahol . $légi úton szállított$ $b\geq 0,n\geq 1$

Minden nyíl operátor (beleértve a közönséges hatványozást is) jobbra asszociatív , azaz jobbról balra értékelődik ki, ha a kifejezés két vagy több hasonló operátort tartalmaz. Például, $a\uparrow b$

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

, de nem ;

(a\uparrow b)\uparrow c

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

egyenlő , de nem

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

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

Jó oka van a jobbról balra haladó számítási irány megválasztásának. Ha a balról jobbra irányú számítási módszert használnánk, akkor ez egyenlő lenne -vel , és akkor nem igazán lenne új operátor. $a\uparrow \uparrow b$ $a\uparrow (a\uparrow (b-1))$ $\uparrow \uparrow$

A helyes asszociativitás a következő okból is természetes. A kibontáskor megjelenő ismétlődő nyílkifejezéseket átírhatjuk a következőre , ahol az összes a a nyíl operátorok bal oldali operandusaivá válik. Ez azért fontos, mert a nyíl operátorok nem kommutatívak . $a\uparrow ^{n}\cdots \uparrow ^{n}a,$ $a\uparrow ^{{n+1}}b$ $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$

Ha a függvény b funkcionális kitevőjeként írunk , azt kapjuk . $(a\uparrow ^{m})^{b}$ $f(x)=a\uparrow ^{m}x,$ $a\uparrow ^{n}b=(a\uparrow ^{{n-1}})^{b}1$

A definíciót még egy lépéssel folytathatjuk , n = 0 esetén, mivel a hatványozás ismétlődő szorzás, 1-től kezdve. Még egy lépés extrapolálása, a szorzás ismételt összeadásként való írása nem teljesen helyes, mivel a szorzás ismételt összeadás, kezdve 1 helyett 0. Egy lépés újbóli "extrapolálásához", az n növekménynek 1 ismételt összeadásaként történő felírásához az a számmal kell kezdeni . Ezt a különbséget a hiperoperátor definíciója is hangsúlyozza , ahol az összeadás és a szorzás kezdeti értékei külön vannak megadva. $a\uparrow ^{n}b=ab$

Értéktáblázat

A számítás újrafogalmazható egy végtelen tábla formájában. A számokat a felső sorba helyezzük, és a bal oldali oszlopot kitöltjük a 2-es számmal. A táblázat számának meghatározásához vegyük a balhoz legközelebbi számot, majd az előző sorban felül keressük meg a kívánt számot. az éppen kapott érték által adott pozíció. $2\uparrow ^{m}n$ $2^{n}$

Értékek = hiper (2, m + 2, n ) = 2 → n → m

2\uparrow ^{m}n

m \ n	egy	2	3	négy	5	6	Képlet
egy	2	négy	nyolc	16	32	64	$2^{n}$
2	2	négy	16	65536	$2^{65536}\approx 2{,}0\x 10^{19,729}$	$2^{2^{65536}}\körülbelül 10^{6{,}0\szer 10^{19 728}}$	$2\uparrow \uparrow n$
3	2	négy	65536	${\begin{mátrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{mátrix}}$			$2\uparrow \uparrow \uparrow n$
négy	2	négy	${\begin{mátrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2))))))}\\65536 \end{mátrix}}$				$2\uparrow \uparrow \uparrow \uparrow n$

A táblázat ugyanaz, mint az Ackerman-függvény cikkében, kivéve a és értékeinek eltolódását , valamint 3-at az összes értékhez. $m$ $n$

Számítás $3\uparrow ^{m}n$

A számokat a felső sorba helyezzük, és a bal oldali oszlopot kitöltjük a 3-as számmal. A táblázat számának meghatározásához vegyük a balhoz legközelebbi számot, majd az előző sorban felül keressük meg a kívánt számot. az éppen kapott érték által adott pozíció. $3^n$

Értékek = hiper (3, m + 2, n ) = 3 → n → m

3\uparrow ^{m}n

m \ n	egy	2	3	négy	5	Képlet
egy	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{mátrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3))))))} \\7,625,597,484,987 \end{mátrix}}$			$3\uparrow \uparrow \uparrow n$
négy	3	${\begin{mátrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3))))))} \\7,625,597,484,987 \end{mátrix}}$				$3\uparrow \uparrow \uparrow \uparrow n$

Számítás $10\uparrow ^{m}n$

A számokat a felső sorba helyezzük, és a bal oldali oszlopot kitöltjük a 10-es számmal. A táblázat számának meghatározásához vegyük a balhoz legközelebbi számot, majd az előző sorban felül keressük meg a kívánt számot. az éppen kapott érték által adott pozíció. $10^{n}$

Értékek = hiper (10, m + 2, n ) = 10 → n → m

10\uparrow ^{m}n

m \ n	egy	2	3	négy	5	Képlet
egy	tíz	100	1000	10 000	100 000	$10^{n}$
2	tíz	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	tíz	${\begin{mátrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 \end{mátrix}}$	${\begin{mátrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 ^{10}\end{mátrix}}$	${\begin{mátrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10)))))))} \\ 10 ^{10^{10}}\end{mátrix}}$		$10\uparrow \uparrow \uparrow n$
négy	tíz	${\begin{mátrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10\end{mátrix))$	${\begin{mátrix}\underbrace {^{^{^{^{^{10}.}.}.}10}10} \\10^{10}\end{mátrix))$			$10\uparrow \uparrow \uparrow \uparrow n$

2 ≤ n ≤ 9 esetén a numerikus sorrend az a lexikográfiai sorrend , amelyben m a legjelentősebb szám, így ennek a 8 oszlopnak a számsorrendje csak soronként. Ugyanez vonatkozik a 97 oszlopban lévő számokra, ahol 3 ≤ n ≤ 99, és m = 1-gyel indulunk akkor is, ha 3 ≤ n ≤ 9 999 999 999. $10\uparrow ^{m}n$

Jegyzetek

↑ Knuth, Donald E. Mathematics and Computer Science: Coping with Finiteness // Science : Journal. - 1976. - 1. évf. 194 . - P. 1235-1242 . - doi : 10.1126/tudomány.194.4271.1235 .

Linkek

Weisstein, Eric W. Knuth felfelé nyíl jelölés (angolul) a Wolfram MathWorld webhelyen .

Nagy számok
Számok	googol Shannon szám Googolplex Skewes szám Moser szám Graham szám FA (3) Rayo szám
Funkciók	Ackermann függvény Veblen funkció Buchholz Pszi-függvényei tetració Pentation Hiperoperátor Gyorsan növekvő hierarchia Lassan növekvő hierarchia Hardy hierarchia
Jelölések	Steinhaus-Moser jelölés Knuth nyíl jelölése Conway nyíl jelölése Massive Bowers jelölés