algoritmikus komplexitás

A Kolmogorov-komplexitás vagy algoritmikus komplexitás formális definíciót ad az Ockham borotvája elvben használt egyszerűségnek. Hogy elkerülhessék azt, hogy az egyszerűség függ az információ reprezentációjától, azt javasolták, hogy az egyszerűségnek nevezzék annak a programnak a hosszát amely a legrövidebb és egy általános Turing-gépen helyesen adja vissza a megfigyelt adatokat. Mivel több fajta általános Turing-gépet lehet létrehozni, így több legrövidebb programot is létrejöhet, ám ezek hossza csak legfeljebb egy konstansban tér el, mely független az adatok mennyiségétől. Ezt a felfedezést csak az rondítja el, hogy a legrövidebb program hosszának kiszámítása csak közelítőleg lehetséges.