User:Slobodanobradovic1995/sandbox

This is the user sandbox of Slobodanobradovic1995. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here. Other sandboxes: Main sandbox | Template sandbox Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Wikipedia? Submit your draft for review!

Алгоритамска информациона теорија је подпоље Теорија информације и информатике која се бави везом између израчунљивости и Информација. Према Gregory Chaitin, она је "резултат сипања Shannon's информационе теорије и Turing теорије израчунљивости у коктел и њиховог мешања."^[1]

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

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

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

За разлику од класичне информационе теорије, алгоритамска информациона теорија нам даје formal, rigorous дефиниције random string и random infinite sequence које не зависе од физичке и филозофске интуиције о nondeterminism или likelihood. (Низ насумичних стригова зависи од избора universal Turing machine која се користи да дефинише Kolmogorov complexity, али сваки избор нам даје идентичне асимптотске резултате зато што Kolmogorov complexity стринга инваријантна до додајуће константе, зависећи само од избора универзалне Тјурингове машине. Због тога,низ насумичних бесконачних секвенца је независан од избора универзалне машине.)

Неки од резултата алгоритамске информационе теорије, као на пример Chaitin's incompleteness theorem, наизглед се противи математичким и филозофским интуицијама. Најистакнутија је конструкција Chaitin's constant Ω, реалан број који исказује вероватноћу да самоограничавајућа универзална Тјурингова машина ће се зауставити када је њен унос одређен фер бацањем новчића. Иако је број Ω лако дефинисан, in any consistent axiomatizable theory могуће је само израчунати коначно много цифара броја Ω, тако да је у неком смислу непознат, пружајући апсолутну границу знања која подсећа наGödel's Incompleteness Theorem. Иако се цифре броја Ω не могу одредити, многе особине су му познате; на пример, он је algorithmically random sequence стога његове бинарне цифре су једнако распоређене (заправо је normal).

Алгоритамску информациону теорију је основао Ray Solomonoff,^[2] који је издао основне идеје на којима је ова област заснована као део његовог проналаска algorithmic probability - начина да се превазиђу озбиљни проблеми повезани са применом Bayes' rules у статистици. Он је први пут описао своје резултате на конференцији у Caltech 1960. године,^[3] and in a report, February 1960, "A Preliminary Report on a General Theory of Inductive Inference."^[4] Алгоритамска информациона теорија се касније развијала независно од стране Andrey Kolmogorov, у 1965 и Gregory Chaitin, око 1966.

Постоји пар варијација Колмогорове комплексности или алгоритамске информације; Најкоришћенија је базирана на self-delimiting programs због Leonid Levin (1974). Per Martin-Löf је такође озбиљно допринео информационој теорији бесконачних секвенци. Аксиомски приступ алгоритамској информационој теорији базиран на Blum axioms (Blum 1967) је представљен од стране Mark Burgin in a paper presented for publication by Andrey Kolmogorov (Burgin 1982). Аксимоски приступ обухвата остале приступе у алгоритамској информационој теорији. Могуће је третирати различита мерења алгоритамске информације као специфичне случајеве аксиоматски дефинисаних мерења ње саме. Уместо доказивања сличних теорема, као што је основна теорема инваријантности, за свако одређено мерење, могуће је са лакоћом дедуковати све резулате из једне сличне теореме доказане аксиомским путем. Ово је предност аксиомског приступа у математици . Аксиомски приступ алгоритамској информационој теорији је детаљније развијен у књизи (Burgin 2005) примењен на софтверској метрици(Burgin and Debnath, 2003; Debnath and Burgin, 2003).

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

Бесконачна бинарна секвенца је насумична ако, за неку константу c, за свако n, Kolmogorov complexity иницијалног сегмента дужине n те секвенце је барем n − c. Може се показати да скоро свака секвенца (из гледишта стандардног measure — "фер бацања новчића" или Lebesgue measure — у оквиру бинарних бесконачних секвенца) је насумична. Такође, пошто се може показати да Колмогорова комплексност, релативна двема универзалним машинама, разликује се највише за константу, колекција насумичних бесконачних секвенци не зависи од избора универзалне машине (насупрот коначним стринговима). Ова дефиниција насумичности се обично назива Martin-Löf насумичност, по Per Martin-Löf, тако да је разликујемо од осталих, сличних, нотација насумичности.Понекад је називамо и 1-насумичност да би је разликовали од осталих, јачих, нотација насумичности(2-насумичност, 3-насумичност, итд.). Поред Мартин-Лоф концепта насумичности постоје и рекурзивне насумичности, Schnorr насумичност и Kurtz насумичност итд. Yongge Wang је показао ^[5] да сви ови концепти насумичности су различити.

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

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

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

"0101010101010101010101010101010101010101010101010101010101010101"

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

"1100100001100001110111101110110011111010010000100101011110010110"

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

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

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

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

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

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

• Solomonoff's theory of inductive inference
• Kolmogorov complexity
• Algorithmically random sequence
• Algorithmic probability
• Chaitin's constant
• Chaitin–Kolmogorov randomness
• Computationally indistinguishable
• Distribution ensemble
• Epistemology
• Inductive inference
• Inductive probability
• Invariance theorem
• Limits of knowledge
• Minimum description length
• Minimum message length
• Pseudorandom ensemble
• Pseudorandom generator
• Simplicity theory
• Uniform ensemble

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (June 2010) (Learn how and when to remove this message)

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

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

Category:Information theory Category:Randomness