Wikipedia · einfach zusammengefasst · Stand
Algorithmische Informationstheorie
Gemäß der klassischen Definition nach Claude Shannon ist der Informationsgehalt der folgenden binären Folge gleich (gilt nur für Entropie erster Ordnung):.
Grundidee und Grenzen
Die algorithmische Informationstheorie ist ein Gebiet der theoretischen Informatik. Anders als die klassische Informationstheorie bestimmt sie den Informationsgehalt einer Zeichenkette mit ihrer Kolmogorow-Komplexität. Diese entspricht der Größe eines kleinsten Algorithmus, der die Zeichenkette erzeugt.
Gregory Chaitin präzisierte die Kolmogorow-Komplexität durch ein spezielles Maschinenmodell: Der Algorithmus muss ausführbar sein. Der algorithmische Informationsgehalt einer Zeichenkette lässt sich jedoch nicht endgültig angeben. Es ist nicht beweisbar, ob ein bestimmtes Programm, das die Zeichenkette erzeugt, wirklich das kürzeste ist. Wie der Informationsbegriff nach Claude Shannon macht die Theorie keine Aussagen über Bedeutung, Wissen oder ähnliche nicht mathematisch definierte Begriffe.
Komprimierbarkeit als Maß
Für die binären Folgen
1000110111100101
und
1111111100000000
ist der Informationsgehalt nach der klassischen Definition von Claude Shannon gleich; dies gilt nur für Entropie erster Ordnung. Die zweite Folge lässt sich aber durch die Anweisung „schreibe 8-mal 1 dann 8-mal 0“ verkürzt beschreiben. Die erste Folge wurde durch Münzwurf als Zufallsgenerator erzeugt.
Daher enthält die erste Folge im Sinn der algorithmischen Informationstheorie mehr algorithmische Information: Sie ist schwieriger oder möglicherweise gar nicht zu verkürzen. Je weniger sich eine Zeichenkette, etwa durch Datenkompression, komprimieren lässt, desto höher ist ihre algorithmische Information. Zufällige Zahlenfolgen und weißes Rauschen haben in der Regel keine vorhersagbaren Muster, sind deshalb nicht komprimierbar und besitzen einen höheren algorithmischen Informationsgehalt.
Mathematische Grundlage
Andrei Kolmogorows Ansatz erlaubt als Algorithmen Programme für beliebige Turingmaschinen. Chaitin stellt die Kolmogorow-Komplexität in Beziehung zur Theorie rekursiver Funktionen, zur µ-Rekursion, zum Lambda-Kalkül und zum Werk von Kurt Gödel. Dabei beschränkt er mögliche Programme auf solche, die auf einer speziellen Variante der universellen Turingmaschine (UTM) laufen: der selbst-limitierenden universellen Turingmaschine.
Nach einem Theorem von Chaitin kann grundsätzlich nicht festgestellt werden, ob eine Zeichenkette noch algorithmisch verkürzt werden kann. Neue, effektivere Kompressionsalgorithmen können gefunden werden; außerdem kann eine scheinbar zufällige Zahlenfolge von einem Pseudozufallszahlengenerator stammen. Wegen des Halteproblems lassen sich auch nicht alle Turingmaschinen, die kleiner als eine gegebene Zeichenfolge sind, in endlicher Zeit ausprobieren.