Algorithmische Informationstheorie

Die algorithmische Informationstheorie ist eine Theorie aus der theoretischen Informatik, die im Gegensatz zur klassischen Informationstheorie die Kolmogorow-Komplexität zur Bestimmung des Informationsgehalts verwendet. Sie wurde im Wesentlichen von Gregory Chaitin, Andrey Kolmogorov und Ray Solomonoff entwickelt.

Zur Beschreibung des Informationsgehalts einer Zeichenkette betrachtet die algorithmische Informationstheorie die Größe eines kleinsten Algorithmus, der die Zeichenkette erzeugt. Gregory Chaitin präzisierte diese allgemein als Kolmogorow-Komplexität bekannte Größe durch ein spezielles Maschinenmodell, nach dem der Algorithmus ausführbar sein muss. Wie Chaitin beweisen konnte, lässt sich der algorithmische Informationsgehalt einer Zeichenkette nicht endgültig angeben, da nicht beweisbar ist, ob ein gegebenes Programm zu ihrer Erzeugung wirklich das kürzeste ist. Ebenso wie der Informationsbegriff nach Claude Shannon trifft die algorithmische Informationstheorie keinerlei Aussagen über Bedeutung, Wissen und ähnliche nicht mathematisch definierten Begriffe.

Beispiel

Gemäß der klassischen Definition nach Claude Shannon ist der Informationsgehalt der folgenden binären Folge gleich (gilt nur für Entropie erster Ordnung):

1000110111100101
1111111100000000

Während die erste Folge durch Münzwurf als Zufallsgenerator erzeugt wurde, kann die zweite Folge jedoch durch die Anweisung „8x1 dann 8x0“ verkürzt werden. Im Sinne der algorithmischen Informationstheorie hat die erste Folge deshalb mehr algorithmische Information, da sie viel schwieriger oder gar nicht verkürzt werden kann. Die algorithmische Information ist umso höher, je weniger eine Zeichenkette (unter Anderem durch Datenkompression) komprimiert werden kann. Zufällige Zahlenfolgen und weißes Rauschen enthalten in der Regel keine vorhersagbaren Muster und sind deshalb nicht komprimierbar – der algorithmische Informationsgehalt ist deshalb höher.

Mathematischer Hintergrund

Der Ansatz von Andrei Kolmogorow lässt als Algorithmen Programme für beliebige Turingmaschinen zu. Gregory Chaitin setzt die Kolmogorow-Komplexität zur Theorie rekursiver Funktionen (Siehe auch µ-Rekursion, Lambda-Kalkül) und dem Werk von Kurt Gödel in Beziehung. Er 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.

Nach dem Beweis von Chaitin kann allerdings nicht grundsätzlich festgestellt werden, ob eine Zeichenkette algorithmisch weiter verkürzt werden kann. So können beispielsweise neue und effektivere Kompressionsalgorithmen gefunden werden oder eine scheinbar zufällige Zahlenfolge kann von einem Pseudozufallszahlengenerator stammen. Wegen des Halteproblems können auch nicht alle Turingmaschinen, die kleiner als das Signal sind, in endlicher Zeit durchprobiert werden.

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmische Komplexität — Die Kolmogorow Komplexität (nach Andrei Nikolajewitsch Kolmogorow) ist ein Maß für die Strukturiertheit einer Zeichenkette und ist durch die Länge des kürzesten Programms gegeben, das diese Zeichenkette erzeugt. Dieses kürzeste Programm gibt… …   Deutsch Wikipedia

  • Informationstheorie — Die Informationstheorie ist eine mathematische Theorie aus dem Bereich der Wahrscheinlichkeitstheorie und Statistik, die auf Claude Shannon zurückgeht. Sie beschäftigt sich mit Begriffen wie Information, Entropie, Informationsübertragung,… …   Deutsch Wikipedia

  • Algorithmische Tiefe — Die Algorithmische oder Logische Tiefe ist ein Maß für die Komplexität einer Datenmenge oder Nachricht, also für den Informationsgehalt. Sie wurde von Charles Bennett definiert als der Aufwand, der betrieben werden muss, um die Daten zu erzeugen… …   Deutsch Wikipedia

  • Algorithmische Komposition — Als Algorithmische Komposition (AK) bezeichnet man jene Kompositionsverfahren, bei denen die Partitur durch einen automatischen, mathematisch beschreibbaren Prozess oder Algorithmus erzeugt wird. Im Prinzip lässt sich jedes Musikstück als eine… …   Deutsch Wikipedia

  • Entropie (Informationstheorie) — Entropie ist ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte eines Zeichensystems. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt. Das… …   Deutsch Wikipedia

  • Überraschungswert — Der Begriff der Information, wie er in der Informationstheorie nach Shannon[1] verwendet wird, ist streng von dem gewöhnlichen Gebrauch dieses Begriffes zu unterscheiden. Insbesondere darf darin die Information nicht mit dem Begriff der Bedeutung …   Deutsch Wikipedia

  • Informationstheoretiker — Die Artikel Informationstheorie, Shannon Index und Shannon (Einheit) überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese Überschneidungen. Bitte… …   Deutsch Wikipedia

  • Informationstheoretisch — Die Artikel Informationstheorie, Shannon Index und Shannon (Einheit) überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Beteilige dich dazu an der Diskussion über diese Überschneidungen. Bitte… …   Deutsch Wikipedia

  • Digitale Information — Das „i“ ist international ein Symbol für Information Information (lat. informare „bilden“, „eine Form geben“) ist ein in vielen Lebensbereichen verwendeter Begriff. Dazu gehören die Naturwissenschaften, die Technik und der Bereich des… …   Deutsch Wikipedia

  • Informationen — Das „i“ ist international ein Symbol für Information Information (lat. informare „bilden“, „eine Form geben“) ist ein in vielen Lebensbereichen verwendeter Begriff. Dazu gehören die Naturwissenschaften, die Technik und der Bereich des… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”