ein Maß für den Informationsgehalt einer endlichen Zeichenfolge.

Für eine Programmiersprache U, z. B. beschrieben als universelle Turing-Maschine, ist der Informationsgehalt oder die Kolmogorow-Komplexität C_U(b) einer Zeichenfolge b definiert als die Bitlänge des kürzesten Programms, das ohne weitere Eingabe die Zeichenfolge b als Ausgabe erzeugt. Für zwei universelle Turing-Maschinen U und U′ (oder allgemeiner für zwei Programmiersprachen) unterscheiden sich C_U(b) und C_U′(b) für alle b maximal um eine additive Konstante. Somit ist der Begriff der Kolmogorow-Komplexität von b im wesentlichen von den verwendeten Modellierungsmitteln unabhängig. Für eine Bitfolge b der Länge n hat das Programm „schreibe b“ eine Bitlänge von n + O(1), die Kolmogorow-Komplexität jeder Bitfolge ist also nach oben bis auf eine additive Konstante durch n beschränkt. Für jede Programmiersprache hat ein Anteil von mindestens 1 − 2^−c aller Bitfolgen der Länge n eine Kolmogorow-Komplexität von mindestens n − c. Die meisten Bitfolgen sind also (bis auf additive Konstante) nicht verkürzbar (incompressible). Bei Betrachtung der Ziffernfolgen \begin{eqnarray}\begin{array}{c}01234567890123456789\\ 31415926535897932384\\ 90836252125511481515\end{array}\end{eqnarray} folgt unmittelbar, daß die erste Folge einen geringen Informationsgehalt hat, während die anderen beiden zufällig aussehen. Die zweite Folge besteht aus den ersten 20 Ziffern der Dezimaldarstellung von π, und ein Programm zur Berechnung der ersten n Ziffern von π kommt mit logarithmischer Länge aus. Diese wird im wesentlichen benötigt, um n darzustellen. Die dritte Folge wurde ausgewürfelt.

Anwendungsgebiete der Theorie der Kolmogorow-Komplexität sind z. B. die algorithmische Lerntheorie, die Theorie Formaler Sprachen, die Komplexitätstheorie (untere Schranken für die worst case-Rechenzeit von Turing-Maschinen), die Abschätzung der average case-Rechenzeit von Algorithmen und sogar die Statistische Mechanik.

[1] Li, M.; Vitányi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag New York, 1993.