Das mathematikhistorische Kalenderblatt - August 2011

Zurück zur Übersicht des mathematikhistorischen Kalenderblatts

2011: 75 Jahre Turingmaschinen und Turing-Berechenbarkeit

Fast ist man versucht, das Jahr 1936 als das Geburtsjahr der theoretischen Informatik zu bezeichnen: Während das Problem der „Entscheidbarkeit“ der Wahrheit bzw. Allgemeingültigkeit von Aussagen schon seit dem Mittelalter durch die philosophische und logische Literatur geistert, wobei aber an eine „maschinelle” Lösung seit Ramón Lullo (1234? – 1315) nicht mehr explizit gedacht wurde, traten Entscheidungsprobleme spätestens 1900 durch den berühmten Problemvortrag Hilberts auf dem 2. Internationalen Mathematikerkongress und das darin umrissene Problem der Lösbarkeit diophantischer Gleichungen auch als innermathematische Probleme auf.

Bekanntlich bewies Kurt Gödel 1931 die Unentscheidbarkeit der Allgemeingültigkeit von Ausdrücken im Prädikatenkalkül 1. Stufe, aber dieser Beweis basierte auf einem noch nicht vollständig geklärten Effektivitätsbegriff. Alan Turing brachte in seiner 1936 vollendeten, 1937 gedruckten Arbeit „On computable numbers with an application to the Entscheidungsproblem” erstmals das exakt definierte Konzept einer virtuellen Maschine mit endlich vielen Zuständen und einem potentiell unendlichen Speicher ins Spiel. Es ist seither wenig gewürdigt worden, dass ebenfalls 1936 eine sehr kurze Note von Emil L. Post (1897 – 1954) „Finite combinatorial processes. Formulation I” erschien, in der das gleiche Konzept sogar noch klarer formuliert wurde.

Alan M. Turing
(1912 – 1954)

Emil L. Post
(1897 – 1954)

Das Maschinenmodell beider Arbeiten ist sehr ähnlich und kann aus heutiger Sicht als endlicher Automat beschrieben werden, der in Wechselwirkung mit einem potentiell unendlichen Speicher steht. Während Turings erste Maschine dazu gedacht war, die unendliche Folge der Dezimalstellen von „berechenbaren” reellen Zahlen zu produzieren, also gar nicht anhalten sollte, geht es bei Post um maschinelle Transformationsprozesse von Zeichenreihen, die nur dann ein Resultat liefern, wenn sie nach endlich vielen Schritten beendet sind.

Diese erste klare Definition der Berechenbarkeit von Wortfunktionen (d.h. Funktionen, deren Argumente und Werte Zeichenreihen eines gegebenen endlichen Alphabetes sind) zieht sogleich eine Definition der Begriffe Entscheidbarkeit und Aufzählbarkeit von Wortmengen nach sich. Turing führte den Begriff der universellen Maschine ein und zeigte, wie einfach man mit Hilfe dieses Begriffs algorithmisch unentscheidbare Probleme definieren kann. Von hier an gibt es eine deutliche Verzweigung der Entwicklung. In der einen Richtung folgte eine Fülle von Resultaten über die Zusammenhänge zwischen Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit sowie über die Unentscheidbarkeit spezieller mathematischer und logischer Probleme, zum Beispiel der verschiedenen „Wortprobleme” der Gruppen- und Halbgruppentheorie.

All dies kann man noch der Mathematik im traditionellen Sinne zurechnen. In der anderen Richtung wurde zunächst die Äquivalenz der Turingberechenbarkeit mit verschiedenen anderen Präzisierungen des intuitiven Berechenbarkeitsbegriffes (zum Beispiel dem von A. Church begründeten λ-Kalkül oder den durch Grundfunktionen und Erzeugungsprinzipien induktiv definierten rekursiven Funktionen) nachgewiesen, wodurch die von Church 1936 formulierte und nach ihm benannte These über die Äquivalenz des präzisierten mit dem intuitiven Berechenbarkeitsbegriff gestützt wurde. (Diese These kann natürlich nicht im mathematischen Sinne bewiesen werden, da sie einen präzisen Begriff in Beziehung zu einem unpräzisen setzt.) Sodann wurden zahlreiche Varianten der ursprünglichen Turingmaschinen erdacht, darunter solche mit ebenem statt linearem Speicher, mit scheinbar stärkeren und solche mit scheinbar schwächeren Fähigkeiten, die sich sämtlich als äquivalent (d.h. gegenseitig simulierbar) erwiesen haben.

Es gab auch eine Jagd nach universellen Maschinen mit möglichst geringer Zahl von Zuständen oder möglichst geringer Zahl von Hilfszeichen (die für die Rechnung benötigt werden, aber weder in der Eingabe noch in der Ausgabe vorkommen). Im Rahmen dieser Untersuchungen lernte eine ganze Generation heranwachsender Mathematiker, in den Kategorien von hypothetischen Maschinen und ihrer Programmierung, von Kodierung, Umkodierung, Simulation und letztlich auch von Speicher- und Zeitbedarf zu denken. Aus Algorithmentheorie wurde Komplexitätstheorie. Das alles hatte mit Mathematik im traditionellen Sinn nur noch wenig gemeinsam. Aus den Reihen der so ausgebildeten Mathematiker kamen dann auch viele derjenigen, die die realen Computer bauten und bedienten, mit an erster Stelle Turing selbst. Über seine Rolle beim Bau und bei der Nutzung des ersten britischen Großrechners im zweiten Weltkrieg gibt es inzwischen mehrere Bücher und auch Filme.

Die aus der traditionellen Mathematik ausgeschiedenen Wissenschaftler und Techniker verwandelten den programmierbaren Rechenautomaten, zeitweise „Elektronenhirn“ genannt, in historisch kurzer Zeit in ein Werkzeug, ohne das heute kaum noch ein Bereich menschlicher Aktivität auskommt.

Literaturhinweise

Alan M. Turing: Intelligence Service. Hrsg. B. Dotzler u. F. Kittler. Brinkmann & Bose, Berlin 1987, enthält wesentliche Arbeiten von Turing, darunter die hier besprochene von 1936/37, in deutscher Übersetzung sowie Biographisches.
The universal Turing machine, a half-century survey (Sammelband von Beiträgen verschiedener Autoren). NewYork 1988.
Martin Davis: The Undecidable. Raven Press, New York 1965, eine inzwischen selbst schon historische Sammlung von wichtigen Originalarbeiten.
P. Schreiber: Grundlagen der Mathematik. Deutscher Verlag der Wissenschaften, Berlin (Ost), ²1984. Enthält eine ausführliche Einführung in die Programmierung von Turingmaschinen sowie verschiedene Varianten und Skizzen von Äquivalenzbeweisen mit anderen Präzisierungen der effektiven Berechenbarkeit.
Sara Turing: Alan M. Turing. Cambridge 1959.
Andrew Hodges: Alan Turing. Simon & Schuster, NewYork 1983.
Rolf. Hochhuth: Alan Turing, Erzählung. Rowohlt, Hamburg 1987, auch in: Jede Zeit baut Pyramiden, Volk und Welt, Berlin (Ost) 1988.
Robert Harris: Enigma. Random House, London/ NewYork 1995 deutsch bei Heine, München 1995. Film: Breaking the code. GB 1997, deutsch als: Der codierte Mann.
Theaterstücke: Breaking the code (Hugh Whitemore nach Hodges) Jenseits aller Gewissheit (Göranson & Karlquist)