Leibniz' Werk und Turings Beitrag

Jedes Kind ahnt heute, was Computer alles können: Sie ermöglichen nicht weniger als die globale Vernetzung, das Erschaffen fantastischer Film- und Spielewelten, Vorhersagen über Wetter und andere Ereignisse; ohne digitale Rechner hätten Ende der 60er Jahre die Fahrzeuge des Apollo-Programms nicht im Ansatz eine brauchbare Steuerung gehabt; und nicht zuletzt dank maschineller (wenn auch nicht universeller) Rechner hat Alan Turing im Zweiten Weltkrieg die Verschlüsselung des deutschen Militärs geknackt und so den Krieg um Jahre verkürzt.

Doch wo liegen die Grenzen von universellen Rechenmaschinen, vulgo: Computern? Gibt es Probleme, deren Lösung man nicht mechanisch ausrechnen kann? Und wann haben Menschen das erste Mal gedanklich an diese Grenzen gerührt? War es etwa 1943, in der frühesten Pionierzeit, als der Chef von IBM einen Weltmarkt für vielleicht fünf Computer vorhersagte?

Die Antwort ist nein. Wir müssen viel weiter zurückgehen, und zwar in das 17. Jahrhundert, die Zeit des Sonnenkönigs Ludwig XIV. In der Mitte jenes Jahrhunderts, etwa 40 Jahre vor Bach und Händel, wurde der Vordenker Gottfried Wilhelm Leibniz geboren. Und gerade, als die beiden Musikgenies das Licht der Welt erblickten, wuchs in dem Universalgenie Leibniz ein Traum, der uns bis heute fasziniert.

Leibniz glaubte, eines Tages würde man jede Streitfrage zwischen zwei Wissenschaftlern ein für alle Mal und vollkommen objektiv lösen können. Dazu würde man jede der beiden konträren Aussagen in eine (zu erfindende) formelhafte Sprache übersetzen, die Leibniz Characteristica universalis nannte, weil sie jeglichen menschlichen Gedanken würde ausdrücken können. Danach würde man quasi mechanisch eine endliche Folge an Rechenschritten ausführen, einem (zu erfindenden) System folgend, welches er Calculus ratiocinator nannte. Schließlich würde man unzweifelhaft erfahren, welche der Formeln schlichtweg wahr wären und welche nicht – einzig und allein durch stupides Rechnen. Leibniz' Wahlspruch lautete folglich: Calculemus! (Lasst uns rechnen!)

Wie sehr Leibniz damit seiner Zeit voraus war, erkennen wir daran, dass seine Idee erst im beginnenden 20. Jahrhundert wieder aufgegriffen wurde. Noch immer waren Mathematik, Philosophie und Logik kaum voneinander getrennt. Doch nun bekamen diese Disziplinen einen enormen Schub – es wurden Fragen behandelt wie: Was bedeutet unendlich? Was ist eine Zahl? Kann man ausrechnen, ob eine Aussage wahr ist oder nicht? Die Größen dieser Zeit hießen Richard Dedekind, Georg Cantor, Gottlob Frege, Giuseppe Peano, David Hilbert, Ernst Zermelo und Bertrand Russel.

Man schaffte es, eine Characteristica universalis zu kreieren; es wuchs sogar ein kleiner Zoo dieser formelhaften Sprachen heran, denn die Zeit war einfach reif für Leibniz' Idee. Berühmt geworden ist dabei das Buch Principia Mathematica von Bertrand Russell und Alfred North Whitehead, welches die Mathematik mithilfe der Prädikatenlogik formalisierte. Auch eine Art Calculus ratiocinator kam in Form einer endlichen Zahl von Schlussregeln gleich mit; unter diesen der sogenannte Modus ponens, den schon die alten Griechen kannten.

Diese Entwicklung gab Anlass zu Euphorie; dem Leibnizschen Traum stand scheinbar nichts im Wege. Die einzige offene Frage war, ob man in dem System der Principia Mathematica wirklich für jede Aussage entweder die Aussage selbst oder aber ihr Gegenteil würde herleiten können. Doch das galt eigentlich als eine reine Formalität. Hilbert war sogar zuversichtlich, dass man mit dem System die Richtigkeit der Mathematik an sich (genauer: ihre Widerspruchsfreiheit) würde beweisen können; und so prägte er seine berühmten Worte, die auch seinen Grabstein zieren: Wir müssen wissen. Wir werden wissen. Man nennt dieses Vorhaben heute das Hilbertprogramm.

Doch mit der Euphorie war es 1930 jäh vorbei, als der Mathematiker Kurt Gödel seine beiden Unvollständigkeitssätze aufstellte. Vereinfacht gesagt zeigte er zuerst, dass die Principa Mathematica unvollständig ist, das heißt, dass es Aussagen gibt, die man innerhalb dieses System weder beweisen noch widerlegen kann. Schlimmer noch: Daran würde sich nichts ändern, wenn man die Principia Mathematica erweitern würde, und die besagten Aussagen sind beileibe nicht abwegig oder weltfremd. Wenn eine solche Aussage im wissenschaftlichen Disput auftauchen sollte, könnte dieser eben nicht durch bloßes Rechnen beigelegt werden. Damit war der Leibnizsche Traum bereits stark lädiert. Als zweites zeigte Gödel: Auch die Widerspruchsfreiheit der Mathematik kann man mit einem solchen System nicht beweisen. Und somit war auch das Programm von Hilbert erledigt.

Es war nun klar: Es gab Aussagen, die sich weder beweisen noch widerlegen ließen. Man brauchte also drei Schubladen, um Aussagen einzuteilen: (a) beweisbar, (b) weder beweisbar noch widerlegbar, (c) widerlegbar. Es blieb noch das Problem, wie man feststellen (entscheiden) sollte, in welche der Schubladen eine gegebene Aussage gehörte. Man nannte dies das (Hilbertsche) Entscheidungsproblem. Oder sollte dieses Problem etwa die Grenzen dessen überschreiten, was überhaupt ausgerechnet werden kann?

Diese Frage beantwortete sechs Jahre nach Gödels Arbeiten der britische Mathematiker Alan Turing. Der geneigte Leser kennt Turing vielleicht aus dem jüngsten Kinofilm über ihn, The Imitation Game. Turing veröffentlichte 1936 eine wissenschaftliche Arbeit mit dem Titel On Computable Numbers, with an Application to the Entscheidungsproblem. In dieser Arbeit zeigte er, vereinfacht gesagt: Es gibt Probleme, die einerseits einfach sind, weil ihre Formulierung mit den Grundrechenarten auskommt, die andererseits aber nicht in endlich vielen Rechenschritten gelöst werden können.

Für den Beweis führte Turing einen Begriff ein, der heute als Turingmaschine bezeichnet wird. Nun ist es nicht so, dass man irgendwo nach England fahren kann, nach Cambridge oder so, und dann geht man in ein altes, ehrwürdiges Museum, und dort steht sie dann, die Turingmaschine, und dann staunt man und sagt Toll., und der Ausflug hat sich gelohnt. Das geht leider nicht, denn die Turingmaschine ist reine Fiktion, die man nur gedanklich besuchen kann. Nichtsdestoweniger ist sie toll, und auch der gedankliche Ausflug lohnt sich, denn sie macht Turings genialen Beweis in der Tat recht anschaulich.

Mit Turings Arbeit war – sieben Jahre vor dem ersten nichtfiktionalen Computer, Konrad Zuses Z3 – klar: Es gibt Probleme, die man nicht ganz allgemein mit Computern lösen kann, und das Entscheidungsproblem gehört dazu. Der Leibnizsche Traum war endgültig ausgeträumt. Und doch gilt das Motto Calculemus! heute mehr denn je, denn – wie eingangs erwähnt – seit Jahrzehnten rauben Computer uns den Atem mit dem, was sie können, und das wird auf absehbare Zeit so bleiben.

Matthias Büchse am 13. August 2015

Weiterführende Literatur

Hier führe ich Bücher an, die ich besitze und empfehle. Außerdem die Originalarbeit von Turing, weil sie im Netz verfügbar ist. Leider ist die Arbeit von Gödel nicht zum Download verfügbar, ebenso wenig wie die Principia Mathematica. Auch wenn man letztlich sowieso lieber Sekundärliteratur lesen wird, ist das schlicht eine Schande.

zurück: Die Warum-Frage oder: Die Frage nach dem richtigen Antrieb
vor: Aber heute: Aggression!

Impressum