Az algoritmikus információelmélet az informatika olyan területe , amely az elméleti számítástechnika eszközeivel próbálja megragadni a komplexitás lényegét. A fő ötlet az, hogy egy karakterlánc összetettségét (vagy leíró összetettségét , Kolmogorov-bonyolultságát , Kolmogorov-Khaitin komplexitását ) a legrövidebb program hosszaként határozzuk meg, amely egy adott karakterláncot ad ki. A rövid programokkal kiírható sorok nem tekinthetők túl bonyolultnak. Ez a jelölés meglepően mély, és ugyanúgy használható bizonyos eredmények lehetetlenségének megállapítására és bizonyítására, mint Gödel hiányossági tétele és Turing függő problémája .
Ezt a régiót Kolmogorov , Ray Solomonoff és Gregory Khaitin fejlesztette ki 1960 -as évek végén A Kolmogorov-féle komplexitás vagy algoritmikus információ többféle változata létezik. A legszélesebb körben használt önhatároló programokon alapul, és leginkább Leonid Levint (1974) követi.
A statisztikai és induktív következtetésekhez és gépi tanuláshoz szükséges minimális üzenethossz (MLM Wallace és DM Boulton fejlesztette ki 1968 -ban MDS - Bayesi valószínűség (beleértve a korábbi véleményeket) és információelméleti. Rendelkezik a statisztikai invariancia kívánt tulajdonságaival (a következtetés például újraparametrizálással transzformálódik ugyanúgy, mint a polárkoordinátákból derékszögű koordinátákká), statisztikai konzisztencia (még nagyon összetett problémák esetén is az MDS bármely mögöttes modellhez konvergál. ), és a hatékonyság (az MDS-modell a lehető leggyorsabban konvergál minden valódi mögöttes modellhez). Christopher Wallace és D.L. Dowe formális kapcsolatot mutatott ki az MDS és az algoritmikus információelmélet (vagy Kolmogorov-komplexitás) között 1999 -ben .