Kolmogorow-Komplexität
Die Kolmogorow-Komplexität ist ein Maß für die Strukturiertheit einer Zeichenkette, und ist durch die Länge des kürzesten Computerprogrammes gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Computerprogramm gibt somit eine beste Komprimierung der Zeichenkette, ohne dass Information verlorengeht.
Wenn die Kolmogorow-Komplexität einer Zeichenkette mindestens so groß ist wie die Zeichenkette selber, dann bezeichnet man die Zeichenkette als unkomprimierbar, zufällig oder auch strukturlos. Je näher die Kolmogorow Komplexität an der Länge der Zeichenkette liegt, desto 'zufälliger' ist die Zeichenkette.
Das Prinzip der Kolmogorow-Komplexität wurde unabhängig im Jahre 1964 von R. J. Solomonoff, im Jahre 1965 von Andrej Kolmogorow und 1969 von Gregory Chaitin entwickelt, und hat Bezüge zur Shannonschen Informationstheorie.
Die Kolmogorow-Komplexität wird manchmal auch Algorithmische Komplexität oder Beschreibungskomplexität genannt, darf aber nicht mit der Komplexität von Algorithmen verwechselt werden.
Beispiel
Ein Beispiel zur Erzeugung einer Folge von 1000 Nullen mag die Kompression veranschaulichen: Die Zahl 1000 lässt sich (in Binärform) durch 10 Bit darstellen. Bei einem gegebenen (konstanten) Programm zum Ausdrucken einer Nullfolge kann man die Kolmogorow Komplexität einer Folge von n Nullen als "Konstante + log(n)" angeben.
Zufall oder Ordnung?
Es gibt allerdings (in diesem Sinne) auch nur scheinbar zufällige Zahlenfolgen. Beispielsweise gibt es ein kurzes Programm, welches die Dezimalentwicklung der Kreiszahl Pi in beliebiger Genauigkeit erzeugt. Damit ergibt sich ebenfalls eine Komplexität der Form "Konstante + log(n)", wobei n die Genauigkeit der Darstellung angibt.
Berechnung
In der Praxis ist eine Angabe der Kolmogorow-Komplexität für eine konkrete Zeichenkette oft schwierig; es gibt keine konstruktive Vorschrift zu ihrer Berechnung.
Anwendungen
Heute findet die Kolmogorow-Komplexität Anwendung in der Informatik, der Biologie und anderen Wissenschaften, die Strukturen oder Informationen betrachten.
Literatur
- Ming Li and Paul Vitanyi: An Introduction to Kolmogorov Complexity and Its Applications, Springer-Verlag, New York, (1993).