Knutova notacija

U matematici, Knutova notacija je notacija za zapisivanje vrlo velikih celih brojeva. Uveo ju je Donald Knut 1976. godine. Ideja je zasnovana na ponovljenom stepenovanju na sličan način na koji je stepenovanje ponovljeno množenje, a množenje je ponovljeno sabiranje.

Uvod[uredi | uredi izvor]

Množenje prirodnim brojem se može definisati kao ponovljeno sabiranje:

{\begin{matrix}ab&=&\underbrace {a_{}+a+\dots +a} \\&&b{\mbox{ primeraka }}a\end{matrix}}

a stepenovanje prirodnim stepenom $b$ se može definisati kao ponovljeno množenje:

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

što je inspirisalo Knuta da definiše operator 'dvostruke strelice' za ponovljeno stepenovanje:

{\begin{matrix}a\uparrow \uparrow b&=&\underbrace {a_{}^{a^{{}^{.\,^{.\,^{.\,^{a}}}}}}} &=&\underbrace {a_{}\uparrow a\uparrow \dots \uparrow a} \\&&b{\mbox{ primeraka }}a&&b{\mbox{ primeraka }}a\end{matrix}}

Ovde i nadalje izračunavanje se sprovodi zdesna ulevo (kao takva, operacija je desno asocijativna):

Prema ovoj definiciji,

3\uparrow \uparrow 2=3^{3}=27\,\!

3\uparrow \uparrow 3=3^{3^{3}}=3^{27}=7625597484987\,\!

3\uparrow \uparrow 4=3^{3^{3^{3}}}=3^{7625597484987}\,\!

(u razloženom obliku, ovaj broj bi popunio nekoliko povećih hard diskova^[1])

3\uparrow \uparrow 5=3^{3^{3^{3^{3}}}}=3^{3^{7625597484987}}\,\!

itd.

Ovo već vodi do prilično velikih brojeva, ali Knut je proširio svoju notaciju. Definisao je operator 'trostruke strelice' za ponovljenu primenu operatora 'dvostruke strelice':

{\begin{matrix}a\uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow a\uparrow \uparrow \dots \uparrow \uparrow a} \\&b{\mbox{ primeraka }}a\end{matrix}}

dalje imamo operator 'četiri strelice':

{\begin{matrix}a\uparrow \uparrow \uparrow \uparrow b=&\underbrace {a_{}\uparrow \uparrow \uparrow a\uparrow \uparrow \uparrow \dots \uparrow \uparrow \uparrow a} \\&b{\mbox{ primeraka }}a\end{matrix}}

i tako dalje. Opšte pravilo je da se operator $n$ strelica razlaže u seriju operatora $n-1$ strelica. Simbolički,

{\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{\mbox{ primeraka }}a\end{matrix}}

Primeri:

$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{\mbox{ primeraka }}3\end{matrix}}{\begin{matrix}=&\underbrace {3_{}\uparrow 3\uparrow \dots \uparrow 3} \\&{\mbox{7.625.597.484.987 primeraka 3}}\end{matrix}}$

Notacija[uredi | uredi izvor]

U izrazima kao što je $a^{b}$ , notacija za stepenovanje obično podrazumeva da se eksponent $b$ zapisuje iznad sa desne strane od baznog broja $a$ . Međutim, mnoga okruženja – kao što su programski jezici – ne podržavaju takav dvodimenzioni zapis. Zbog toga je usvojena linearna notacija $a\uparrow b$ za ovakva okruženja; strelica nagore predstavlja 'dizanje na stepen'. Ako u skupu karaktera ne postoji strelica nagore, koristi se simbol ^.

Notacija sa zapisivanjem eksponenta iznad broja koji se diže na stepen, $a^{b}$ nije pogodna za generalizaciju, što objašnjava zašto je knut izabrao da radi sa strelicom nagore, $a\uparrow b$ .

U kontekstu programskog jezika C, karakter ^ označava ekskluzivno ili XOR. ** je uobičajena alternativa za $\uparrow$ pa je u ovom kontekstu moguće koristiti dva simbola za ponavljanje operatora. Moguće je uzeti da je *** ekvivalentno sa $\uparrow \uparrow$ , ali ova upotreba nije uobičajena.

Generalizacije[uredi | uredi izvor]

Neki brojevi su toliko veliki da čak i zapis sa višestrukim strelicama nagore postaje preglomazan: tada je od koristi operator $n$ -strelica $\uparrow ^{n}$ (kao i za opise sa promenljivim brojem strelica), ili ekvivalentno, hiper operatori.

Neki brojevi su toliko veliki da ni ovakva notacija nije dovoljna. Primer za ovo je Grejemov broj. U ovim slučajevima se može koristiti Konvejeva lančana notacija: lanac od tri elementa je ekvivalentan ostalim notacijama, ali lanac od četiri elementa je još veći.

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

Obično se Knutova notacija koristi za brojeve relativno manje magnitude, a lančane strelice ili hiper operatori za veće brojeve.

Definicija[uredi | uredi izvor]

Knutova notacija se formalno definiše na sledeći način

a\uparrow ^{n}b=\left\{{\begin{matrix}a^{b},&{\mbox{ako }}n=1;\\1,&{\mbox{ako }}b=0;\\a\uparrow ^{n-1}(a\uparrow ^{n}(b-1)),&{\mbox{u suprotnom}}\end{matrix}}\right.

za sve cele brojeve $a,b,n$ i $b\geq 0,n\geq 1$ .

Svi operatori strelice nagore (uključujući klasično stepenovanje, $a\uparrow b$ ) su desno asocijativni, to jest, izračunavanje se sprovodi zdesna ulevo ukoliko izraz sadrži dva ili više takvih operatora. Na primer, $a\uparrow b\uparrow c=a\uparrow (b\uparrow c)$ , ne $(a\uparrow b)\uparrow c$ ; na primer
$3\uparrow \uparrow 3=3^{3^{3}}$ je $3^{(3^{3})}=3^{27}=7625597484987$ a ne $\left(3^{3}\right)^{3}=27^{3}=19683.$

Postoji dobar razlog zašto je izabran ovakav redosled izračunavanja. Da je korišćeno izračunavanje sleva udesno, tada bi $a\uparrow \uparrow b$ bilo jednako $a\uparrow (a\uparrow (b-1))$ , pa $\uparrow \uparrow$ suštinski ne bi bilo nova operacija. Desna asocijativnost je takođe prirodna jer možemo da prepišemo ponovljeni sa strelicama $a\uparrow ^{n}\cdots \uparrow ^{n}a$ koji se ponavlja u razvoju $a\uparrow ^{n+1}b$ kao $a\uparrow ^{n}\cdots \uparrow ^{n}a\uparrow ^{n}1$ , pa je svako $a$ levi operand operatora strelice. Ovo je značajno jer operatori strelice nisu komutativni.

Tablica vrednosti[uredi | uredi izvor]

Računanje $2\uparrow ^{m}n$ se može zapisati u beskonačnoj tablici. Zapisujemo brojeve 2 $n$ u prvoj vrsti, i punimo desnu kolonu vrednostima 2. Kako bi se odreila neka vrednost u tablici, uzima se broj odmah levo od nje, a zatim se traži broj u prethodnoj vrsti na pziciji označenoj ovim brojem.

Vrednosti $2\uparrow ^{m}n$ = hiper(2, m + 2, n) = 2 → n → m
m\n	1	2	3	4	5	6	7	formula
0	2	4	6	8	10	12	14	$2n$
1	2	4	8	16	32	64	128	$2^{n}$
2	2	4	16	65536	$2^{65536}\approx 2,0\times 10^{19.729}$	$2^{2^{65536}}\approx 10^{6,0\times 10^{19.728}}$	$2^{2^{2^{65536}}}\approx 10^{10^{6,0\times 10^{19.728}}}$	$2\uparrow \uparrow n$
3	2	4	65536	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ primeraka }}2\end{matrix}}\approx (10\uparrow )^{65531}(6,0\times 10^{19.728})$				$2\uparrow \uparrow \uparrow n$
4	2	4	${\begin{matrix}\underbrace {2_{}^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}} \\65536{\mbox{ primeraka }}2\end{matrix}}$					$2\uparrow \uparrow \uparrow \uparrow n$

Napomena: $(10\uparrow )^{k}$ označava funkcionalni stepen funkcije $f(n)=10^{n}$ (funkcija se takođe označava sufiksom -pleks, kao kod gugolpleks).

Tablica je ista kao kod Akermanove funkcije, osim zamene $m$ i $n$ , i dodatka 3 svim vrednostima.

Računanje $3\uparrow ^{m}n$

Stavimo brojeve 3 $n$ u gornju vrstu, i popunimo levu kolonu trojkama. Kako bi odredili neku vrednost u tabeli, uzmemo broj odmah levo do njega, i potražimo broj u prethodnoj vrsti, na poziciji koju označava broj koji smo uzeli.

Vrednosti $3\uparrow ^{m}n$ = hiper(3, m + 2, n) = 3 → n → m
m\n	1	2	3	4	5	formula
0	3	6	9	12	15	$3n$
1	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{\mbox{ primeraka }}3\end{matrix}}$			$3\uparrow \uparrow \uparrow n$
4	3	${\begin{matrix}\underbrace {3_{}^{3^{{}^{.\,^{.\,^{.\,^{3}}}}}}} \\7.625.597.484.987{\mbox{ primeraka }}3\end{matrix}}$				$3\uparrow \uparrow \uparrow \uparrow n$

Računanje $10\uparrow ^{m}n$

Popunimo prvu vrstu brojevima 10 $n$ , a prvu kolonu desetkama. Kako bi odredili neku vrednost u tabeli uzmimamo broj odmah levo do ove pozicije, i potražimo broj u prethodnoj vrsti, na poziciji koju označava broj koji smo uzeli.

Vrednosti $10\uparrow ^{m}n$ = hiper(10, m + 2, n) = 10 → n → m
m\n	1	2	3	4	5	formula
0	10	20	30	40	50	$10n$
1	10	100	1.000	10.000	100.000	$10^{n}$
2	10	10.000.000.000	$10^{10.000.000.000}$	$10^{\,\!10^{10.000.000.000}}$		$10\uparrow \uparrow n$
3	10	${\begin{matrix}\underbrace {10_{}^{10^{{}^{.\,^{.\,^{.\,^{10}}}}}}} \\10{\mbox{ primeraka }}10\end{matrix}}$				$10\uparrow \uparrow \uparrow n$
4	10					$10\uparrow \uparrow \uparrow \uparrow n$

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

^ To jest $7.625.597.484.987\times {\frac {\log 3}{\log 2}}$ bitova, ili oko 1,4 TB

Spoljašnje veze[uredi | uredi izvor]

Erik V. Vajsštajn, Notacija strelica na sajtu MathWorld
Robert Munafo, Veliki brojevi

[1] To jest $7.625.597.484.987\times {\frac {\log 3}{\log 2}}$ bitova, ili oko 1,4 TB

[1]

p r u Donald Knut
Publikacije	The Art of Computer Programming "The Complexity of Songs" Computers and Typesetting Concrete Mathematics Surreal Numbers Things a Computer Scientist Rarely Talks About Selected papers series
Softver	TeX METAFONT MIXAL (MIX MMIX GNU MDK)
Fontovi	AMS Euler Computer Modern Concrete Roman
Literarno programiranje	WEB CWEB
Algoritmi	Knuth's Algorithm X Knuth–Bendix completion algorithm Knuth–Morris–Pratt algorithm Knuth shuffle Robinson–Schensted–Knuth correspondence Trabb Pardo–Knuth algorithm Generalization of Dijkstra's algorithm Knuth's Simpath algorithm
Ostalo	Dancing Links Knuth reward check Knuth Prize Man or boy test Quater-imaginary base -yllion Potrzebie system of weights and measures