Algoritamska informaciona teorija

Algoritamska informaciona teorija je podvrsta teorije informacija i informatike koja se bavi vezom između teorije izračunljivosti i informacija. Prema Gregoriju Čejtinu, ona je "rezultat sipanja Šenonove informacione teorije i Tjuringove teorije izračunljivosti u koktel i njihovog mešanja."

Pregled

Algoritamska informaciona teorija u svojoj osnovi izučava kompleksna merenja nad stringovima (ili drugim strukturama podataka). Pošto se mnogo matematičkih objekata mogu predstaviti u obliku stringova, ili kao granica niza stringova, ona se može koristiti za izučavanje velikog broja matematičkih objekata, uključujući i cele brojeve.

Neformalno, iz perspektive algoritamske informacione teorije, informacioni sadržaj stringa je ekvivalentan dužini najkompresovanije moguće samosadržavajuće reprezentacije tog stringa. Takva reprezentacija je u osnovi računarski program – u nekim fiksiranim, ali ipak irelevantnim univerzalnim programskim jezicima – koji, kada su pokrenuti, ispisuju originalan string.

Iz ove tačke gledišta, enciklopedija od 3000 strana zapravo sadrži manje informacija nego 3000 strana nasumičnih slova, uprkos činjenici da je enciklopedija mnogo korisnija. To je zato što da bi rekonstruisali cele sekvence nasumičnih slova, moramo znati koje je svako slovo. U drugu ruku, ako svaki samoglasnik izbrišemo iz enciklopedije, neko sa umerenim znanjem srpskog jezika bi je mogao rekonstruisati, kao što bi neko mogao rekonstruisati rečenicu "Ov rčnc sdrž ml pdtk" iz konteksta i postojećih suglasnika.

Za razliku od klasične informacione teorije, algoritamska informaciona teorija nam daje logički sistem, rigorozne definicije nasumičnog stringa i nasumičnog beskonačnog niza koje ne zavise od fizičke i filozofske intuicije o nedeterminizmu ili verovatnoći. (Niz nasumičnih stringova zavisi od izbora univerzalne Tjuringove mašine koja se koristi da definiše Kolgomorovu kompleksnost, ali svaki izbor nam daje identične asimptotske rezultate zato što Kolmogorova kompleksnost stringa invarijantna do dodajuće konstante, zaviseći samo od izbora univerzalne Tjuringove mašine. Zbog toga, niz nasumičnih beskonačnih sekvenca je nezavisan od izbora univerzalne mašine.)

Neki od rezultata algoritamske informacione teorije, kao na primer Čejtinova teorema nepotpunosti, naizgled se protivi matematičkim i filozofskim intuicijama. Najistaknutija je konstrukcija Čejtinove konstante Ω, realan broj koji iskazuje verovatnoću da će se samoograničavajuća univerzalna Tjuringova mašina zaustaviti kada je njen unos određen poštenim bacanjem novčića. Iako je broj Ω lako definisan, u bilo kojoj doslednoj aksiomatskoj teoriji moguće je samo izračunati konačno mnogo cifara broja Ω, tako da je u nekom smislu nepoznat, pružajući apsolutnu granicu znanja koja podseća na Gedelove teoreme o nepotpunosti. Iako se cifre broja Ω ne mogu odrediti, mnoge osobine su mu poznate; na primer, on je algoritamski nasumičan niz, stoga su njegove binarne cifre jednako raspoređene (zapravo je normalan broj).

Istorija

Algoritamsku informacionu teoriju je osnovao Rej Solomonov, koji je izdao osnovne ideje na kojima je ova oblast zasnovana kao deo njegovog pronalaska algoritamske verovatnoće - načina da se prevaziđu ozbiljni problemi povezani sa primenom Bejevih pravilas u statistici. On je prvi put opisao svoje rezultate na konferenciji u Kalifornijskom tehnološkom institutu 1960. godine, and in a report, February 1960, "A Preliminary Report on a General Theory of Inductive Inference." Algoritamska informaciona teorija se kasnije razvijala nezavisno od strane Andreja Kolmogorova, u 1965. i Gregorija Čejtina, oko 1966.

Postoji par varijacija Kolmogorove kompleksnosti ili algoritamske informacije; najkorišćenija je bazirana na samoograničavajućim programima zbog Leonida Levina (1974). Per Martin-Lof je takođe ozbiljno doprineo informacionoj teoriji beskonačnih sekvenci. Aksiomski pristup algoritamskoj informacionoj teoriji baziran na Blumobim aksiomama (Blum 1967) je predstavljen od strane Marka Burgina u članku koji je podnet za objavljivanje od strane Andreja Kolmogorova (Burgin 1982). Aksimoski pristup obuhvata ostale pristupe u algoritamskoj informacionoj teoriji. Moguće je tretirati različita merenja algoritamske informacije kao specifične slučajeve aksiomatski definisanih merenja nje same. Umesto dokazivanja sličnih teorema, kao što je osnovna teorema invarijantnosti, za svako određeno merenje, moguće je sa lakoćom dedukovati sve rezulate iz jedne slične teoreme dokazane aksiomskim putem. Ovo je prednost aksiomskog pristupa u matematici. Aksiomski pristup algoritamskoj informacionoj teoriji je detaljnije razvijen u knjizi (Burgin 2005) primenjen na softverskoj metrici (Burgin i Debnat, 2003; Debnat i Burgin, 2003).

Precizne definicije

Glavni članak: Kolmogorova kompleksnost

Binarni string je nasumičan ako je Kolmogorova kompleksnost stringa barem dužine tog stringa. Jednostavno prebrojavanje pokazuje da su neki stringovi, bilo koje dužine, nasumični i skoro su svi oni veoma blizu da budu nasumični. Pošto Kolmogorova kompleksnost zavisi od fiksiranog izbora univerzalne Tjuringove mašine (neformalno, definisan "opisni jezik" za koji su "opisi" zadati), kolekcija nasumičnih stringova zavisi od izbora fiksirane univerzalne mašine. Kolekcija nasumičnih stringova, u celini, ima slične osobine nezavisno od fiksirane mašine, tako da možemo pričati o osobinama nasumičnih stringova kao o grupi, a često to i radimo, bez potrebe da specificiramo fiksiranu mašinu.

Glavni članak: Algoritamski nasumični nizovi

Beskonačna binarna sekvenca je nasumična ako za neku konstantu c, za svako n, Kolmogorova kompleksnost inicijalnog segmenta dužine n te sekvence je barem n − c. Može se pokazati da je skoro svaka sekvenca (iz gledišta standardnog merenja — "poštenog bacanja novčića" ili Mera Lebega — u okviru binarnih beskonačnih sekvenca) nasumična. Takođe, pošto se može pokazati da se Kolmogorova kompleksnost, relativna dvema univerzalnim mašinama, razlikuje najviše za konstantu, kolekcija nasumičnih beskonačnih sekvenci ne zavisi od izbora univerzalne mašine (nasuprot konačnim stringovima). Ova definicija nasumičnosti se obično naziva Martin-Lof nasumičnost, po Per Martin-Lof, tako da je razlikujemo od ostalih, sličnih, notacija nasumičnosti. Ponekad je nazivamo i 1-nasumičnost da bi je razlikovali od ostalih, jačih, notacija nasumičnosti (2-nasumičnost, 3-nasumičnost, itd.). Pored Martin-Lof koncepta nasumičnosti postoje i rekurzivne nasumičnosti, Šnor nasumičnost i Kurc nasumičnost itd. Jong Vang je pokazao da svi ovi koncepti nasumičnosti su različiti.

(Related definitions can be made for alphabets other than the set $\{0,1\}$.)

Specifične sekvence

Algoritamska informaciona teorija (AIT) je informaciona teorija induvidualnih objekata. Koristi principe informatike i bavi se vezama između izračunavanja, informacija i nasumičnosti.

Informacioni sadržaj ili kompleksnost objekta može se meriti dužinom njegovog najkraćeg opisa. Na primer, string:

"0101010101010101010101010101010101010101010101010101010101010101"

ima kratak opis "32 ponavljanja '01'", dok

"1100100001100001110111101110110011111010010000100101011110010110"

verovatno nema jednostavnijeg opisa od pisanja samog stringa.

Formalnije, algoritamska kompleksnost (AK) stringa x je definisana kao dužina najmanjeg programa koji izračunava ili ispisuje x, gde se program pokreće na nekom fiksiranom referencnom univerzalnom kompjuteru.

Blisko povezan pojam je verovatnoća da univerzalni kompjuter ispisuje neki string x ukoliko je preopterećen nasumično izabranim programom. Ova algoritamska "Solomonov" verovatnoća (AV) je ključ pri interpretaciji starog filozofskog problema indukcije na formalan način.

Loše strane AK i AV su njihove neizračunljivosti. Vremenski zahtevna "Levin" kompleksnost kažnjava spor program dodajući vreme trajanja algoritma njegovoj dužini. Ovo dovodi do izračunljivih varijanti AK i AV, i univerzalna "Levin" pretraga (UP) rešava sve inverzne probleme u optimalnom vremenu (izuzev nekih nerealno velikih multiplikativnih konstanti).

AK i AV omogućavaju formalnu i rigoroznu definiciju nasumičnosti induvidualnih stringova da ne zavise od fizičkih i filozofskih intuicija o nedeterminizmu ili verovatnoće. Ugrubo, string je algoritamski "Martin-Lof" nasumičan (AN) ako ne može da se kompresuje, u smislu da je njegova algoritamska kompleksnost jednaka njegovoj dužini.

AK, AV, i AN su ključne poddiscipline algoritamske informacione teorije, ali ona se prostire u mnogo drugih oblasti. Služi kao temelj principu minimalne opisne dužine (MOD), može da pojednostavi dokaze u kompleksnoj teoriji izračunljivosti, koristi se da definiše univerzalnu metriku sličnosti između objekata, rešava problem Maksvelovog demona i mnogo drugog.

Vidi još

• Solomonova teorija induktivnog zaključka
• Kolmogorova kompleksnost
• Algoritamski nasumičan niz
• Algoritamska verovatnoća
• Čejtinova konstanta
• Čejtin-Kolmogorova nasuimčnost
• Računska neprimetnost
• Distribucijski ansambl
• Epistemologija
• Indukcija (logika)
• Induktivna verovatnoća
• Teorema invarijante
• Minimalna dužina opisa
• Minimalna dužina poruke
• Pseudonasumični ansambl
• Pseudonasumični generator
• Teorija jednostavnosti

Literatura

• Blum, M. (1967) On the Size of Machines, Information and Control, v. 11. str. 257–265
• Blum M. (1967a) A Machine-independent Theory of Complexity of Recursive Functions, Journal of the ACM, v. 14, No.2. str. 322–336
• Burgin, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Soviet Math. Dokl., v.25, No. 3. str. 19–23
• Burgin, M. (1990) Generalized Kolmogorov Complexity and other Dual Complexity Measures, Cybernetics, No. 4. str. 21–29
• Burgin, M. Super-recursive algorithms, Monographs in computer science, Springer, 2005
• Calude, C.S. (1996) Algorithmic information theory: Open problems, J. UCS, v. 2. str. 439–441
• Calude, C.S. Information and Randomness: An Algorithmic Perspective, (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag, Berlin, 2002
• Chaitin, G.J. (1966) On the Length of Programs for Computing Finite Binary Sequences, J. Association for Computing Machinery, v. 13, No. 4. str. 547–569
• Chaitin, G.J. (1969) On the Simplicity and Speed of Programs for Computing Definite Sets of Natural Numbers, J. Association for Computing Machinery, v. 16. str. 407–412
• Chaitin, G.J. (1975) A Theory of Program Size Formally Identical to Information Theory, J. Association for Computing Machinery, v. 22, No. 3. str. 329–340
• Chaitin, G.J. (1977) Algorithmic information theory, IBM Journal of Research and Development, v.21, No. 4, 350-359
• Chaitin, G.J. Algorithmic Information Theory, Cambridge University Press, Cambridge, 1987
• Kolmogorov, A.N. (1965) Three approaches to the definition of the quantity of information, Problems of Information Transmission, No. 1. str. 3–11
• Kolmogorov, A.N. (1968) Logical basis for information theory and probability theory, IEEE Trans. Inform. Theory, vol. IT-14. str. 662–664
• Levin, L. A. (1974) Laws of information (nongrowth) and aspects of the foundation of probability theory, Problems of Information Transmission, v. 10, No. 3. str. 206–210
• Levin, L.A. (1976) Various Measures of Complexity for Finite Objects (Axiomatic Description), Soviet Math. Dokl., v. 17. str. 522–526
• Li, M., and Vitanyi, P. An Introduction to Kolmogorov Complexity and its Applications, Springer-Verlag, New York, 1997
• Solomonoff, R.J. (1960) A Preliminary Report on a General Theory of Inductive Inference, Technical Report ZTB-138, Zator Company, Cambridge, Mass.
• Solomonoff, R.J. (1964) A Formal Theory of Inductive Inference, Information and Control, v. 7, No. 1. str. 1–22; No.2. str. 224–254
• Solomonoff, R.J. (2009). Emmert-Streib, F.; Dehmer, M., ur. Algorithmic Probability: Theory and Applications, Information Theory and Statistical Learning. Springer NY. ISBN 978-0-387-84815-0. 
• Lambagen, Van (1989). „Algorithmic Information Theory”. Journal for Symbolic Logic. 54: 1389—1400. doi:10.1017/S0022481200041153. 
• Zurek, W.H. (1991) Algorithmic Information Content, Church-Turing Thesis, physical entropy, and Maxwell’s demon, in Complexity, Entropy and the Physics of Information, (Zurek, W.H., Ed.) Addison-Wesley. str. 73–89
• Zvonkin, A.K. and Levin, L. A. (1970) The Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms, Russian Mathematics Surveys, v. 256. str. 83–124

Spoljašnje veze

• Algorithmic Information Theory (Scholarpedia)
• Chaitin's account of the history of AIT.