Total berechenbar
Wie eine Algorithmusmaschine Lösungen für wirklich jedes Problem findet.
Ein Theorieschnipsel zu Alan Turing.
Da werden alle neugierig: „On Computable Numbers, with an Application to the Entscheidungsproblem” — auch, weil Sprache wechseln, klar, voll nice ist. Worum geht’s? Vielleicht um die einfache Frage, ob Ja oder Nein? Von wegen Entscheidung und so? Nee, leider nicht. Sondern darum, ob eine Formel der Prädikatenlogik allgemeingültig ist. Also ob jede Interpretation einer mathematischen, das heißt formal logischen, Aussage wahr ist? Ha ha ha — what!? Auf jeden Fall irgendwas mit Mathe. Irgendwelche Probleme mit Entscheidungen, okay. Checkt aber erstmal keiner. Bevor wir also klären können, warum Alan Turing mit seiner Schrift etwas geleistet hat, was uns alle betrifft, müssen wir zumindest grob erläutern, bei welchen Entscheidungen es überhaupt zu Problemen kam.
Wir befinden uns hier in der theoretischen Informatik. Also der Theorie hinter dem elektronischen Firlefanz (Handy, Computer, Fernseher, Auto, U-Bahn-Netz und so weiter), der uns unseren Alltag erleichtern soll. Damit dieser Firlefanz funktioniert, müssen sich Menschen überlegen, wie sich bestimmte Funktionen dieses Firlefanzes errechnen lassen. Es geht also darum, Verfahren zu entwickeln, Pläne, die es dem Firlefanz ermöglichen, automatisch Entscheidungen zu treffen. Diese Verfahren haben einen sehr bekannten Namen. Sie heißen: Algorithmen. Algorithmen sind letztlich einfach nur eindeutige Handlungsvorschriften zur Lösung eines Problems. Es sind viele wohldefinierte Einzelschritte. Sie können in menschlicher Sprache formuliert („Tu dies, dann das und voilà!”), in Bildern ausgedrückt (Ikea!) oder in ein Computerprogramm implementiert werden (Word!). Ein Algorithmus löst ein Problem, mehr nicht. Und kann ein Algorithmus jedem Element einer bestimmten Menge eine Eigenschaft zuordnen, ist diese Menge entscheidbar, also berechenbar. Ein Entscheidungsproblem ist also die Frage, ob es für das betreffende Problem einen Algorithmus gibt oder nicht.
Nun haben Mathematiker*innen ständig irgendwelche Probleme. Ein Mann namens David Hilbert hat am 8. August 1900 gleich 23 auf einmal aufgelistet. Eines davon war eben, ob eine Formel der Prädikatenlogik allgemeingültig sei. An dieser Stelle könnten wir uns jetzt die Prädikatenlogik vornehmen, schauen, was sie von der Aussagenlogik unterscheidet, und warum beides einfach total geil ist. Aber wir wollen ja eigentlich wissen, warum Alan the Turingmachine so eine Hammersache ist. Also scheißen wir einfach drauf und kommen gleich zur Sache: Hilbert stellte nämlich gleichzeitig die Frage, ob dieses Prädikatenlogik-Problem automatisch gelöst werden könne, also mit einer Maschine, das heißt mit einem Algorithmus. Und das wusste eben keiner. Bis 1936 Alan Turing kam und mit seiner Turingmachine eine Methode ersann, die für jegliche Probleme einen Algorithmus findet — wenn es denn einen gibt. Das funktioniert total simpel: Auf einem imaginären unendlichen Band sind einzelne Felder eingeteilt. Auf jedem Feld steht eine Zahl — 0 oder 1 zum Beispiel.
Schritt für Schritt bewegt sich nun eine Maschine entlang dieses Bandes von Feld zu Feld und liest die entsprechende Zahl. Die Maschine hat außerdem einen Hebel mit drei Einstellungen. Und in einer Tabelle wird festgelegt, welche Aktionen ausgeführt werden sollen — je nachdem, wie der Hebel eingestellt ist und welche Zahl auf dem Band steht. Jetzt kann der Maschine mit der Tabelle praktisch alles Mögliche gesagt werden: Wenn da ’ne 1 steht, gehst du nach rechts, bei ’ner 0 nach links oder so. Und mehr ist es eigentlich auch nicht. Schreib in die Tabelle, was passieren soll, und schick die Maschine das Band entlang. Bumm tschack!
Turing gibt also die entsprechende Prädikatenlogik-Parameter in die Tabelle ein, und wie sich herausstellte, gab es für das Hilbert’sche Entscheidungsproblem keinen Algorithmus. Gut zu wissen, aber scheißegal, weil viel wichtiger: Alan Turings Turingmachine kann Algorithmen erstellen, automatische Pläne zur Lösung von Problemen, und zwar ganz allein, ohne die Hilfe von Menschen. Geil!