Algorithmische Informationstheorie
Die Algorithmische Informationstheorie (AIT) ist eine Methode zur Bestimmung des Informationsgehalts einer Nachricht, die von Gregory Chaitin entwickelt wurde. Im Gegensatz zur klassischen Informationstheorie nach Claude Shannon betrachtet sie aber, wie die Kolmogorow-Komplexität, die "Größe" des kleinsten Algorithmus' zur Erzeugung der Daten als Maß für den Informationsgehalt. Dabei wird der Ansatz Kolmogorows bezüglich des Maschinenmodells präzisiert und zur Theorie Rekursiver Funktionen (Siehe auch µ-Rekursion, Lambda-Kalkül) und dem Werk von Kurt Gödel in Beziehung gesetzt.
Die Grundidee ist, dass die Kolmogorow-Komplexität keine präzisen Aussagen liefert, weil sie Programme für beliebige Turingmaschinen zulässt. Chaitin beschränkt die möglichen Programme auf solche, die selbst wieder auf einer speziellen Variante der Universellen Turingmaschine (UTM) laufen, auf der so genannten selbst-limitierenden universellen Turingmaschine.
Chaitins Begriff der Information setzt im Gegensatz zu Shannons Informationstheorie eher bei der Komplexität und Vorhersagbarkeit an.
In welchen Ausmaß beinhaltet ein Signal Muster? Lassen sie sich durch ein Computerprogramm verkürzen?
Gemäß der klassischen Definition von Shannon ist der Informationsgehalt einer binären Folge:
1111111100000000 und der Folge
1000110111100101
genau gleich, obwohl die erste mit "8x1 dann 8x0" auf den ersten Blick erheblich verkürzt und übertragen werden kann. Nach Chaitins AIT hat die zweite Folge erheblich mehr algorithmische Information da sie viel schwieriger oder gar nicht verkürzt werden kann. Die erste Folge wurde mit dem oben erwähnten Pseudo-Programm erzeugt, die zweite stammt aus einen Kopf-oder-Zahl Zufallsgenerator.
Je weniger ein Signal komprimiert werden kann, desto mehr Information enthält es. Beispielsweise ist ein fast ganz dunkles JPEG-Bild auf dem Speichermedium viel kleiner als ein Bild mit vielen Details. Bemerkenswerterweise ist ein Video von weissem Rauschen (TV ohne Empfang) größer als ein Hochzeitsvideo mit den gleichen Kompressionsparametern. Das kommt daher weil Bilder mit blauen Himmel viele Wiederholungen gleicher und ähnlicher Pixel enthalten, die sich besser komprimieren lassen als total unvorhersagbares Rauschen. Die Methode der Kompression sucht Muster, um das gleiche Signal kürzer zu beschreiben. Komplett zufällige Zahlenfolgen wie Weißes Rauschen enthalten keine Muster, dafür aber das meiste an Information. Das ergibt insofern Sinn: Wenn jedes nächste Bit maximal unvorhersagbar ist lernt man mit jedem weiteren Stückchen Information mehr als vorher. Dagegen ist es bei dem oberen Beispiel keine große Überraschung, wenn nach 1111111100000 eine weitere 0 folgt. Versuchen Sie mal ein komprimiertes JPEG-Bild (von einer weißen Fläche beispielsweise) in binärer Darstellung zu öffnen und dann das selbe Bild als Bitmap abgespeichert. Die JPEG-Version ist komprimiert und das nächste Bit ist kaum zu erraten.
Man kann die Menge der algorithmischen Information in einer Nachricht abschätzen, aber niemals berechnen. Das hat Gregory Chaitin mathematisch bewiesen. Veranschaulicht bedeutet das: man kann sagen, dass ein einfaches oder bekanntes Muster eine Nachricht zur Übermittlung algorithmisch verkürzen kann. Aber man weiß nicht, ob es eine neuartige Methode wie fraktale Kompression gibt, die scheinbar zufällige Signale nicht erheblich verkürzen kann.
Information und Bedeutung
Information und Bedeutung sind 2 grundsätzlich verschiedene Konzepte.
"Das also war des Pudels Kern!" aus Faust enthält dieselbe Shannonsche Information wie diese Zeichenkette: "t3R§5IahXgwWJyMjw%140L?8sAu/" (Passwortgenerator). Goethes Zitat hat auch weniger Chaitin'sche Information als der Zufallstext, ist aber natürlich bedeutender als irgendein Text, den ein Affe auf der Schreibmaschine tippen könnte (auch wenn es 10.000 Affen sind). Wissenschaftler konnten die Bedeutung von Nachrichten bisher noch nicht in mathematischen Formeln ausdrücken. Googles PageRank Methoden sind aber auf dem besten Weg dazu. Die dazugehörige Wissenschaft heißt Information Retrieval (en:Information Retrieval).
Siehe auch
Weblinks
- How to Run Algorithmic Information Theory on a Computer von Gregory Chaitin (englisch)
- The Limits of Mathematics von Gregory Chaitin, inklusive eines Interpreters für ein erweitertes LISP zur Simulation von selbst-limitierenden UTMs (englisch)
- Komprimierte Nachrichten von Aliens mit Rauschen identisch