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.