Turing-Maschinen

Im Jahr 1936 veröffentlichte ein 23-jähriger Cambridge-Mathematiker namens Alan Turing eine Arbeit mit dem Titel On Computable Numbers. Um das Entscheidungsproblem zu beantworten — David Hilberts Herausforderung, ein Verfahren zu finden, das über die Wahrheit jeder mathematischen Aussage entscheiden könnte — tat Turing etwas, das niemand zuvor getan hatte: er gab eine präzise mathematische Definition dafür, was es heißt, irgendetwas zu berechnen. Das Modell — ein unendliches, in Felder geteiltes Papierband, ein Kopf, der jeweils ein Symbol liest und schreibt und sich nach links oder rechts bewegt, und eine endliche Regeltabelle, die am inneren Zustand der Maschine ansetzt — war bewusst karg. Es war auch hinreichend. Jede Berechnung, die irgendeine physische Maschine je ausführen könnte, ließe sich grundsätzlich von einer solchen Maschine ausführen. Die begriffliche Maschine, die dem Digitalzeitalter zugrunde liegen sollte, wurde in einer Arbeit skizziert, die vielleicht zwei Dutzend Leute gelesen haben.

Eine Berechnung ist in diesem Bild nichts weiter als eine Folge von Konfigurationen — der Bandinhalt, die Kopfposition, der aktuelle Zustand —, deren jede aus der vorigen durch ein einziges Nachschlagen in der Regeltabelle hervorgeht; Denken, zur Buchführung mechanisiert. Von diesem kargen Anfang aus bewies Turings Arbeit drei Resultate von dauerhafter Bedeutung. Erstens die universelle Turing-Maschine: eine einzelne Turing-Maschine kann jede andere Turing-Maschine simulieren, sofern ihr deren Beschreibung, auf das Band geschrieben, als Eingabe vorliegt. Hardware und Software wurden trennbar — eine feste Maschine plus ein austauschbares Programm —, und die universelle Maschine ist im Kern der speicherprogrammierte Rechner, ein Jahrzehnt bevor irgendeiner gebaut wurde. Das ist die Kernabstraktion jedes modernen Computers; die Technik kam erst später, mit dem ENIAC und von Neumanns Architektur, doch die Idee lag bereits vollständig auf dem Papier. Zweitens das Halteproblem: es gibt keinen Algorithmus, der für ein beliebiges Programm samt Eingabe entscheiden könnte, ob das Programm anhält oder ewig weiterläuft. Der Beweis stützt sich auf ein Diagonalargument — dem Geist nach mit Gödels Unvollständigkeitssatz identisch — und setzt eine harte Grenze dafür, was ein Berechnungssystem über sich selbst entscheiden kann: eine formale Unentscheidbarkeit, die der Berechnung eingebaut ist, keine vorübergehende Lücke unseres Scharfsinns. Drittens die Church-Turing-These (gemeinsam mit Alonzo Church, der unabhängig zum Lambda-Kalkül gelangt war): jede Funktion, die sich überhaupt effektiv berechnen lässt, lässt sich auch von einer Turing-Maschine berechnen. Die These ist kein Theorem (effektive Berechnung ist nicht formal definiert), hat aber seit nahezu einem Jahrhundert allen versuchten Gegenbeispielen standgehalten, Quantencomputer eingeschlossen. Ihre stille Wucht liegt darin, dass sich jedes plausible Berechnungsmodell als gleichwertig erweist — Churchs Lambda-Kalkül, Gödels rekursive Funktionen, Registermaschinen und moderne Programmiersprachen berechnen exakt dieselbe Klasse von Funktionen, nicht mehr und nicht weniger. Diese Übereinstimmung ist der Grund, warum „berechenbar“ als ein einziger, absoluter Begriff gelten kann und nicht als Eigenheit einer bestimmten Maschine.