Wovon haben Sie geträumt, als Sie 16 Jahre alt waren? Ich wollte damals Auto fahren, ausgehen und die Welt bereisen. Ray Solomonoff hatte in diesem Alter ehrgeizigere Ziele. Er wollte eine Methode finden, um jedes erdenkliche wissenschaftliche Problem zu lösen. Das war kein reines Wunschdenken – der Jugendliche hatte eine bahnbrechende Idee, die ein komplett neues Forschungsgebiet begründen sollte. In den kommenden Jahren entwickelte Solomonoff ein Konzept, das es ermöglicht, Daten systematisch nach Mustern zu durchsuchen – und so die verborgenen Vorgänge zu offenbaren, die unserer Welt zu Grunde liegen.

Das mag heute an die Arbeitsweise von künstlicher Intelligenz erinnern. Doch Solomonoff formulierte seine ersten Ideen im Jahr 1942 – lange bevor es KI-Algorithmen gab.

Solomonoffs Überlegungen fußen auf dem Prinzip von »Ockhams Rasiermesser«, wonach die einfachste Erklärung für ein Phänomen meist die richtige ist. Daran orientieren sich auch Physiker, wenn sie die Naturgesetze beschreiben: Sie versuchen einfache Formeln zu finden, die möglichst viele physikalische Vorgänge beschreiben sollen. Solomonoff suchte nach einer Art Regelwerk, einen Algorithmus, die verborgene Zusammenhänge in Daten offenbart. Auf diese Weise, so die Hoffnung, ließe sich einfach alles auf der Welt erklären.

Wenn ich zum Beispiel die Flugbahn eines geworfenen Baseballs aufzeichne, können Sie daraus beliebig viele – teilweise sehr komplizierte – mathematische Formeln finden, die den Verlauf der Bahnkurve nachbilden. Um aus all diesen Möglichkeiten die richtige Gesetzmäßigkeit abzuleiten, sollten Sie die einfachste Beschreibung heraussuchen. Diese wird höchstwahrscheinlich den newtonschen Bewegungsgesetzen entsprechen, die das Zusammenspiel von zwei Kräften beschreiben: einmal diejenige, mit der die Person den Ball geworfen hat, und dann die Gravitation, die den Ball zu Boden zwingt. Solomonoff suchte nach einer Vorschrift, die aus allen möglichen Beschreibungen die einfachste auswählt.

Es wäre eine regelrechte Wundermaschine

Eine solche Vorschrift ließe sich in ein Computerprogramm übersetzen. Diesem könnte man beliebige Daten übergeben und nach einer gewissen Zeit die einfachste Erklärung für die Entstehung dieser Werte bekommen. Es wäre eine regelrechte Wundermaschine.

Was ist schon einfach?

So viel schon mal vorab: Solomonoffs Wundermaschine existiert nicht – und sie wird niemals existieren, so viel ist sicher. Dennoch hat der damals 16-Jährige mit seinen Überlegungen ein völlig neues Forschungsfeld eröffnet, das sich mit der wahren Natur von Zufall und Komplexität beschäftigt. Und wie es so häufig in den Naturwissenschaften vorkommt, hatten zwei andere Personen zeitgleich ziemlich ähnliche Ideen.

Eine dieser beiden Menschen war der sowjetische Mathematiker Andrei Kolmogorow, der sich vor allem mit Wahrscheinlichkeiten und Zufallszahlen beschäftigte. Insbesondere interessierte er sich ebenfalls dafür, wie sich entscheiden lässt, ob die Beschreibung eines Phänomens einfach oder kompliziert ist.

Angenommen, ich zeige Ihnen die Zahl 25041903. Auf den ersten Blick wirkt sie ziemlich zufällig. Es gibt verschiedene Möglichkeiten, diesen Wert zu erklären. Ich könnte beispielsweise einen Zufallsgenerator genutzt haben und die Ziffern 2,5,0,4,1,9,0,3 in dieser Reihenfolge erhalten haben. Das erscheint nicht besonders zufrieden stellend – auf diese Weise können Sie keine Gesetzmäßigkeit ableiten, um sich den Wert genauer zu merken. Ich könnte aber auch sagen, dass diese Zahl dem Produkt der drei Primzahlen 3 · 61 · 136 841 entspricht. Oder ich könnte Ihnen mitteilen, dass die Zahlenfolge in der 40 122 575-ten Nachkommastelle von Pi auftaucht. Oder dass ich diese Zahl gewählt habe, weil Andrei Kolmogorow am 25. April 1903 geboren wurde. Welche dieser Erklärungen klingt für Sie am einfachsten? Wahrscheinlich haben verschiedene Personen unterschiedliche Meinungen dazu.

Kolmogorow gelang es, eine objektive Methode zu entwickeln, um die Komplexität von Objekten zu bestimmen: Die Kolmogorow-Komplexität einer Zahl entspricht der Länge des kürzesten Computerprogramms, das die Zahl berechnet. Je kürzer das Programm ist, mit dem man einen Wert wie 25041903 erzeugen kann, desto simpler ist die Zahl.

Damit hängt die Kolmogorow-Komplexität natürlich von der Programmiersprache ab, die man benutzt: Ein bestimmter Zusammenhang könnte in Python kürzer ausfallen als in C++ und umgekehrt. Jedes Computerprogramm lässt sich in Maschinencode ausdrücken, das wiederum aus einer Folge von Nullen und Einsen besteht. Die Länge der kürzesten Null-Eins-Zeichenfolge, für welche ein Computer das gewünschte Ergebnis ausrechnet, entspricht der Kolmogorow-Komplexität.

Möchte man beispielsweise die Kolmogorow-Komplexität von 25041903 bestimmen, kann man die verschiedenen Erklärungen durchgehen (Aufzählen der Ziffern, Primfaktorzerlegung, Position in Pi oder Geburtstag von Kolmogorow), sie in ein Computerprogramm übersetzen und die jeweils benötigten Zeichen im dazugehörigen Maschinencode zählen. Aber vielleicht habe ich eine einfachere Erklärung für 25041903 übersehen, die sich kürzer formulieren lässt.

Um garantiert das kürzeste Programm zu identifizieren, entwickelte Kolmogorow einen systematischen Weg. Dafür übergibt man einem Rechner eine Zahl, etwa 25041903. Dann geht der Computer nach und nach alle möglichen Algorithmen, die es gibt, durch – angefangen mit dem kleinsten, das durch eine 0 oder 1 codiert wird. Das macht der Rechner so lange, bis die ausformulierten Programme das gewünschte Ergebnis produzieren. Das erste Programm, das beispielsweise den Wert 25041903 liefert, ist dann das kürzeste. Dessen Zeichenlänge entspricht der Kolmogorow-Komplexität von 25041903.

Das Berry-Paradoxon zerstört den Traum

Damit scheint der Traum von Solomonoff erreicht. Mit der Kolmogorow-Komplexität lässt sich jedes Muster in beliebigen Daten offenbaren. Ein vollständiges Verständnis unserer Welt schien zum Greifen nah.

Doch ein Paradoxon macht dem Ganzen einen Strich durch die Rechnung. Der Bibliothekar G. G. Berry stieß bereits im 19. Jahrhundert auf das nach ihm benannte Paradoxon – also lange bevor Solomonoff und Kolmogorow ihre Ideen veröffentlicht hatten.

Die kleinste Zahl, die sich nicht durch 20 Wörter beschreiben lässt

Berrys Gedankenexperiment ist folgendes: Angenommen, man habe ein Wörterbuch mit bloß 20 Wörtern und versucht, verschiedene Zahlen durch diese Worte zu beschreiben – ganz ähnlich wie Kolmogorow es sich mit Computerprogrammen überlegt hatte. Man kann also anfangen, nach und nach Zahlen durch diese 20 Wörter zu definieren. Da es nur endlich viele Möglichkeiten gibt, die 20 Wörter miteinander zu kombinieren, kann man nur endlich viele Zahlen beschreiben. Da es aber unendlich viele Zahlen gibt, entgehen einige von ihnen einer solchen Definition. Doch was, wenn man mit den 20 Wörtern folgenden Satz formuliert: »Die kleinste Zahl, die sich nicht durch 20 Wörter beschreiben lässt.«

Da diese Beschreibung bloß elf Worte umfasst, erzeugt die Aussage offensichtlich einen Widerspruch. Was ist schiefgelaufen?

Manche Wahrheiten lassen sich nicht beweisen

Wie sich herausstellt, besteht das Problem darin, dass man nicht berechnen kann, wie viele Wörter nötig sind, um eine Zahl zu definieren. Das erscheint zunächst wie eine billige Ausrede, aber tatsächlich hängen das Berry-Paradoxon und die Kolmogorow-Komplexität mit einer der unintuitivsten Merkmale der Mathematik zusammen: Manche Wahrheiten lassen sich nicht beweisen. Oder anders ausgedrückt: Die Mathematik ist unvollständig.

Das lässt sich in diesem Fall auch beweisen. Angenommen, es gäbe tatsächlich ein Computerprogramm K, das zu jeder Eingabe die zugehörige Kolmogorow-Komplexität berechnet. Dieses Programm bestehe aus einer Million Zeichen – es muss nicht schnell oder effizient sein, sondern einfach nur funktionieren. Nun testen Sie das Programm und füttern es mit allen möglichen Eingaben, bis Sie schließlich eine große Zahl x finden, deren Komplexität zwei Millionen beträgt. Dann gehen Sie ähnlich vor wie beim Berry-Paradoxon. Sie schreiben ein neues Computerprogramm P, das folgende Aufgabe erledigt: Es geht systematisch alle Zeichenfolgen durch und berechnet mit dem Programm K die Kolmogorow-Komplexität der Zeichenfolgen, bis es eine mit einer Komplexität von zwei Millionen findet. Das neue Programm P hängt unmittelbar von K ab und wird daher nicht viel mehr Zeichen enthalten als K (es besteht auf jeden Fall aus weniger als zwei Millionen Zeichen). Damit hat man aber ein Computerprogramm mit weniger als zwei Millionen Zeichen gefunden, das eine Zahl mit einer Komplexität von zwei Millionen berechnet – ein Widerspruch.

Wenn eine logische Argumentation einen Widerspruch erzeugt, muss mindestens eine der Annahmen falsch sein. In diesem Fall haben wir angenommen, dass es ein Programm K gibt, das zu jeder Eingabe die Kolmogorow-Komplexität berechnet. Daher gibt es nur einen möglichen Schluss: Ein solches K kann nicht existieren. Es ist unmöglich, zu jeder erdenklichen Eingabe das kürzeste Programm zu finden, das diese Eingabe erzeugt.

Doch noch ein Happy End

Damit ist Solomonoffs Traum geplatzt. Aber auch wenn man nicht zu jeder beliebigen Eingabe die Kolmogorow-Komplexität berechnen kann, erweist sich die Idee für viele Anwendungen als nützlich.

Denn für die meisten Spezialfälle ist keine exakte Kolmogorow-Komplexität nötig – es genügt, eine Näherung anzugeben. Dafür greifen Fachleute in der Regel auf Kompressionsprogramme zurück. »Indem man gzip nutzt oder ein Bild als .gif-Datei speichert, erhält man eine grobe Annäherung an die Kolmogorov-Komplexität«, erklärt der Informatiker Scott Aaronson von der University of Texas in Austin in »Plus Magazine«.

Möchte man zum Beispiel herausfinden, ob zwei Zahlenfolgen x und y (diese können zum Beispiel Messdaten entsprechen) zusammenhängen, kann man zuerst jeweils x und y einzeln komprimieren und dann beide Folgen aneinanderhängen und xy komprimieren. Wenn die Kompression von xy kaum größer ist als die Einzelkompressionen von x oder y, dann muss es zwischen den Zahlenfolgen Korrelationen geben – und schon hat man Hinweise auf versteckte Muster.

Die Kolmogorow-Komplexität lässt sich auch verwenden, um zu bestimmen, wie zufällig eine bestimmte Zahlenfolge ist. Zum Beispiel könnten die drei achtstelligen Zahlen 25041903, 47395929 und 10101010 durch einen Zufallsgenerator entstanden sein – auch wenn nicht jede gleich zufällig erscheint. Dabei ist die Wahrscheinlichkeit, jede dieser drei Zahlen zufällig zu erzeugen, gleich groß: Im Zahlenraum von 00000000 bis 99999999 trifft man mit einer Wahrscheinlichkeit von je 1 zu 10⁸ auf einen dieser Werte. Aber 10101010 weist ein eindeutiges Muster auf, ebenso wie 25041903, das einem Geburtsdatum entspricht. Indem man die Kolmogorow-Komplexität der Zahlen berechnet, lässt sich beurteilen, ob sie einem bestimmten Muster folgen – und ob ein Zufallsgenerator zuverlässig arbeitet.

Besonders komplex ist die Zahl 42 nicht

Die Kolmogorow-Komplexität beantwortet also leider nicht die Frage nach dem Leben, dem Universum und dem ganzen Rest. Wenn wir dem Sciencefiction-Autor Douglas Adams glauben, dann lautet die Antwort darauf 42. Das erscheint allerdings fragwürdig, besonders komplex ist die Zahl 42 nämlich nicht; das lässt sich mit der Kolmogorow-Komplexität berechnen.

Sie haben auch ein Lieblingsthema zu Mathematik und würden gerne mehr darüber in dieser Kolumne lesen? Dann schreiben Sie es mir gerne in die Kommentare!