## [Kolmogorov-Komplexität](/de/node/57654) 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 Beschreibungs­länge eines Individuums unabhängig von probabilistischen Ensembles. ## Synthese Synthese Die Kolmogorov-Komplexität formalisiert die kürzeste effektive Beschreibungs­länge eines konkreten Objekts relativ zu einem universellen Beschreibungs­schema und begründet algorithmische Zufälligkeit und Kompressibilität als Eigenschaften einzelner Instanzen.