Komplexität und Entropie
- Sascha Delitzscher (TU Berlin)
Abstract
Ein zentrales Ergebnis der Komplexitätstheorie ist ein Theorem, das von A.A. Brudno 1983 zuerst bewiesen wurde. Es besagt, dass die Entropierate eines ergodischen Prozesses fast sicher gleich der Kolmogorov Komplexität pro Symbol seiner Trajektorien ist.
Betrachtet man einen aus zwei Systemen zusammengesetzten ergodischen Prozess, so lässt sich diese Aussage auf die zugehörigen bedingten Größen erweitern.
Der Vortrag stellt die beiden Theoreme vor und zeigt Wege auf, diese zu verallgemeinern: Es wird eine leicht modifizierte Version der bedingten Kolmogorov Komplexität vorgestellt. Bei dieser hat die unterliegende Rechenmaschine die Möglichkeit aus einer gegebenen Menge von Daten die zur Berechnung eines Objektes passendsten auszuwählen.
Desweiteren wird der Begriff der Komplexität eines klassischen Ensembles, d.h. eines klassischen physikalischen Systems in einer unbekannten Konfiguration, eingeführt. Dabei wird eine Variante, Ensembles als Ausgaben von Turing Maschinen zu 'berechnen', diskutiert und eine Formel zur Berechnung der Komplexität angegeben.
