Alan Turings Maschine

Vor neunzig Jahren, offiziell am 12. November 1936, nahm die Londoner Mathematische Gesellschaft eine Arbeit des jungen Mathematikers Alan Turing an. Sie wurde im November und Dezember 1936 gedruckt und umriss ein Gerät, das dann den Namen Turing-Maschine erhielt. Es zählt zu den wichtigsten Werkzeugen der theoretischen Informatik und zu den konzeptionellen Vorläufern des Computers.

„Der Verfasser definiert eine unendliche Folge der Ziffern 0 und 1 als berechenbar, wenn sich eine rechnende Maschine mit endlichen Maßen und endlich großen Teilen angeben lässt, die die Folge in jeder beliebigen Länge niederschreibt, wenn genug Zeit zur Verfügung steht. …ein menschlicher Rechner mit Papier und Bleistift und genauen Instruktionen kann als eine Art Turing-Maschine betrachtet werden.“

Diese Passage stammt vom amerikanischen Logiker Alonzo Church und aus der Rezension eines Artikels, der in den Proceedings der Londoner Mathematischen Gesellschaft stand. Eingereicht wurde er am 28. Mai 1936 und akzeptiert auf einem Treffen der Gesellschaft am 18. Juni; wir stützen uns hier auf einen Aufsatz von Jack Copeland. Die Druck erfolgte am 30. November und 23. Dezember 1936, wobei sich das falsche Annahmedatum 12. November einschlich. Der Titel des Textes lautete „On Computable Numbers, with an Application to the Entscheidungsproblem“, der Autor hieß Alan Turing.

Alan Turing in den 1930er-Jahren

Ihn müssen wir nicht groß vorstellen. Geboren am 23. Juni 1912 in London, studierte er Mathematik in Cambridge und in Princeton, wo er 1938 promovierte. Im Zweiten Weltkrieg arbeitete Alan Turing im Entschlüsselungszentrum Bletchley Park, danach begann er in London mit der Entwicklung eines Computers. 1948 wechselte er an die Universität von Manchester. 1950 erfand er den nach ihm benannten Test für das Denkvermögen einer Maschine. 1952 wurde er wegen Homosexualität angeklagt und zu einer medikamentösen Therapie verurteilt. Er nahm sich am 7. Juni 1954 das Leben.

Der Artikel „On Computable Numbers“, zu deutsch „Über berechenbare Zahlen“, dürfen wir das mathematisch-logische Hauptwerk von Alan Turing nennen. Der Titel erwähnt noch das Entscheidungsproblem, also die Frage, ob eine Formel der Prädikatenlogik allgemeingültig oder beweisbar ist – die beiden Eigenschaften sind in jener Logik äquivalent. Wir möchten das Problem, das Turing am Ende als unlösbar nachwies, einmal beiseite lassen und uns auf die wichtigste Erfindung des Textes konzentrieren, das Konzept, das später den Namen Turing-Maschine erhielt.

Alan Turing definierte zu Beginn eine „computing machine“, eine rechnende Maschine. Durch sie läuft ein Band, das in Quadrate geteilt ist und das die Maschine nach links oder nach rechts verschieben kann. Sie kann zudem in ein Quadrat eine Null, eine Eins oder ein anderes Symbol schreiben oder ein schon gesetztes Symbol überschreiben oder löschen. Dabei nimmt die Maschine stets einen von mehreren Zuständen an; Turing sprach von m-Konfigurationen, die eine Tafel bilden. Nach einer Aktion kann sie im alten Zustand bleiben oder in einen neuen übergehen.

Turing-Maschine von Gisbert Hasenjaeger in der revidierten Form nach Hao Wang

Die Maschine liefert berechenbare Zahlen und berechenbare Folgen, aus denen sich erstere ergeben. Als Beispiel einer solchen Folge führte Turing   01010101…  an. Es macht deutlich, dass er – was schon Alonzo Church sah – eine Berechnung als eine Erzeugung verstand und unendlich lange Resultate erlaubte. Nach der einfachen kam Alan Turing zur universellen Maschine, die mit Hilfe normierter Beschreibungen jede denkbare Maschine ersetzt. Das Halteproblem taucht im Text nicht auf, doch wies er nach, dass keine Maschine sagen kann, ob eine beliebige andere jemals ein bestimmtes Symbol produziert.

Als Turings Schrift Ende 1936 in Druck erschien, wurde sie wohl nur von wenigen Fachleuten verstanden. Sie war auch nicht frei von Fehlern; 1937 trug der Autor vier Seiten Korrekturen nach. Im Lauf der Zeit stellten sich einfache Definitionen ein, seit den frühen 1950er-Jahren verbreitete sich die Bezeichnung „Turing-Maschine“ und das Bild der Maschine als eine Art Ur-Computer. In der so bereinigten Form avancierte sie zu einem Pfeiler der theoretischen Informatik. Wir möchten auf eine revidierte Darstellung verzichten und verweisen auf den Blogbeitrag zum fleißigen Biber, der das moderne Konzept mit Beispielen erläutert.

Unser Eingangsbild zeigt eine reale Turing-Maschine, die 2012 zur Alan-Turing-Ausstellung des HNF entstand; das Foto nahm der jetzige HNF-Geschäftsführer Dr. Jochen Viehoff auf. Weitere Hardware mit Turing-Bezug liegt im Depot; sie geht auf den einst in Münster und Bonn tätigen Logik-Professor Gisbert Hasenjaeger zurück. Wir schließen mit einer Turing-Meldung vom Sommer 2026 zu einer neu entdeckten Kurzgeschichte des Forschers. Sie ist ein kleines bisschen unanständig, wer sie dennoch lesen möchte, findet sie hier.