Algorithmische Informationstheorie -
Kolmogoroffkomplexität

Die algorithmische Informationstheorie ist ein kleiner und wenig bekannter Zweig der Informatik. Heute wird er im wesentlichen als Teilgebiet der Komplexitätstheorie behandelt. Entstanden ist dieses Gebiet in den sechziger Jahren durch drei voneinander unabhängige Arbeiten, die kurz hintereinander veröffentlicht wurden. Alle drei Arbeiten befaßten sich mit dem Problem der kürzestmöglichen Beschreibung einer gegebenen Zeichenkette. Die drei Autoren waren R. J. Solomonoff, A. N. Kolmogoroff und G. J. Chaitin. Solomonoff war ein Schüler Carnaps, der sich im Rahmen des Induktionsproblems damit beschäftigte, wie Beobachtungsdaten möglichst kompakt dargestellt werden können und dadurch zu induktiven Schlüssen führen. Seine Untersuchungen sind in seinem Artikel A Formal Theory of Inductive Inference 1964 Solomonoff[Sol64] erschienen. Der zweite Autor - der russische Mathematiker A.N. Kolmogoroff führte derartige Betrachtungen in seiner Arbeit Three Approaches to the Quantitative Definition of Information 1965 Kolmogoroff[Kol65] ein. Nach ihm wird heute auch die Länge der kürzesten Beschreibung einer Zeichenkette Z als die Kolmogoroffkomplexität von Z, K(Z)bezeichnet. Chaitins Arbeit On the Length of Programs for Computing Finite Binary Strings Chaitin[Cha66] wurde 1966 veröffentlicht.

Die minimale Länge der Beschreibung einer Zeichenkette kann von dem jeweiligen Aufbau der betrachteten universellen Turingmaschine abhängen. Daher sollen für weitere Betrachtungen die folgenden Dinge wie folgt festgelegt werden.

• Es werden nur binäre endliche oder unendliche Zeichenketten betrachtet. Dies gilt sowohl für Zeichenketten, die beschrieben werden sollen, wie für beschreibende Zeichenketten. Die beschreibenden Zeichenketten - also die jeweiligen Eingaben für eine universelle Turingmaschine U - werden auch als Programm bezeichnet.

• Es werden nur universelle Turingmaschinen betrachtet, deren vollständige Turingmaschinentabelle nicht mehr als 1000 Zeilen enthält.^4.15
• Das kürzeste Programm für eine universelle Turingmaschine U, um eine Zeichenkette Z zu konstruieren, wird im folgenden auch als Kolmogoroffkomplexität von Z, kurz K(Z) bezeichnet.

Ein grundlegendes Theorem der algorithmischen Informationstheorie ist das sogenannte Invariance Theorem welches besagt, daß der besondere Aufbau der betrachteten universellen Turingmaschine U lediglich einen Unterschied in der Kolmogoroffkomplexität einer Zeichenkette Z von einer Konstanten c ausmacht. Dies läßt sich einsehen, indem man sich überlegt, daß auf jeder universellen Turingmaschine U jede andere universelle Turingmaschine U' durch ein Programm von fester Länge c simuliert werden kann. Mithin ist c als eine kleine Zahl anzunehmen, wenn man von überschaubaren Varianten einer universellen Turingmaschine ausgeht (ihre Beschreibung darf nicht zu lang werden). Das Invariance Theorem ist geradezu Voraussetzung für die algorithmische Informationstheorie, da ansonsten alle Aussagen stets auf eine spezifische universelle Turingmaschine bezogen werden müßten. Im Gegensatz dazu kann man aufgrund des Invariance Theorems von der Komplexität sprechen, die den Zeichenketten inhärent ist und nicht von einem Interpretationsmechanismus abhängt.

Das Invariance Theorem ist die theoretische Grundlage dafür, daß man von der Komplexität von Zeichenketten in einem gewissen absoluten Sinn sprechen kann.

Diese Tatsache der absoluten Komplexität von Zeichenketten, das heißt, der Unmöglichkeit Zeichenketten unter eine bestimmte Mindestlänge zu komprimieren - sie nicht kürzer beschreiben zu können, soll Gegenstand der nachfolgenden Kapitel sein.