Thread by @pavel23

Woher kommen Algorithmen? Und wie kommt es, dass mein Gehirn Algorithmen produzieren kann, aber mein Computer Programme braucht, die irgend ein Mensch geschrieben hat? Wo doch mein Gehirn auch nur ein Computer ist, wie ich glaube.

Ja, es gibt genetische Programmierung und maschinelles Lernen, die beide automatisch Algorithmen erzeugen, und selbst ein Schachprogramm erzeugt Algorithmen, nämlich eine Abfolge von Zügen, die möglichst zum Sieg führen sollen, mittels "backtracking".

Und es gibt jede Menge "Codegeneratoren", die Programmstücke aus Datenspezifikationen erzeugen, meist zur Ein- oder Ausgabe von Daten oder deren Übertragung, oder Programmcode aus einer Repräsentation in eine andere überführen, etwa bei Compilern.

Wirklich programmieren können Computer aber nicht. Die Mathematik sagt, dass es nicht möglich ist, das kürzeste Programm zu berechnen, das eine bestimmte Information erzeugt - das mit der niedrigsten Kolgomorow-Komplexität.

Die möglichen Programme sind aber rekursiv aufzählbar, so dass uns nichts daran hindert, jede Menge Programme zu finden, die vielleicht nicht die kürzesten sind, aber funktionieren. Das Problem ähnelt aber dem Reiskornproblem:

Mit jedem Bit mehr verdoppelt sich die Zahl der möglichen Programme, und ein PC bräuchte ca. ein Jahr, um alle Programme auch nur aufzuzählen, die in 48 Bit passen. Brute Force scheidet also komplett aus.

Was passiert also in meinem Kopf, wenn ich ein Programm schreibe oder mir einen Algorithmus überlege? Enthält mein Gehirn vielleicht metaphysische oder transzendente Elemente, die es mir durch göttliche Eingebung ermöglichen, Algorithmen zu finden und Programme zu schreiben?

Gott oder Aliens sind für mich Wildcard-Theorien, die man jederzeit hervorholen kann, um alles zu erklären und nicht weiter darüber nachdenken zu müssen. Das machen wir jetzt nicht. Wäre ja noch schöner, wenn in Wirklichkeit Gott Microsoft Windows geschrieben hat.

In meiner Realität ist der Ausgangspunkt eines Algorithmus eine Spezifikation der Eingabedaten, der Ausgabedaten und wie diese zusammen hängen. Das kann formal oder in natürlicher Sprache ausgedrückt werden, oder einfach ein Gedanke in meinem Kopf sein.

Die Eingabedaten können eine beliebige Abfolge von Bits sein, etwa bei einem Kompressionsprogramm, oder Folgen von Messwerten, etwa Töne, Bilder oder Filme, oder Texte sein, die im Fall von Programmiersprachen einer bestimmten Grammatik entsprechen müssen.

Die Eingabedaten sind zudem optional, etwa, wenn ich die Primzahlen oder Pi berechnen will, aber in der Regel gibt es Eingabedaten, und es gibt eine Relation zwischen Eingabe und Ausgabe. Grundsätzlich genügt es aber, eine Spezifikation der Ausgabedaten zu haben.

Ein Algorithmus besteht im wesentlichen aus Eingaben, Assoziationen, Vergleichen, Fallunterscheidungen, Wiederholungen und Ausgaben. Diese können formal auf verschiedenste Art ausgedrückt werden, als Turing-Maschine, Lamba-Kalkül oder Registermaschine, oder ...

...in der Praxis in einer von hunderten Maschinensprachen oder höheren Programmiersprachen. Dabei kann man denselben Algorithmus in jeder Programmiersprache ausdrücken, die "Turing-vollständig" ist.

Wie komme ich aber von der Spezifikation zum Algorithmus? Nun, ähnlich, wie ich zu einer Tasse Tee komme. Tee bekomme ich, indem ich kochendes Wasser über Teeblätter gieße. Tee ist im Schrank, oder ich muss Einkaufen, Wasser kommt aus dem Hahn, und erhitzen kann ich es auf...

...dem Herd oder mit dem Wasserkocher. Letzterer geht schneller, ich prüfe also den Wasserstand im Kocher, oder ich kippe das alte Wasser weg und zapfe grundsätzlich neues. Wenn ich losen Tee habe, fülle ich ihn den Teefilter, ansonsten entnehme ich ein oder zwei...

...Teebeutel aus ihrer Verpackung und platziere sie in der Teekanne oder ein oder mehreren Teetassen, die ich vorher von ihrem Aufbewahrungsort geholt habe. Ich warte, bis das Wasser kocht und gieße es in die Teekanne, indem ich den Ausfluss des Kochers über das Gefäß bringe...

...und den Kocher so weit neige, dass kochendes Wasser herausfließt und halte ihn in der Position und Orientierung, bis die gewünschte Menge heißes Wasser in der Kanne ist. Habe ich mehrere Tassen, wiederhole ich das für jede Tasse.

Habe ich eine Kanne, warte ich, bis der Tee gezogen hat und gieße mir eine Tasse Tee ein. Voila. Ganz schön viel Algorithmus für eine Tasse Tee, und ich habe mich jeder Menge "Subalgorithmen" bedient, etwa zum Auspacken des Tees oder Füllen des Kochers, die wage beschrieben sind.

Grundsätzlich aber entwirft unser Gehirn ständig Algorithmen, etwa, wie wir an eine Tasse Tee kommen, und passt sie Gegebenheiten an oder optimiert sie. Oder, wenn man morgens im Halbschlaf Frühstück macht, kann es vorkommen, dass man die Schritte nicht in der optimalen...

...Reihenfolge macht und Wasser aufsetzt, obwohl kein Tee mehr da ist, oder erst den Tee und die Tassen und die Kanne holt, bevor man das Wasser aufsetzt, oder man muss noch mal vom Tisch aufstehen, weil man die Löffel oder Untertassen vergessen hat.

Die Kunst, einen allgemeinen Algorithmus zum Tee kochen zu beschreiben besteht auch darin, Eventualitäten und mögliche Störungen oder Fehler im Ablauf zu berücksichtigen, aber das ist keine prinzipielle Anforderung.

Grundsätzlich entsteht in meinem Kopf ein Algorithmus, indem ich das Problem in Teilschritte zerlege und einen einfacheren Algorithmus für das Teilproblem finde oder einen bekannten Algorithmus dafür aus dem Gedächtnis hole. Aber so einfach ist es dann doch nicht.

Das war nämlich einer der ersten Ansätze, die man in der KI ausprobiert, mit GPS, dem "General Problem Solver", und ist gescheitert. Ein Abfallprodukt waren "Expertensysteme", die aber auch nicht die Welt revolutioniert haben.

Warum kann mein PC keinen Algorithmus zum Tee kochen entwerfen? Er hat keine Ahnung von Dingen wie Teekannen oder Wasser eingießen, und das gilt für die meisten Probleme, die wir mit dem Computer lösen wollen: Er hat kein ausreichend komplexes Modell von unserer Realität.

Selbst für einfache Probleme steckt das Generieren von Algorithmen in den Kinderschuhen. Denke, man sollte es probabilistisch anzugehen, aber auch da sind die Grundlagen dünn, fast, als würde Forschung auf dem Gebiet unterdrückt. Kennt ihr interessante Arbeiten zum Thema?