Algoritminen informaatioteoria on tietojenkäsittelytieteen ala , joka yrittää vangita monimutkaisuuden olemuksen käyttämällä teoreettisen tietojenkäsittelytieteen työkaluja. Pääajatuksena on määritellä merkkijonon monimutkaisuus (tai kuvaileva monimutkaisuus , Kolmogorov-kompleksisuus , Kolmogorov-Khaitin -kompleksisuus ) lyhimmän ohjelman pituudeksi, joka tulostaa tietyn merkkijonon. Lyhyillä ohjelmilla tulostettavia rivejä ei pidetä kovin monimutkaisina. Tämä merkintätapa on yllättävän syvä ja sitä voidaan käyttää tiettyjen tulosten mahdottomuuden toteamiseen ja todistamiseen samalla tavalla kuin Gödelin epätäydellisyyslause ja Turingin riippuvuusongelma .
Tämän alueen kehittivät Kolmogorov , Ray Solomonoff ja Gregory Khaitin 1960 luvun lopulla Kolmogorovin monimutkaisuudesta tai algoritmisesta tiedosta on useita muunnelmia. Eniten käytetty perustuu itserajautuviin ohjelmiin ja seuraa enimmäkseen Leonid Leviniä (1974).
Wallace ja DM Boulton kehittivät vuonna 1968 MLM ( Minimum Message Length -periaatteen tilastolliseen ja induktiiviseen päättelyyn ja koneoppimiseen MDS - Bayesin todennäköisyys (sisältää aikaisemmat mielipiteet) ja informaatioteoreettinen. Sillä on halutut tilastollisen invarianssin ominaisuudet (päätelmä muuntuu esimerkiksi uudelleenparametrisoinnilla samalla tavalla kuin muunnetaan napakoordinaateista suorakulmaisiksi koordinaatteiksi), tilastollinen johdonmukaisuus (jopa erittäin monimutkaisissakin ongelmissa MDS konvergoi mihin tahansa taustalla olevaan malliin ) ja tehokkuus (MDS-malli konvergoi todelliseen taustamalliin mahdollisimman nopeasti). Christopher Wallace ja D.L. Dowe osoittivat muodollisen yhteyden MDS:n ja algoritmisen informaatioteorian (tai Kolmogorov-kompleksisuuden) välillä vuonna 1999 .