Algoritmik axborot nazariyasi
Algoritmik axborot nazariyasi ― bu nazariy informatika vositalaridan foydalangan holda murakkablikning mohiyatini tushunishga harakat qiladigan informatika sohasidir. Asosiy gʻoya qatorning murakkabligini (yoki tavsiflovchi murakkabligi, Kolmogorov murakkabligi, Kolmogorov-Xaytin murakkabligi) berilgan qatorni chiqaradigan eng qisqa dastur uzunligi sifatida aniqlashdan iborat. Qisqa dasturlar orqali chiqarilishi mumkin boʻlgan qatorlar uncha murakkab sanalmaydi. Ushbu xulosa hayratlanarli darajada chuqurdir va Gyodelning toʻliqsizlik teoremasi va Tyuringning osilgan muammosi kabi ayrim natijalarning mumkin emasligini isbotlash va tashkil qilish uchun ishlatilishi mumkin. Bu soha 1960-yillarning oxirida Andrey Kolmogorov, Rey Solomonov va Gregori Xaytin tomonidan ishlab chiqilgan. Kolmogorov murakkabligi yoki algoritmik maʼlumotlarning bir nechta variantlari mavjuddir. Eng koʻp ishlatiladigani oʻz-oʻzini chegaralovchi dasturlarga asoslangan va asosan Leonid Levinga (1974) amal qiladi. Statistik va induktiv xulosalar hamda mashinalarni oʻrganish uchun minimal xabar uzunligi (MXU) tamoyili 1968-yilda Kristofer Uolles va D. M. Boulton tomonidan ishlab chiqilgan. MXU — Bayes ehtimolligi (u oldingi fikrlarni oʻz ichiga oladi) va axborot-nazariy. U statistik oʻzgarmaslikning zaruriy xususiyatlariga ega (xulosa qayta parametrlash bilan oʻzgartiriladi, masalan, qutb koordinatalaridan dekart koordinatalariga oʻtkazish kabi), statistik muvofiqlik (hatto juda murakkab muammolar uchun ham MXU har qanday asosiy modelga yaqinlashadi) va samaradorlik (MXU modeli iloji boricha tezroq har qanday yaqinroq haqiqiy model bilan toʻqnashadi). Kristofer Uolles va D. L. Dou 1999-yilda MXU va algoritmik axborot nazariyasi (yoki Kolmogorov murakkabligi) oʻrtasidagi formal aloqani koʻrsatdi.