Nach einem Skript von Philipp Moor (Kantonsschule Zimmerberg).

Lernziele
  • Band, Kopf und Zustand einer Turingmaschine benennen
  • Eine Turingtafel lesen und Schritt für Schritt ausführen
  • Zu einer Turingtafel und einer Eingabe das Band am Schluss angeben
  • Eine einfache Turingmaschine selber bauen
  • Erklären, was eine universelle Maschine ist und warum sie wichtig ist
Titelbild TuringmaschineTitelbild Turingmaschine
Der Simulator

Alle Maschinen in diesem Teil lassen sich im Browser ausprobieren, ohne Installation und ohne Java:

Man gibt dort die Turingtafel ein, schreibt die Eingabe aufs Band und lässt die Maschine Schritt für Schritt oder am Stück laufen. Wer eine Aufgabe von Hand gelöst hat, prüft sie damit in einer halben Minute.

4 Die Turingmaschine

4.1 Band, Kopf und Zustand

Dem endlichen Automaten fehlte ein Speicher, der beliebig gross werden darf. Alan Turing hat 1936 aufgeschrieben, wie wenig man hinzufügen muss, damit dieser Mangel verschwindet: einen Papierstreifen und einen Stift.

Definition: Turingmaschine

Eine Turingmaschine rechnet auf einem Band. Das Band ist in Felder eingeteilt und nach beiden Seiten so lang, wie es sein muss. Auf jedem Feld steht ein Zeichen, oder das Feld ist leer. Ein Kopf steht immer auf genau einem Feld. Er liest das Zeichen dort, schreibt eines hin und rückt dann um ein Feld weiter.

Eine Turingmaschine besteht aus fünf Teilen:

Der Unterschied zum endlichen Automaten

Der endliche Automat liest jedes Zeichen genau einmal und von links nach rechts. Die Turingmaschine darf zurückgehen, nochmals lesen und dazwischen etwas hinschreiben. Damit hat sie einen Speicher, der mit der Aufgabe mitwächst. Genau das fehlte in Teil 2.

Beispiel

Auf dem Band steht die Zahl 1011, der Kopf steht auf dem zweiten Feld. Die Maschine führt den Schritt «schreibe 1, gehe nach rechts» aus. Wie sieht das Band danach aus, und wo steht der Kopf?

Band 1011, Kopf auf dem zweiten FeldBand 1011, Kopf auf dem zweiten Feld

4.2 Die Turingtafel

Die Turingtafel ist eine gewöhnliche Tabelle. Jede Zeile beantwortet die Frage: was tue ich, wenn ich in diesem Zustand dieses Zeichen lese? Für den Kopf schreiben wir →\rightarrow für ein Feld nach rechts, ←\leftarrow für ein Feld nach links und einen Strich, wenn er stehen bleibt. Ein leeres Feld bezeichnen wir mit dem Wort leer.

In der Zeile, die zum Haltezustand führt, bleibt der Kopf stehen. Er steht dann auf dem Feld, an dem die Maschine gemerkt hat, dass sie fertig ist, also meist auf dem ersten leeren Feld hinter dem Wort.

Dieselbe Maschine lässt sich auch als Zustandsdiagramm zeichnen, genau wie die Automaten in den Teilen 1 und 2. An jedem Pfeil steht dann eine ganze Zeile der Tafel, in der Form gelesen | schreiben, Kopf; für das leere Feld steht dort kurz _. Grau hinterlegt ist der Zustand, in dem die Maschine anhält. Tafel und Diagramm sagen dasselbe; die Tafel ist zum Rechnen bequemer, das Diagramm zeigt den Aufbau auf einen Blick.

Beispiel

Diese Maschine läuft über eine Folge von Nullen und Einsen und vertauscht dabei jede 0 mit einer 1. Was macht sie aus 101?

ZustandgelesenschreibenKopfneuer Zustand
q0q_{0}01→q0q_{0}
q0q_{0}10→q0q_{0}
q0q_{0}leerleer–halt
Zustandsdiagramm der MaschineZustandsdiagramm der Maschine

4.3 Eine Maschine selber bauen

Beispiel

Eine Maschine soll eine Binärzahl um eins erhöhen. Sie muss dazu erst ans rechte Ende laufen und dann von hinten nach vorn addieren, mit Übertrag. Zustand q0q_0 heisst: nach rechts bis zum Ende. Zustand q1q_1 heisst: von hinten addieren. Prüfen Sie die Tafel an der Eingabe 100.

ZustandgelesenschreibenKopfneuer Zustand
q0q_{0}00→q0q_{0}
q0q_{0}11→q0q_{0}
q0q_{0}leerleer←q1q_{1}
q1q_{1}10←q1q_{1}
q1q_{1}01–halt
q1q_{1}leer1–halt
Zustandsdiagramm der MaschineZustandsdiagramm der Maschine

4.4 Die universelle Maschine

Eine Maschine, die alle anderen nachspielt

Eine Turingtafel ist selbst nichts anderes als eine Folge von Zeichen. Man kann sie also auf ein Band schreiben. Turing hat 1936 eine Maschine angegeben, die genau das ausnutzt. Sie bekommt auf ihrem Band zwei Dinge: die Beschreibung einer beliebigen anderen Turingmaschine und deren Eingabe. Dann spielt sie Schritt für Schritt nach, was die beschriebene Maschine täte.

Band mit der Beschreibung einer Maschine (violett) und ihrer Eingabe (grün)Band mit der Beschreibung einer Maschine (violett) und ihrer Eingabe (grün)

Eine einzige Maschine kann damit alles, was irgendeine Turingmaschine kann. Man muss sie nicht umbauen, sondern nur ihr Band neu beschreiben. Turing nennt sie die universelle Maschine.

Warum das der wichtigste Satz des Skripts ist

Das ist die Idee, auf der jeder Computer beruht: Programm und Daten liegen im selben Speicher, und dieselbe Maschine führt heute ein Spiel und morgen eine Tabellenkalkulation aus. Turing hat das 1936 aufgeschrieben, neun Jahre bevor der erste solche Rechner gebaut wurde.

4.5 Aufgaben zum Lesen

Aufgabe 4.5.1

Auf dem Band steht aab, der Kopf steht auf dem ersten Feld, Startzustand ist q0q_0.

ZustandgelesenschreibenKopfneuer Zustand
q0q_{0}ax→q0q_{0}
q0q_{0}bb→q0q_{0}
q0q_{0}leerleer–halt

Schreiben Sie Schritt für Schritt auf, was auf dem Band steht und wo der Kopf ist. Was steht am Schluss da?

Aufgabe 4.5.2

Vervollständigen Sie die Tafel einer Maschine, die jedes b durch ein a ersetzt und jedes a stehen lässt. Sie soll am rechten Ende der Eingabe halten.

ZustandgelesenschreibenKopfneuer Zustand
q0q_0a
q0q_0b
q0q_0leer
Aufgabe 4.5.3

In der folgenden Tafel steckt ein Fehler: die Maschine soll wie im Beispiel jede 0 mit einer 1 vertauschen, aber sie hält nie an. Finden Sie den Fehler und schreiben Sie die richtige Zeile auf.

ZustandgelesenschreibenKopfneuer Zustand
q0q_{0}01→q0q_{0}
q0q_{0}10→q0q_{0}
q0q_{0}leerleer→q0q_{0}

4.6 Maschinen bauen – Level A

Aufgabe 4.6.1

Löschen Sie alle 1-Symbole, ersetzen Sie sie also durch ein leeres Feld.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.2

Bit-Flip: ersetzen Sie jede 1 durch eine 0 und jede 0 durch eine 1.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.3

Hängen Sie am Ende des Wortes eine 0 an.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.4

Verschieben Sie ein einzelnes Bit um ein Feld nach rechts.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.5

Löschen Sie alle 0, lassen Sie jede 1 stehen, und halten Sie beim ersten leeren Feld an.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.6

Wandeln Sie die erste 0 in eine 1 um und halten Sie danach an.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.7

Löschen Sie die erste 1 und halten Sie danach an.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.8

Ersetzen Sie die erste 1 durch eine 0, laufen Sie dann bis zum ersten leeren Feld und halten Sie an.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.9

Löschen Sie alle Zeichen bis zum ersten leeren Feld.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.10

Hängen Sie am Wortanfang eine 0 an.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.11

Fügen Sie am Anfang und am Ende je eine 1 hinzu.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.6.12

Prüfen Sie, ob mindestens eine 1 im Wort steht. Schreiben Sie mit einem Feld Abstand eine 1, falls ja, und sonst eine 0.

Band am Start und am Ende, Wort mit einer 1Band am Start und am Ende, Wort mit einer 1Band am Start und am Ende, Wort ohne 1Band am Start und am Ende, Wort ohne 1
Aufgabe 4.6.13

Prüfen Sie, ob mindestens eine 0 im Wort steht. Löschen Sie alle Zeichen und schreiben Sie danach mit einem Feld Abstand eine 0, falls ja, und sonst eine 1.

Band am Start und am Ende, Wort mit einer 0Band am Start und am Ende, Wort mit einer 0Band am Start und am Ende, Wort ohne 0Band am Start und am Ende, Wort ohne 0

4.7 Maschinen bauen – Level B

Aufgabe 4.7.1

Ersetzen Sie alle 1, die am Anfang unmittelbar aufeinander folgen, durch ein X.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.7.2

Ersetzen Sie die ersten drei Zeichen durch ein X und halten Sie dann an.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.7.3

Ersetzen Sie jede zweite 1 durch ein X.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.7.4

Akzeptieren Sie das Wort, wenn es eine gerade Anzahl 1 enthält, und verwerfen Sie es sonst.

Ein Band, das akzeptiert wird, und eines, das verworfen wirdEin Band, das akzeptiert wird, und eines, das verworfen wird
Aufgabe 4.7.5

Akzeptieren Sie das Wort, wenn das letzte Zeichen eine 1 ist, und verwerfen Sie es sonst.

Ein Band, das akzeptiert wird, und eines, das verworfen wirdEin Band, das akzeptiert wird, und eines, das verworfen wird
Aufgabe 4.7.6

Akzeptieren Sie das Wort, wenn es eine ungerade Anzahl 0 enthält, und verwerfen Sie es sonst.

Ein Band, das akzeptiert wird, und eines, das verworfen wirdEin Band, das akzeptiert wird, und eines, das verworfen wird

4.8 Maschinen bauen – Level C

Aufgabe 4.8.1

Ersetzen Sie jedes dritte Bit durch ein X.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.8.2

Erhöhen Sie eine Binärzahl um eins. Die Maschine aus Unterkapitel 4.3 löst die Aufgabe; prüfen Sie sie an dieser Eingabe, bei der der Übertrag ganz durchläuft.

Band am Start und am EndeBand am Start und am Ende
Aufgabe 4.8.3

Links und rechts von einem leeren Feld steht je ein Wort. Steht links eine gerade Anzahl Zeichen, so soll das rechte Wort gelöscht werden; steht dort eine ungerade Anzahl, so sollen alle Zeichen rechts durch eine 1 ersetzt werden.

Band am Start und am Ende, links eine gerade Anzahl ZeichenBand am Start und am Ende, links eine gerade Anzahl ZeichenBand am Start und am Ende, links eine ungerade Anzahl ZeichenBand am Start und am Ende, links eine ungerade Anzahl Zeichen
Aufgabe 4.8.4

Palindromtest über den Zeichen 0 und 1: akzeptieren Sie das Wort, wenn es vorwärts und rückwärts gleich lautet.

Ein Band, das akzeptiert wird, und eines, das verworfen wirdEin Band, das akzeptiert wird, und eines, das verworfen wirdEin Band, das akzeptiert wird, und eines, das verworfen wirdEin Band, das akzeptiert wird, und eines, das verworfen wird

Weitere Aufgaben

Zusatzaufgabe 4.8.5

Bauen Sie eine Maschine, die prüft, ob auf dem Band mehr 0 als 1 stehen.

Zusatzaufgabe 4.8.6

Entwerfen Sie eine Maschine, die das Band unendlich lang mit der Folge 01 überschreibt.

Zusatzaufgabe 4.8.7

Erstellen Sie eine Maschine, die prüft, ob das Band ausschliesslich aus abwechselnden Symbolen 0 und 1 besteht.

Zusatzaufgabe 4.8.8

Bauen Sie eine Maschine, die prüft, ob das erste und das letzte Zeichen des Bandes gleich sind.