Teoria algoritmică a informației este un domeniu al informaticii care încearcă să surprindă esența complexității folosind instrumente din informatica teoretică. Ideea principală este de a defini complexitatea (sau complexitatea descriptivă , complexitatea Kolmogorov , complexitatea Kolmogorov-Khaitin ) a unui șir ca lungime a celui mai scurt program care scoate un șir dat. Liniile care pot fi iesite de programe scurte sunt considerate ca nu sunt foarte complexe. Această notație este surprinzător de profundă și poate fi folosită pentru a afirma și dovedi imposibilitatea anumitor rezultate în același mod ca teorema de incompletitudine a lui Gödel și problema suspendată a lui Turing .
Această regiune a fost dezvoltată de Kolmogorov , Ray Solomonoff și Gregory Khaitin la anilor 1960 Există mai multe variante ale complexității Kolmogorov sau ale informațiilor algoritmice. Cel mai utilizat este bazat pe programe de autodelimitare și urmează în mare parte Leonid Levin (1974).
Principiul lungimii minime a mesajului (MLM pentru inferența statistică și inductivă și învățarea automată a fost dezvoltat în 1968 de Wallace și DM Boulton MDS - Probabilitate bayesiană (include opiniile anterioare) și teoretică informațională. Are proprietățile dorite de invarianță statistică (transformări de inferență cu reparametrizare, de exemplu, în același mod în care se face conversia din coordonatele polare în coordonate carteziene), consistența statistică (chiar și pentru probleme foarte complexe, MDS-ul va converge către orice model de bază). ), și eficiență (modelul MDS va converge către orice model adevărat de bază cât mai repede posibil). Christopher Wallace și D.L. Dowe au arătat o legătură formală între MDS și teoria informației algoritmice (sau complexitatea Kolmogorov) în 1999 .