Algoritmická teorie informace je obor informatiky , který se snaží zachytit podstatu složitosti pomocí nástrojů teoretické informatiky. Hlavní myšlenkou je definovat složitost (nebo deskriptivní složitost , Kolmogorovova složitost , Kolmogorov-Khaitinova složitost ) řetězce jako délku nejkratšího programu, který daný řetězec vydává. Řádky, které lze vytisknout krátkými programy, nejsou považovány za příliš složité. Tato notace je překvapivě hluboká a lze ji použít ke konstatování a dokazování nemožnosti určitých výsledků stejným způsobem jako Gödelův teorém o neúplnosti a Turingův problém zavěšení .
Tato oblast byla vyvinuta Kolmogorov , Ray Solomonoff a Gregory Khaitin konci 60. let 20. století Existuje několik variant Kolmogorovovy složitosti nebo algoritmických informací. Nejpoužívanější je založen na samovymezovacích programech a většinou navazuje na Leonida Levina (1974).
Princip minimální délky zprávy (MLM pro statistické a induktivní vyvozování a strojové učení vyvinuli v roce 1968 Wallace a DM Boulton MDS - Bayesovská pravděpodobnost (zahrnuje předchozí názory) a informačně-teoretická. Má požadované vlastnosti statistické invariance (odvozování transformuje s reparametrizací, například stejným způsobem, jako se provádí převod z polárních souřadnic na kartézské souřadnice), statistickou konzistenci (i u velmi složitých problémů bude MDS konvergovat k jakémukoli základnímu modelu ) a účinnost (model MDS se bude co nejrychleji sbližovat s jakýmkoli skutečným základním modelem). Christopher Wallace a D.L. Dowe ukázali formální spojení mezi MDS a algoritmickou informační teorií (nebo Kolmogorovovou složitostí) v roce 1999 .