Turingmaschinen erklärt

1936, bevor es elektronische Computer gab, fragte der 24-jährige Mathematiker Alan Turing, was es heißt, dass eine Rechnung mechanisch ist. Seine Antwort war eine gedachte Maschine, so einfach, dass sie kaum weniger tun könnte: Sie liest und schreibt Symbole auf einem Band, eine Zelle nach der anderen, nach einer festen Tabelle von Regeln. Diese Maschine erwies sich als Definition des Berechnens selbst, und sie zeigte, dass manche Fragen von überhaupt keinem Computer je beantwortet werden können.

Ein Band aus Zellen mit Einsen und leeren Zellen, darüber ein Schreib-Lese-Kopf über einer Zelle, beschriftet mit seinem Zustand
Ein Band aus Zellen mit Einsen und leeren Zellen, darüber ein Schreib-Lese-Kopf über einer Zelle, beschriftet mit seinem Zustand

Turings Frage

1928 fragte David Hilbert, ob es ein mechanisches Verfahren gibt, das für jede mathematische Aussage entscheidet, ob sie beweisbar ist: das Entscheidungsproblem. Um es zu beantworten, musste jemand genau sagen, was ein mechanisches Verfahren ist. In seiner Arbeit On Computable Numbers von 1936 stellte sich Turing einen Schreiber vor, der mit Bleistift und Papier arbeitet, und zerlegte die Arbeit in ihre kleinsten Schritte: ein Symbol ansehen, es ändern, zu einem benachbarten Symbol gehen und sich ein wenig merken, womit man gerade beschäftigt war. Das Ergebnis war die Turingmaschine.

Eine Bombe-Maschine (links) und ein Porträt von Alan Turing (rechts)
Eine Bombe-Maschine (links) und ein Porträt von Alan Turing (rechts)

Die Maschine

Eine Turingmaschine hat ein in Zellen unterteiltes Band, das in beide Richtungen endlos ist; jede Zelle enthält ein Symbol, meist das Leerzeichen. Ein Kopf steht auf einer Zelle, und die Maschine befindet sich in einem von endlich vielen Zuständen. Eine Tabelle von Regeln gibt für jeden Zustand und jedes Symbol, das der Kopf lesen kann, das zu schreibende Symbol, die Bewegungsrichtung und den nächsten Zustand an. Die Maschine wendet pro Schritt eine Regel an. Wenn sie einen Haltezustand erreicht, hält sie an, und was auf dem Band übrig bleibt, ist ihre Antwort.

Programme als Regeltabellen

Jede Regeltabelle ist ein Programm. Um 1 zu einer Binärzahl zu addieren, läuft die Maschine zum rechten Ende der Zahl und bewegt sich dann nach links, wobei sie Einsen in Nullen verwandelt, bis sie eine 0 oder eine leere Zelle findet, die sie in eine 1 verwandelt. Um zu prüfen, ob ein Wort ein Palindrom ist, löscht sie das erste Symbol, merkt es sich in ihrem Zustand, läuft zum anderen Ende und prüft, ob das letzte Symbol passt, und wiederholt das Ganze. Lange Programme, etwa eines, das multipliziert oder sortiert, sind aus denselben wenigen Arten von Regeln aufgebaut.

Die universelle Maschine

Turings wichtigste Idee war, dass die Regeltabelle selbst auf das Band geschrieben werden kann. Eine universelle Turingmaschine liest die Beschreibung einer beliebigen anderen Maschine und deren Eingabe und ahmt sie dann Schritt für Schritt nach. Eine einzige feste Maschine kann also jedes Programm ausführen: Das ist das Prinzip hinter jedem speicherprogrammierten Computer, in dem Software nur Daten im Speicher sind. Jedes System, das eine universelle Turingmaschine nachahmen kann, heißt Turing-vollständig, darunter jede Programmiersprache, Conways Game of Life und der zelluläre Automat Rule 110.

Die Church-Turing-These

Im selben Jahr beschrieb Alonzo Church das Berechnen mit seinem Lambda-Kalkül, und es stellte sich heraus, dass beide Definitionen genau dieselben Funktionen berechnen. Dasselbe galt für jedes spätere Modell, von Registermaschinen bis zu modernen Prozessoren. Die Church-Turing-These besagt, dass alles, was sich durch ein schrittweises Verfahren berechnen lässt, von einer Turingmaschine berechnet werden kann. Beweisen lässt sie sich nicht, weil „schrittweises Verfahren“ ein informeller Begriff ist, aber ein Gegenbeispiel wurde nie gefunden.

Das Halteproblem

Dann zeigte Turing, dass manche Fragen keine mechanische Antwort haben. Angenommen, eine Maschine könnte für jedes Programm und jede Eingabe entscheiden, ob dieses Programm irgendwann anhält. Man baut ein neues Programm, das diesen Entscheider nach sich selbst fragt und dann das Gegenteil tut: Heißt es, es halte an, läuft es endlos weiter, und heißt es, es laufe endlos, hält es an. Beide Antworten sind falsch, also kann es den Entscheider nicht geben. Das Halteproblem ist unentscheidbar, und mit ihm das Entscheidungsproblem: Kein Algorithmus kann jede mathematische Frage klären.

Fleißige Biber

1962 machte Tibor Radó aus dem Halteproblem ein Spiel: Welche unter allen Maschinen mit n Zuständen und den Symbolen 0 und 1, die auf einem leeren Band gestartet anhalten, schreibt die meisten Einsen, und wie viele Schritte kann eine solche Maschine machen? Diese Zahlen, die Werte der fleißigen Biber, wachsen schneller als jede berechenbare Funktion, denn ein Weg, sie zu berechnen, würde das Halteproblem lösen. Die bekannten Werte sind 6, 21 und 107 Schritte für zwei, drei und vier Zustände; bei fünf Zuständen braucht der Champion von Heiner Marxen und Jürgen Buntrock 47.176.870 Schritte, ein Wert, der 2024 von der Online-Zusammenarbeit bbchallenge mit einem computergeprüften Beweis bewiesen wurde. Für sechs Zustände kennt man Maschinen, die mehr Schritte laufen, als sich in gewöhnlicher Schreibweise aufschreiben lässt.

Selbst ausprobieren

Öffnen Sie den Turingmaschinen-Simulator, um acht fertige Programme auszuführen oder eigene zu schreiben. Folgen Sie dem Kopf Schritt für Schritt und sehen Sie, welche Regel greift, beobachten Sie den Zähler, der nie anhält, prüfen Sie Palindrome und lassen Sie die fleißigen Biber laufen: Die 107 Schritte des Champions mit vier Zuständen passen ins Diagramm, und die 47 Millionen Schritte des Champions mit fünf Zuständen dauern auf der Stufe „Sehr schnell“ wenige Sekunden.

Häufig gestellte Fragen

Wurde die Turingmaschine je gebaut?

Nicht so, wie Turing sie beschrieb, denn ihr Band ist endlos, aber auf die Idee folgten bald echte speicherprogrammierte Computer, an deren Entwurf Turing nach dem Zweiten Weltkrieg selbst mitwirkte. Bastler haben seitdem funktionierende Modelle aus Holz, aus LEGO und sogar im Game of Life gebaut, alle mit endlichem Band, was für jede Rechnung genügt, die zu einem Ende kommt.

Was ist der Unterschied zwischen den Schrittzahlen 14 und 21 bei drei Zuständen?

Es gibt zwei Fragen zu fleißigen Bibern: die meisten geschriebenen Einsen und die meisten ausgeführten Schritte. Bei drei Zuständen schreibt die Maschine im Simulator das Maximum von sechs Einsen in 14 Schritten, während eine andere Maschine mit drei Zuständen das Maximum von 21 Schritten braucht, aber nur fünf Einsen hinterlässt. Bei zwei, vier und fünf Zuständen gewinnt eine einzige Maschine beides.

Heißt Turing-vollständig auch leistungsfähig?

Es heißt, alles Berechenbare berechnen zu können, sofern genug Zeit und Speicher vorhanden sind, und sagt nichts über die Geschwindigkeit aus. Eine Turingmaschine braucht für einfache Arithmetik viele Schritte, und manche Systeme sind fast zufällig Turing-vollständig, etwa Kartenspiele, Tabellenkalkulationsformeln und Redstone in Minecraft.

Warum kann ein Computer nicht einfach ein Programm laufen lassen, um zu sehen, ob es anhält?

Das Laufenlassen zeigt, dass ein Programm anhält, falls es das tut; hat es aber noch nicht angehalten, kann man nicht sagen, ob es nie anhalten wird oder nur mehr Zeit braucht. Turings Beweis zeigt, dass keine klügere Methode für jedes Programm funktioniert, auch wenn sich die Frage für viele einzelne Programme beantworten lässt.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Turingmaschinen-Simulator öffnen