Kolmogorov-Komplexität

Ein Maß für den algorithmischen Informationsgehalt eines endlichen Objekts, definiert als die Länge der kürzesten Beschreibung (Programm plus Eingabe) auf einer festen universellen Beschreibungsmaschine, die das Objekt erzeugt.

Die Länge (in Bits) der kürzesten effektiven Beschreibung bzw. des kürzesten Programms, das auf einer festen universellen Turing-Maschine eine gegebene endliche Zeichenfolge ausgibt, betrachtet bis auf eine additive Konstante abhängig von der Wahl der universellen Maschine.