Von Thomas von Randow

Gelegentlich lesen wir, daß allzu intensives Jogging den Geist trübe. Nachgewiesen hat es bislang niemand. Hingegen ist ein frappierendes Gegenbeispiel verbürgt. Geliefert hat es vor gut einem halben Jahrhundert Alan Mathison Turing, ein knapp über zwanzig Jahre alter Mathematiker an der Universität Cambridge in England. Seinen Geist jedenfalls hat das schweißtreibende Freizeitvergnügen – zu jener Zeit noch Dauerlauf geheißen – geradezu erhellt. Denn während er keuchend über die Pfade der lieblichen Grafschaft Cambridgeshire trabte, war ihm der Gedanke gekommen, wie eine in den dreißiger Jahren leidenschaftlich diskutierte Frage der mathematischen Logik, das Entscheidungsproblem, auf höchst plausible Weise zu beantworten sei.

Damals steckte die Mathematik in einer tiefen Krise. Verursacht hatte sie der böhmische Logiker Kurt Gödel, der 1932 schlüssig nachwies, daß das Fundament der exaktesten aller Wissenschaften ziemlich wackelig ist. Die reine Mathematik stellte sich plötzlich als befleckt dar. Gödel war es gelungen, durchaus legitime mathematische Aussagen zu formulieren, deren Richtigkeit jedoch weder beweisbar noch widerlegbar ist. Zunächst hatten die Gelehrten gehofft, den Makel zu beseitigen, indem sie das mathematische Grundgesetz – das Axiomensystem – mit zusätzlichen Regeln ergänzten. Doch diese Hoffnung erwies sich als trügerisch; denn keine noch so durchgreifende Gesetzesreform würde die widerborstigen Aussagen eliminieren. Wie alles in der Welt ist eben auch die Mathematik unvollkommen.

Wir könnten uns damit abfinden, wenn es ein Verfahren gäbe, nach dem sich wenigstens ermitteln ließe, ob eine gegebene mathematische Aussage zu jenen Schandflecken gehört oder nicht, so daß es sich erübrigte, nach ihrem Beweis oder einem Gegenbeispiel zu fahnden. Das Verfahren müßte ein „Algorithmus“ sein, das heißt, es müßte nach Anwendung einer endlichen Anzahl von mathematischen Operationen die angestrebte Entscheidung herbeiführen; anderenfalls hätte das Ganze keinen praktischen Wert.

Mit diesem Entscheidungsproblem im Kopf lief Alan Turing irgendwann im Jahre 1935 am Flüßchen Cam entlang, als dem 23jährigen fellow des Kings College ein kurioser Gedanke in den Sinn kam: Einen Algorithmus auszuführen sei doch eine mechanische Tätigkeit, ergo könne dies auch eine Mechanik erledigen. Fortan beschäftigte sich Alan Turing mit dem Entwurf eines möglichst einfachen Problemlösungsgerätes. Er brauchte den Apparat, die inzwischen berühmte „Turing-Maschine“, allerdings nicht zu bauen; sie diente ihm lediglich als ein Gedankeninstrument, mit dem sich das Entscheidungsproblem untersuchen ließ.

Turing konstruierte – freilich nur in Gedanken – für jede mathematisch korrekt formulierte Aussage eine Maschine, deren Funktion es war, zu prüfen, ob diese spezielle Aussage wahr ist oder nicht. War die Prüfung beendet, blieb die – gedachte – Maschine stehen und gab ein Signal aus, zum Beispiel 1 für „wahr“ und 0 für „falsch“. Es mag allerdings auch geschehen, daß so ein Apparat nie zum Stillstand kommt, „sich aufhängt“, wie es im Computerlingo heißt, weil er in einen unentrinnbaren Teufelskreis geraten ist. In diesem Fall läßt sich die Frage, ob die entsprechende Aussage wahr oder falsch ist, nicht entscheiden.

Turing „erfand“ sodann eine Universalmaschine, welche die Tätigkeit jeder denkbaren Turing-Maschine vollständig übernehmen kann – sie könnte übrigens auch jeden Computer, vom PC bis zum Superrechner Cray imitieren. Eines aber vermag sie nicht: vorweg zu ermitteln, ob eine von ihr imitierte Turing-Maschine jemals zum Stillstand kommen wird. Da jeder Prüfung auf die Wahrheit einer mathematischen Aussage eine Turing-Maschine entspricht, löst diese hieb- und stichfest erwiesene Erkenntnis Turings das Entscheidungsproblem. Wir müssen die Hoffnung begraben, die schwarzen Schafe unter den mathematischen Aussagen auszumachen.