Algoritmisk informationsteori er et felt inden for datalogi , der forsøger at fange essensen af kompleksitet ved hjælp af værktøjer fra teoretisk datalogi. Hovedideen er at definere kompleksiteten (eller beskrivende kompleksitet , Kolmogorov kompleksitet , Kolmogorov-Khaitin kompleksitet ) af en streng som længden af det korteste program, der udsender en given streng. Linjer, der kan udlæses af korte programmer, anses for ikke at være særlig komplekse. Denne notation er overraskende dyb og kan bruges til at fastslå og bevise umuligheden af visse resultater på samme måde som Gödels ufuldstændighedssætning og Turings hængeproblem gør .
Denne region blev udviklet af Kolmogorov , Ray Solomonoff og Gregory Khaitin slutningen af 1960'erne Der er flere varianter af Kolmogorov kompleksitet eller algoritmisk information. Den mest brugte er baseret på selvafgrænsende programmer og følger mest Leonid Levin (1974).
Minimum Message Length ( MLM princippet for statistisk og induktiv inferens og maskinlæring blev udviklet i 1968 af Wallace og DM Boulton MDS - Bayesiansk sandsynlighed (det inkluderer tidligere udtalelser) og informationsteoretisk. Det har de ønskede egenskaber for statistisk invarians (slutningstransformationer med reparametrisering, for eksempel på samme måde som konvertering fra polære koordinater til kartesiske koordinater udføres), statistisk konsistens (selv for meget komplekse problemer vil MDS konvergere til enhver underliggende model ), og effektivitet (MDS-modellen vil konvergere til enhver sand underliggende model så hurtigt som muligt). Christopher Wallace og D.L. Dowe viste en formel forbindelse mellem MDS og algoritmisk informationsteori (eller Kolmogorov-kompleksitet) i 1999 .