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.

Prinzip

Die minimale Beschreibungs­länge auf einer universellen Referenzmaschine als objektive Messgröße des algorithmischen Informationsgehalts und der Zufälligkeit eines einzelnen endlichen Objekts verwenden.

Demonstration

Für die Binärfolge S = '0101010101' existiert ein kurzes Programm, das das wiederkehrende Muster ausgibt und damit geringe Kolmogorov-Komplexität hat; für eine Folge R aus fairen Münzwürfen ohne kurzes Muster sind Programme, die R erzeugen, ungefähr so lang wie R selbst. Kolmogorov-Komplexität ist im Allgemeinen nicht berechenbar, daher lassen sich nur obere Schranken durch konkrete Programme angeben.

Fehlanwendung

Kolmogorov-Komplexität als für beliebige Zeichenfolgen berechenbar anzunehmen oder sie unmittelbar mit Shannon-Entropie zu identifizieren, ohne zu berücksichtigen, dass Kolmogorov-Komplexität eine Eigenschaft einzelner Objekte ist und nur bis auf additive Konstanten von der universellen Maschine abhängt.

Konsequenz

Bei korrekter Anwendung liefert sie eine (bis auf eine Konstante) invariante Klassifikation von Zeichenfolgen nach Komprimierbarkeit, formt eine formale Zufallsdefinition für Einzelobjekte und erklärt Grenzen algorithmischer Kompression sowie das Vorhandensein inkompressibler Zeichenfolgen.

Umkehrung

Wendet man das Gegenteil an und betrachtet maximale Beschreibungs­längen statt minimaler, rückt die Inkompressibilität in den Vordergrund: die meisten Zeichenfolgen einer gegebenen Länge haben Kolmogorov-Komplexität nahe dieser Länge, sodass die invertierte Sicht die Typicalität statt der Komprimierbarkeit betont.

Abgrenzung

Gilt für endliche Zeichenfolgen relativ zu einer festen universellen Turing-Maschine; die Größe ist nur bis auf additive Konstanten definiert, im Allgemeinen nicht berechenbar und quantifiziert nicht direkt durchschnittliche oder distributionsbezogene Information ohne zusätzliches probabilistisches Modell.

Semantische Spannung

Spannung besteht zwischen Kolmogorov-Komplexität (Eigenschaft einzelner Objekte, nicht berechenbar, maschinenabhängig bis auf Konstanten) und Shannon-Entropie (statistische, berechenbare Messgröße einer Zufallsvariable); sie können in stochastischen Grenzfällen übereinstimmen, haben aber unterschiedliche Rollen.

Synthese

Kolmogorov-Komplexität vereinigt algorithmische Beschreibungs­länge und eine formale Zufallsbegriffsbildung, indem sie die Länge des kürzesten Programms auf einer festen universellen Maschine als kanonische Messgröße für die Informationsmenge einer einzelnen endlichen Zeichenfolge nimmt, unter Anerkennung der Maschinenabhängigkeit und Nichtberechenbarkeit.