Definition
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.
Prinzip
Prinzip
Die Komplexität einer einzelnen endlichen Zeichenfolge ist die minimale Länge, bis auf eine additive Konstante abhängig von der gewählten universellen Maschine, eines Programms, das jene Folge ausgibt und terminiert.
Demonstration
Demonstration
Eine periodische Binärfolge wie '010101...0101' hat geringe Kolmogorov-Komplexität, weil ein kurzes Programm die Wiederholung erzeugen kann, während eine lange Folge durch faire Münzwürfe typischerweise nahezu maximale Komplexität besitzt.
Fehlanwendung
Fehlanwendung
Die Größe für beliebige Eingaben als berechenbar zu behandeln oder rohe Werte über verschiedene nicht spezifizierte universelle Maschinen hinweg ohne Berücksichtigung additiver Konstanten zu vergleichen, führt zu ungültigen Schlüssen.
Konsequenz
Konsequenz
Lieferte eine formale Grundlage für individuelle Zufälligkeit, Untergrenzen der Nichtkomprimierbarkeit und theoretische Grenzen für algorithmische Datenkompression und Inferenz.
Umkehrung
Umkehrung
Der Wechsel zu mengenbasierten Maßen (etwa durchschnittlicher Information einer Verteilung) kehrt den Fokus um: von der beschreibenden Minimalität eines einzelnen Objekts zur statistischen Unsicherheit über Stichproben hinweg.
Abgrenzung
Abgrenzung
Definiert für endliche diskrete Objekte relativ zu einer Wahl einer universellen Beschreibungsmethode; im Allgemeinen nicht berechenbar und abhängig von einer Invarianz bis zu einer maschinenabhängigen additiven Konstante.
Semantische Spannung
Semantische Spannung
Steht im Gegensatz zur Shannon-Information, die die durchschnittliche Unsicherheit einer stochastischen Quelle quantifiziert; die Kolmogorov-Komplexität bemisst die Beschreibungslänge eines Individuums unabhängig von probabilistischen Ensembles.
Synthese
Synthese
Die Kolmogorov-Komplexität formalisiert die kürzeste effektive Beschreibungslänge eines konkreten Objekts relativ zu einem universellen Beschreibungsschema und begründet algorithmische Zufälligkeit und Kompressibilität als Eigenschaften einzelner Instanzen.