Алгоритамска информациона теорија

Алгоритамска информациона теорија је подврста теорије информација и информатике која се бави везом између теорије израчунљивости и информација. Према Грегорију Чејтину, она је "резултат сипања Шенонове информационе теорије и Тјурингове теорије израчунљивости у коктел и њиховог мешања."

Преглед

Алгоритамска информациона теорија у својој основи изучава комплексна мерења над стринговима (или другим структурама података). Пошто се много математичких објеката могу представити у облику стрингова, или као граница низа стрингова, она се може користити за изучавање великог броја математичких објеката, укључујући и целе бројеве.

Неформално, из перспективе алгоритамске информационе теорије, информациони садржај стринга је еквивалентан дужини најкомпресованије могуће самосадржавајуће репрезентације тог стринга. Таква репрезентација је у основи рачунарски програм – у неким фиксираним, али ипак ирелевантним универзалним програмским језицима – који, када су покренути, исписују оригиналан стринг.

Из ове тачке гледишта, енциклопедија од 3000 страна заправо садржи мање информација него 3000 страна насумичних слова, упркос чињеници да је енциклопедија много кориснија. То је зато што да би реконструисали целе секвенце насумичних слова, морамо знати које је свако слово. У другу руку, ако сваки самогласник избришемо из енциклопедије, неко са умереним знањем српског језика би је могао реконструисати, као што би неко могао реконструисати реченицу "Ов рчнц сдрж мл пдтк" из контекста и постојећих сугласника.

За разлику од класичне информационе теорије, алгоритамска информациона теорија нам даје логички систем, ригорозне дефиниције насумичног стринга и насумичног бесконачног низа које не зависе од физичке и филозофске интуиције о недетерминизму или вероватноћи. (Низ насумичних стрингова зависи од избора универзалне Тјурингове машине која се користи да дефинише Колгоморову комплексност, али сваки избор нам даје идентичне асимптотске резултате зато што Колмогорова комплексност стринга инваријантна до додајуће константе, зависећи само од избора универзалне Тјурингове машине. Због тога, низ насумичних бесконачних секвенца је независан од избора универзалне машине.)

Неки од резултата алгоритамске информационе теорије, као на пример Чејтинова теорема непотпуности, наизглед се противи математичким и филозофским интуицијама. Најистакнутија је конструкција Чејтинове константе Ω, реалан број који исказује вероватноћу да ће се самоограничавајућа универзална Тјурингова машина зауставити када је њен унос одређен поштеним бацањем новчића. Иако је број Ω лако дефинисан, у било којој доследној аксиоматској теорији могуће је само израчунати коначно много цифара броја Ω, тако да је у неком смислу непознат, пружајући апсолутну границу знања која подсећа на Геделове теореме о непотпуности. Иако се цифре броја Ω не могу одредити, многе особине су му познате; на пример, он је алгоритамски насумичан низ, стога су његове бинарне цифре једнако распоређене (заправо је нормалан број).

Историја

Алгоритамску информациону теорију је основао Реј Соломонов, који је издао основне идеје на којима је ова област заснована као део његовог проналаска алгоритамске вероватноће - начина да се превазиђу озбиљни проблеми повезани са применом Бејевих правилаs у статистици. Он је први пут описао своје резултате на конференцији у Калифорнијском технолошком институту 1960. године, and in a report, February 1960, "A Preliminary Report on a General Theory of Inductive Inference." Алгоритамска информациона теорија се касније развијала независно од стране Андреја Колмогорова, у 1965. и Грегорија Чејтина, око 1966.

Постоји пар варијација Колмогорове комплексности или алгоритамске информације; најкоришћенија је базирана на самоограничавајућим програмима због Леонида Левина (1974). Пер Мартин-Лоф је такође озбиљно допринео информационој теорији бесконачних секвенци. Аксиомски приступ алгоритамској информационој теорији базиран на Блумобим аксиомама (Блум 1967) је представљен од стране Марка Бургина у чланку који је поднет за објављивање од стране Андреја Колмогорова (Бургин 1982). Аксимоски приступ обухвата остале приступе у алгоритамској информационој теорији. Могуће је третирати различита мерења алгоритамске информације као специфичне случајеве аксиоматски дефинисаних мерења ње саме. Уместо доказивања сличних теорема, као што је основна теорема инваријантности, за свако одређено мерење, могуће је са лакоћом дедуковати све резулате из једне сличне теореме доказане аксиомским путем. Ово је предност аксиомског приступа у математици. Аксиомски приступ алгоритамској информационој теорији је детаљније развијен у књизи (Бургин 2005) примењен на софтверској метрици (Бургин и Дебнат, 2003; Дебнат и Бургин, 2003).

Прецизне дефиниције

Главни чланак: Колмогорова комплексност

Бинарни стринг је насумичан ако је Колмогорова комплексност стринга барем дужине тог стринга. Једноставно пребројавање показује да су неки стрингови, било које дужине, насумични и скоро су сви они веома близу да буду насумични. Пошто Колмогорова комплексност зависи од фиксираног избора универзалне Тјурингове машине (неформално, дефинисан "описни језик" за који су "описи" задати), колекција насумичних стрингова зависи од избора фиксиране универзалне машине. Колекција насумичних стрингова, у целини, има сличне особине независно од фиксиране машине, тако да можемо причати о особинама насумичних стрингова као о групи, а често то и радимо, без потребе да специфицирамо фиксирану машину.

Главни чланак: Алгоритамски насумични низови

Бесконачна бинарна секвенца је насумична ако за неку константу c, за свако n, Колмогорова комплексност иницијалног сегмента дужине n те секвенце је барем n − c. Може се показати да је скоро свака секвенца (из гледишта стандардног мерења — "поштеног бацања новчића" или Мера Лебега — у оквиру бинарних бесконачних секвенца) насумична. Такође, пошто се може показати да се Колмогорова комплексност, релативна двема универзалним машинама, разликује највише за константу, колекција насумичних бесконачних секвенци не зависи од избора универзалне машине (насупрот коначним стринговима). Ова дефиниција насумичности се обично назива Мартин-Лоф насумичност, по Пер Мартин-Лоф, тако да је разликујемо од осталих, сличних, нотација насумичности. Понекад је називамо и 1-насумичност да би је разликовали од осталих, јачих, нотација насумичности (2-насумичност, 3-насумичност, итд.). Поред Мартин-Лоф концепта насумичности постоје и рекурзивне насумичности, Шнор насумичност и Курц насумичност итд. Јонг Ванг је показао да сви ови концепти насумичности су различити.

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

Специфичне секвенце

Алгоритамска информациона теорија (АИТ) је информациона теорија индувидуалних објеката. Користи принципе информатике и бави се везама између израчунавања, информација и насумичности.

Информациони садржај или комплексност објекта може се мерити дужином његовог најкраћег описа. На пример, стринг:

"0101010101010101010101010101010101010101010101010101010101010101"

има кратак опис "32 понављања '01'", док

"1100100001100001110111101110110011111010010000100101011110010110"

вероватно нема једноставнијег описа од писања самог стринга.

Формалније, алгоритамска комплексност (АК) стринга x је дефинисана као дужина најмањег програма који израчунава или исписује x, где се програм покреће на неком фиксираном референцном универзалном компјутеру.

Блиско повезан појам је вероватноћа да универзални компјутер исписује неки стринг x уколико је преоптерећен насумично изабраним програмом. Ова алгоритамска "Соломонов" вероватноћа (АВ) је кључ при интерпретацији старог филозофског проблема индукције на формалан начин.

Лоше стране AК и AВ су њихове неизрачунљивости. Временски захтевна "Левин" комплексност кажњава спор програм додајући време трајања алгоритма његовој дужини. Ово доводи до израчунљивих варијанти AК и AВ, и универзална "Левин" претрага (УП) решава све инверзне проблеме у оптималном времену (изузев неких нереално великих мултипликативних константи).

АК и AВ омогућавају формалну и ригорозну дефиницију насумичности индувидуалних стрингова да не зависе од физичких и филозофских интуиција о недетерминизму или вероватноће. Угрубо, стринг је алгоритамски "Мартин-Лоф" насумичан (АН) ако не може да се компресује, у смислу да је његова алгоритамска комплексност једнака његовој дужини.

AК, AВ, и АН су кључне поддисциплине алгоритамске информационе теорије, али она се простире у много других области. Служи као темељ принципу минималне описне дужине (МОД), може да поједностави доказе у комплексној теорији израчунљивости, користи се да дефинише универзалну метрику сличности између објеката, решава проблем Максвеловог демона и много другог.

Види још

• Соломонова теорија индуктивног закључка
• Колмогорова комплексност
• Алгоритамски насумичан низ
• Алгоритамска вероватноћа
• Чејтинова константа
• Чејтин-Колмогорова насуимчност
• Рачунска неприметност
• Дистрибуцијски ансамбл
• Епистемологија
• Индукција (логика)
• Индуктивна вероватноћа
• Теорема инваријанте
• Минимална дужина описа
• Минимална дужина поруке
• Псеудонасумични ансамбл
• Псеудонасумични генератор
• Теорија једноставности

Литература

• Blum, M. (1967) On the Size of Machines, Information and Control, v. 11. стр. 257–265
• Blum M. (1967a) A Machine-independent Theory of Complexity of Recursive Functions, Journal of the ACM, v. 14, No.2. стр. 322–336
• Burgin, M. (1982) Generalized Kolmogorov complexity and duality in theory of computations, Soviet Math. Dokl., v.25, No. 3. стр. 19–23
• Burgin, M. (1990) Generalized Kolmogorov Complexity and other Dual Complexity Measures, Cybernetics, No. 4. стр. 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. стр. 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. стр. 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. стр. 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. стр. 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. стр. 3–11
• Kolmogorov, A.N. (1968) Logical basis for information theory and probability theory, IEEE Trans. Inform. Theory, vol. IT-14. стр. 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. стр. 206–210
• Levin, L.A. (1976) Various Measures of Complexity for Finite Objects (Axiomatic Description), Soviet Math. Dokl., v. 17. стр. 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. стр. 1–22; No.2. стр. 224–254
• Solomonoff, R.J. (2009). Emmert-Streib, F.; Dehmer, M., ур. 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. стр. 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. стр. 83–124

Спољашње везе

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