Turing-Maschinen

David Hilbert hatte der Mathematik eine Aufgabe gestellt: ein Verfahren zu finden, das über die Wahrheit jeder mathematischen Aussage entscheidet — das Entscheidungsproblem. Um darauf zu antworten, musste Alan Turing 1936 erst etwas klären, woran sich vor ihm niemand versucht hatte: Was heißt es überhaupt, etwas zu berechnen? Der Aufsatz, den der 23-jährige Cambridger Mathematiker dazu vorlegte, hieß On Computable Numbers und beschrieb eine bewusst karge Apparatur — ein unendliches, in Felder geteiltes Papierband; einen Kopf, der Feld für Feld ein Zeichen liest und schreibt und dann nach links oder rechts rückt; eine endliche Regeltabelle, die am inneren Zustand der Maschine ansetzt. Karg, aber hinreichend: Was immer irgendeine physische Maschine je ausrechnen könnte, ließe sich grundsätzlich auch auf diesem Band ausrechnen. Die Maschine, auf der das digitale Zeitalter beruhen sollte, stand in einem Aufsatz, den vielleicht zwei Dutzend Menschen gelesen haben.

Eine Berechnung ist in diesem Bild nichts als eine Folge von Konfigurationen — Bandinhalt, Kopfstellung, aktueller Zustand —, und von einer zur nächsten kommt man durch einen einzigen Blick in die Regeltabelle: Denken, heruntergebrochen auf Buchführung. Aus diesem kargen Anfang holte Turing drei Ergebnisse heraus, die geblieben sind. Das erste ist die universelle Turingmaschine: Schreibt man die Beschreibung einer beliebigen Turingmaschine auf das Band, so verrichtet eine einzige, feste Maschine deren Arbeit. Damit ließen sich Hardware und Software voneinander lösen — ein unveränderliches Gerät, ein austauschbares Programm —, und im Kern steht der speicherprogrammierte Rechner damit auf dem Papier, ein Jahrzehnt bevor der erste gebaut wurde. Gebaut wurde er später, mit dem ENIAC und der Von-Neumann-Architektur; die Idee aber war fertig. Das zweite ist das Halteproblem: Kein Algorithmus kann für ein beliebiges Programm samt Eingabe entscheiden, ob es je anhält oder ewig weiterläuft. Der Beweis führt ein Diagonalargument, dem Geist nach dasselbe wie bei Gödels Unvollständigkeitssatz, und zieht eine harte Grenze um das, was ein rechnendes System über sich selbst herausfinden kann — eine formale Unentscheidbarkeit, die im Begriff der Berechnung steckt und keine Lücke, die sich mit mehr Scharfsinn schließen ließe. Das dritte ist die Church-Turing-These, gemeinsam mit Alonzo Church, der auf eigenem Weg zum Lambda-Kalkül gekommen war: Was sich überhaupt effektiv berechnen lässt, lässt sich von einer Turingmaschine berechnen. Ein Theorem ist das nicht — effektive Berechenbarkeit ist nirgends formal definiert —, doch seit bald hundert Jahren hat kein Gegenbeispiel standgehalten, Quantenrechner eingeschlossen. Ihre stille Wucht bezieht die These daraus, dass sich jedes ernsthafte Modell des Rechnens als gleichwertig herausstellt: Churchs Lambda-Kalkül, Gödels rekursive Funktionen, Registermaschinen, heutige Programmiersprachen — alle berechnen genau dieselbe Klasse von Funktionen, keine mehr und keine weniger. Deshalb darf „berechenbar“ als ein einziger, absoluter Begriff gelten und nicht als Eigenart einer bestimmten Bauform.