Knutova notacija

Iz Vikipedije, slobodne enciklopedije
Jump to navigation Jump to search

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]

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

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

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

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

Prema ovoj definiciji,

(u razloženom obliku, ovaj broj bi popunio nekoliko povećih hard diskova[1])
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':

dalje imamo operator 'četiri strelice':

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

Primeri:

Notacija[uredi]

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

Notacija sa zapisivanjem eksponenta iznad broja koji se diže na stepen, nije pogodna za generalizaciju, što objašnjava zašto je knut izabrao da radi sa strelicom na gore, .

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

Generalizacije[uredi]

Neki brojevi su toliko veliki da čak i zapis sa višestrukim strelicama na gore postaje preglomazan: tada je od koristi operator -strelica (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.

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

Definicija[uredi]

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

za sve cele brojeve i .

Svi operatori strelice na gore (uključujući klasično stepenovanje, ) su desno asocijativni, to jest, izračunavanje se sprovodi zdesna ulevo ukoliko izraz sadrži dva ili više takvih operatora. Na primer, , ne ; na primer
je a ne

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

Tablica vrednosti[uredi]

Računanje se može zapisati u beskonačnoj tablici. Zapisujemo brojeve 2 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 = 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
1 2 4 8 16 32 64 128
2 2 4 16 65536
3 2 4 65536      
4 2 4        

Napomena: označava funkcionalni stepen funkcije (funkcija se takođe označava sufiksom -pleks, kao kod gugolpleks).

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

Računanje

Stavimo brojeve 3 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 = hiper(3, m + 2, n) = 3 → n → m
m\n 1 2 3 4 5 formula
0 3 6 9 12 15
1 3 9 27 81 243
2 3 27 7.625.597.484.987  
3 3 7.625.597.484.987    
4 3      

Računanje

Popunimo prvu vrstu brojevima 10 , 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 = hiper(10, m + 2, n) = 10 → n → m
m\n 1 2 3 4 5 formula
0 10 20 30 40 50
1 10 100 1.000 10.000 100.000
2 10 10.000.000.000  
3 10      
4 10        

Vidi još[uredi]

Reference[uredi]

  1. ^ To jest bitova, ili oko 1,4 TB

Spoljašnje veze[uredi]