b'\n_START_ARTICLE_\nKolmogorovkomplexitet\n_START_PARAGRAPH_\nKolmogorovkomplexiteten av ett objekt, s\xc3\xa5som en textstr\xc3\xa4ng, \xc3\xa4r ett m\xc3\xa5tt p\xc3\xa5 ber\xc3\xa4kningsresurserna som kr\xc3\xa4vs f\xc3\xb6r att specificera objektet eller med andra ord ett m\xc3\xa5tt p\xc3\xa5 hur kaotiskt objektet \xc3\xa4r. Det tillh\xc3\xb6r omr\xc3\xa5det algoritmisk informationsteori och \xc3\xa4r d\xc3\xb6pt efter Andrej Kolmogorov, som publicerade artiklar under 60-talet om \xc3\xa4mnet ._NEWLINE_Vi betraktar f\xc3\xb6ljande tv\xc3\xa5 str\xc3\xa4ngar:_NEWLINE_101010101010101010101010101010101010101010111000110100011111100001001010001001010000_NEWLINE_Det \xc3\xa4r l\xc3\xa4tt att se vilken av dessa som \xc3\xa4r mer kaotisk. Den f\xc3\xb6rsta str\xc3\xa4ngen kan kort beskrivas som "10" skrivet 21 g\xc3\xa5nger. Den andra str\xc3\xa4ngen blir d\xc3\xa4remot sv\xc3\xa5rare att beskriva och har d\xc3\xa4rmed h\xc3\xb6gre Kolmogorovkomplexitet \xc3\xa4n den f\xc3\xb6rsta. Som det formellt beskrivs nedan, m\xc3\xa4ter Kolmogorovkomplexiteten den minsta m\xc3\xa4ngden resurser som beh\xc3\xb6vs f\xc3\xb6r att beskriva ett objekt. Men komplexiteten kan inte ber\xc3\xa4knas utan endast approximeras uppifr\xc3\xa5n.\n_START_SECTION_\nKolmogorovslump\n_START_PARAGRAPH_\nSats: F\xc3\xb6r alla n finns det n\xc3\xa5got x med |x| = n s\xc3\xa5 att . Detta x kallar vi f\xc3\xb6r kolmogorovslump._NEWLINE_Bevis: Antag motsatsen. D\xc3\xa5 \xc3\xa4r  f\xc3\xb6r alla x. Allts\xc3\xa5 m\xc3\xa5ste det existera ett program p\xe2\x82\x93,  och . Om  \xc3\xa4r ej heller . _NEWLINE_Men det finns  program med kortare l\xc3\xa4ngd \xc3\xa4n n, och  str\xc3\xa4ngar av l\xc3\xa4ngden n. Om alla str\xc3\xa4ngar av l\xc3\xa4ngd n har ett program som \xc3\xa4r kortare \xc3\xa4n n, m\xc3\xa5ste det finnas ett program som producerar tv\xc3\xa5 str\xc3\xa4ngar. Uppenbarligen \xc3\xa4r det om\xc3\xb6jligt och d\xc3\xa4rav m\xc3\xa5ste det finnas minst en str\xc3\xa4ng av l\xc3\xa4ngd n som har ett program av minst l\xc3\xa4ngden n.\n_START_SECTION_\nHistorik\n_START_PARAGRAPH_\nKolmogorovkomplexitet gjordes k\xc3\xa4nd av matematikern Andrej Kolmogorov, men definierades tidigare av Raymond J. Solomonoff som en del i hans arbete kring algoritmisk informationsteori  och matematisk induktion och \xc3\xa4ven senare av Gregory J. Chaitin, som formulerade en rigor\xc3\xb6s definition i den artikel han publicerade 1969. Motivationen till Kolmogorovs arbete var informationsteoretisk och inriktad p\xc3\xa5 slump/kaos medan Solomonoff var motiverat av matematisk induktion.\n_START_SECTION_\nParalleller till entropi\n_START_PARAGRAPH_\nI somliga fall kallas teorin f\xc3\xb6r algoritmisk entropi. Detta h\xc3\xa4rr\xc3\xb6r fr\xc3\xa5n att entropi i ett system \xc3\xa4r ett m\xc3\xa5tt p\xc3\xa5 systemets kaos. Inom informationsteori refererar entropi vanligast till Shannons entropi som delar flertalet egenskaper med Kolmogorov komplexitet.'