Kolmogorov-Komplexität (Algorithmische Komplexität)

Natural & Formal Sciences Dictionary
Für eine endliche Binärfolge ist die Kolmogorov-Komplexität die Länge (in Bits) des kürzesten Programms auf einer festen universellen Turing-Maschine, das diese Folge ausgibt und anhält; sie formalisiert algorithmische Komprimierbarkeit.