Grammar Complexity - Algorithmische Entropie

Die Grundbegriffe der algorithmischen Entropie beruhen auf Arbeiten zur algorithmischen Informationstheorie (Kolmogorov 1965, Zvonkin & Levin 1970, Chaitin 1974), die den Informationsgehalt einer Werteabfolge nach dem Informationsgehalt bemisst, der benötigt wird um die Werteabfolge zu beschreiben. In diesem Sinne ist die Wurzel aus zwei eine Zahl mit unendlich vielen Nachkommastellen, die zudem in einer extrem komplexen Abfolge auftreten. Trotz dieser augenscheinlichen Komplexität der Ziffernabfolgen kann diese durch einen einfachen Algorithmus ermittelt werden. Zur Beschreibung bzw. Erzeugung der Zahlenabfolge genügt also eine relativ einfache Formel.

Die algorithmische Informationstheorie bezieht sich auf diese Überlegungen, indem davon ausgegangen wird, dass zur Beschreibung bzw. Erzeugung bestimmter komplexer aber geordneter Strukturen die Kenntnis eines einfachen Algorithmus genügt. Es ist der Informationsgehalt dieses Algorithmus, der ausreichend ist, um eine, in der Regel weit komplexere, dynamische Ordnung zu generieren. Etwas vereinfachend ist die algorithmische Entropie einer Werteabfolge also gegeben durch die mindestens erforderliche Größe eines Algorithmus, der diese Abfolge erzeugen kann.

Auf ähnlichen Überlegungen beruhen Computerprogramme, die zur Komprimierung von Dateien benutzt werden. Eine komprimierte Datei ist im Wesentlichen eine Erzeugungsvorschrift für die Datei selbst. Gelingt die Komprimierung, so liegt ein Algorithmus vor, der viel weniger Speicherplatz einnimmt als die ursprüngliche Datei, aber alle Informationen enthält, um die Datei wieder zu erzeugen. Der Unterschied zwischen der Größe der komprimierten und der unkomprimierten Datei ist dabei ein Maß ihrer algorithmischen Entropie.

Berechnungsmöglichkeiten für die algorithmische Entropie ergeben sich also durch die Anwendung von Verfahren zur verlustfreien Komprimierung von Dateien. Ein solcher Komprimierungsalgorithmus ist z.B. die Grammar Complexity.

Die Software GChaos verfügt über eine umfassend geprüfte Implementierung der Grammar Complexity, die zudem über zahlreiche Optionen und zusätzliche Tools verfügt.

Eine ausführliche Darstellung der Methoden findet sich hier:

Handbuch mit Beispielanalysen und Bedienhinweisen.

Die Software lässt sich herunterladen unter: Download