Algoritmisk informationsteori är ett område inom datavetenskap som försöker fånga essensen av komplexitet med hjälp av verktyg från teoretisk datavetenskap. Huvudidén är att definiera komplexiteten (eller beskrivande komplexitet , Kolmogorov-komplexitet , Kolmogorov-Khaitin-komplexitet ) för en sträng som längden på det kortaste programmet som matar ut en given sträng. Rader som kan matas ut av korta program anses inte vara särskilt komplexa. Denna notation är förvånansvärt djup och kan användas för att konstatera och bevisa omöjligheten av vissa resultat på samma sätt som Gödels ofullständighetsteorem och Turings hängningsproblem gör .
Denna region utvecklades av Kolmogorov , Ray Solomonoff och Gregory Khaitin slutet av 1960 -talet Det finns flera varianter av Kolmogorovs komplexitet eller algoritmisk information. Den mest använda är baserad på självavgränsande program och följer mestadels Leonid Levin (1974).
Minimum Message Length -principen (MLM för statistisk och induktiv slutledning och maskininlärning utvecklades 1968 av Christopher och DM Boulton MDS - Bayesisk sannolikhet (det inkluderar tidigare åsikter) och informationsteoretisk. Den har de önskade egenskaperna för statistisk invarians (inferenstransformeras med omparametrisering, till exempel på samma sätt som konvertering från polära koordinater till kartesiska koordinater görs), statistisk konsistens (även för mycket komplexa problem kommer MDS att konvergera till vilken underliggande modell som helst ), och effektivitet (MDS-modellen kommer att konvergera till vilken verklig underliggande modell som helst så snabbt som möjligt). Christopher Wallace och D.L. Dowe visade ett formellt samband mellan MDS och algoritmisk informationsteori (eller Kolmogorov-komplexitet) 1999 .