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.

Prinzip

Die Komplexität ist bis auf eine additive Konstante maschinenabhängig (Invarianzsatz) und im Allgemeinen nicht berechenbar; Folgen ohne kürzere Beschreibung als sie selbst gelten als algorithmisch zufällig.

Demonstration

Eine Folge aus 10.000 Wiederholungen von '01' hat geringe Kolmogorov-Komplexität, weil ein kurzes Programm das Muster erzeugen kann, während eine 10.000 lange Folge unabhängiger Münzwürfe wahrscheinlich eine Komplexität nahe 10.000 hat.

Fehlanwendung

Die Kolmogorov-Komplexität als berechenbare Metrik für praktische Kompression zu behandeln oder sie direkt mit der Shannon-Entropie einer Quelle gleichzusetzen, ohne Modell- und Maschinenabhängigkeit zu berücksichtigen.

Konsequenz

Bietet eine strenge Auffassung von Zufälligkeit und eine absolute untere Schranke für verlustfreie Kompression einzelner Objekte; bildet die Grundlage der algorithmischen Informationstheorie und der Grenzen der Inferenz mit endlichen Beschreibungen.

Umkehrung

Wird die Unsicherheit in probabilistische Begriffe (Shannon-Information) überführt, erhält man durchschnittliche, berechenbare Maße, die aus Verteilungen abgeleitet sind, im Gegensatz zur instanzzentrierten, nicht berechenbaren Kolmogorov-Maßzahl.

Abgrenzung

Gilt für endliche diskrete Objekte relativ zu einer gewählten universellen Maschine; sie ist im Allgemeinen nicht berechenbar, hängt von Programmkodierungs-Konventionen bis auf eine additive Konstante ab, und Varianten (prefix-, monotone Komplexität) modifizieren technische Details.

Semantische Spannung

Wird oft mit praktischen Kompressionsraten oder mit der Entropierate einer stochastischen Quelle verwechselt; die Spannung liegt zwischen instanzbasierter algorithmischer Unreduzierbarkeit und ensemblebasierten Durchschnittsinformationen.

Synthese

Die Kolmogorov-Komplexität quantifiziert die kürzeste algorithmische Beschreibungslänge eines einzelnen Objekts relativ zu einem universellen Berechnungsmodell und formalisiert Komprimierbarkeit und algorithmische Zufälligkeit trotz ihrer Nichtberechenbarkeit.