Anwendungen und Entwicklungen der Kolmogoroffkomplexität

Die Anwendungen des Begriffs der Kolmogoroffkomplexität liegen primär in den folgenden Gebieten:

• Anwendung der möglichen Komprimierung von Zeichenketten: Zu den berühmtesten Anwendungen gehört sicherlich Chaitins Version des Beweises des Gödelschen Unvollständigkeitstheorems in Chaitin Chaitin[Cha74].   Eine andere Anwendung der Komprimierungsbetrachtungen ist das induktive Schließen. Dort wird versucht, eine möglichst kurze Beschreibung für die gegebenen empirischen Daten zu finden. Siehe beispielsweise Solomonoff Solomonoff[Sol64], Freivalds & Kinber FreivaldsKinber[FK77] oder Li & Vitanyi LiVitanyi[LV89].

• Anwendungen in der mathematischen Zahlentheorie: Beispielsweise untersuchte Chaitin Chaitin[Cha87] die Lösbarkeit   diophantischer Gleichungen^4.17 und zeigte dabei, daß die Lösung bestimmter diophantischer Gleichungen einen unbegrenzten algorithmischen Informationsgehalt erfordert.

• Die Anwendung der Tatsache, daß es Zeichenketten gibt, die nicht kompromiert werden können: Die nicht komprimierbaren Zeichenketten lassen sich nicht effektiv konstruieren, obwohl es durch das erwähnte Zählargument offensichtlich ist, daß es solche Zeichenketten gibt. Diese Tatsache kann genutzt werden, um elegante und einfache Beweise über Unterschranken von Berechnungskomplexitäten zu führen. Siehe beispielsweise Paul Paul[Pau79]. Weitere Anwendungen sind von Li & Vitanyi in LiVitanyi[LV91] diskutiert oder in Kirchherr Kirchherr[Kir92] zu finden.

Eine Weiterentwicklung des vorgestellten Begriffs der Kolmogoroffkomplexität stellt die resourcenbeschränkte Kolmogoroffkomplexität dar: Hier werden die erlaubten Resourcen^4.18 beschränkt, die zur Erzeugung einer Zeichenkette mittels der komprimierten Zeichenkette (dem Programm für die universelle Turingmaschine) erforderlich sind. Dies nutzte beispielsweise Adleman Adleman[Adl79] um die Zeitkomplexität des Faktorisierungsproblems^4.19 zu untersuchen.

In der Arbeit werden nun mit Hilfe des Begriffs der allgemeinen Kolmogoroffkomplexität eine Reihe von Betrachtungen über die Natur künstlicher Intelligenz und kognitiver Prozesse angestellt. Die Kolmogorffkomplexität dient dabei als Maß der Komplexität einer (statischen) Beschreibung dieser Prozesse - sie hat also noch nichts mit der eventuellen Ausführung eines Algorithmus und damit etwa mit der Zahl der dabei benötigten Rechenschritte zu tun.

Will man jedoch konkreter werden, und bestimmte Probleme im Detail betrachten, so bietet es sich an, dabei auch einen Begriff der resourcenbeschränkten Kolmogoroffkomplexität zu verwenden. Denn einerseits kann man einen Computer bei der Ausführung eines Programms nicht unbeschränkt viel Zeit einräumen und andererseits sind auch bestimmte kognitive Modelle nicht plausibel, wenn man davon ausgeht, daß das menschliche Gehirn als `biologische Rechenmaschine' unbeschränkte Resourcen zur Verfügung hat.^4.20