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 Turingmaschine
Der SimulatorAlle 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: TuringmaschineEine 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 AutomatenDer 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.
BeispielAuf dem Band steht die Zahl
1011, der Kopf steht auf dem zweiten Feld. Die Maschine führt den Schritt «schreibe1, gehe nach rechts» aus. Wie sieht das Band danach aus, und wo steht der Kopf?
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 für ein Feld nach rechts, 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.
BeispielDiese Maschine läuft über eine Folge von Nullen und Einsen und vertauscht dabei jede
0mit einer1. Was macht sie aus101?
Zustand gelesen schreiben Kopf neuer Zustand 01→ 10→ leerleer– halt
4.3 Eine Maschine selber bauen
BeispielEine 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 heisst: nach rechts bis zum Ende. Zustand heisst: von hinten addieren. Prüfen Sie die Tafel an der Eingabe
100.
Zustand gelesen schreiben Kopf neuer Zustand 00→ 11→ leerleer← 10← 01– halt leer1– halt
4.4 Die universelle Maschine
Eine Maschine, die alle anderen nachspieltEine 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.
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 istDas 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.1Auf dem Band steht
aab, der Kopf steht auf dem ersten Feld, Startzustand ist .
Zustand gelesen schreiben Kopf neuer Zustand ax→ bb→ 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.2Vervollständigen Sie die Tafel einer Maschine, die jedes
bdurch einaersetzt und jedesastehen lässt. Sie soll am rechten Ende der Eingabe halten.
Zustand gelesen schreiben Kopf neuer Zustand ableer
Aufgabe 4.5.3In der folgenden Tafel steckt ein Fehler: die Maschine soll wie im Beispiel jede
0mit einer1vertauschen, aber sie hält nie an. Finden Sie den Fehler und schreiben Sie die richtige Zeile auf.
Zustand gelesen schreiben Kopf neuer Zustand 01→ 10→ leerleer→
4.6 Maschinen bauen – Level A
Aufgabe 4.6.1Löschen Sie alle
1-Symbole, ersetzen Sie sie also durch ein leeres Feld.
Aufgabe 4.6.2Bit-Flip: ersetzen Sie jede
1durch eine0und jede0durch eine1.
Aufgabe 4.6.3Hängen Sie am Ende des Wortes eine
0an.
Aufgabe 4.6.4Verschieben Sie ein einzelnes Bit um ein Feld nach rechts.
Aufgabe 4.6.5Löschen Sie alle
0, lassen Sie jede1stehen, und halten Sie beim ersten leeren Feld an.
Aufgabe 4.6.6Wandeln Sie die erste
0in eine1um und halten Sie danach an.
Aufgabe 4.6.7Löschen Sie die erste
1und halten Sie danach an.
Aufgabe 4.6.8Ersetzen Sie die erste
1durch eine0, laufen Sie dann bis zum ersten leeren Feld und halten Sie an.
Aufgabe 4.6.9Löschen Sie alle Zeichen bis zum ersten leeren Feld.
Aufgabe 4.6.10Hängen Sie am Wortanfang eine
0an.
Aufgabe 4.6.11Fügen Sie am Anfang und am Ende je eine
1hinzu.
Aufgabe 4.6.12Prüfen Sie, ob mindestens eine
1im Wort steht. Schreiben Sie mit einem Feld Abstand eine1, falls ja, und sonst eine0.
Aufgabe 4.6.13Prüfen Sie, ob mindestens eine
0im Wort steht. Löschen Sie alle Zeichen und schreiben Sie danach mit einem Feld Abstand eine0, falls ja, und sonst eine1.
4.7 Maschinen bauen – Level B
Aufgabe 4.7.1Ersetzen Sie alle
1, die am Anfang unmittelbar aufeinander folgen, durch einX.
Aufgabe 4.7.2Ersetzen Sie die ersten drei Zeichen durch ein
Xund halten Sie dann an.
Aufgabe 4.7.3Ersetzen Sie jede zweite
1durch einX.
Aufgabe 4.7.4Akzeptieren Sie das Wort, wenn es eine gerade Anzahl
1enthält, und verwerfen Sie es sonst.
Aufgabe 4.7.5Akzeptieren Sie das Wort, wenn das letzte Zeichen eine
1ist, und verwerfen Sie es sonst.
Aufgabe 4.7.6Akzeptieren Sie das Wort, wenn es eine ungerade Anzahl
0enthält, und verwerfen Sie es sonst.
4.8 Maschinen bauen – Level C
Aufgabe 4.8.1Ersetzen Sie jedes dritte Bit durch ein
X.
Aufgabe 4.8.2Erhö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.
Aufgabe 4.8.3Links 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
1ersetzt werden.
Aufgabe 4.8.4Palindromtest über den Zeichen
0und1: akzeptieren Sie das Wort, wenn es vorwärts und rückwärts gleich lautet.
Weitere Aufgaben
Zusatzaufgabe 4.8.5Bauen Sie eine Maschine, die prüft, ob auf dem Band mehr
0als1stehen.
Zusatzaufgabe 4.8.6Entwerfen Sie eine Maschine, die das Band unendlich lang mit der Folge
01überschreibt.
Zusatzaufgabe 4.8.7Erstellen Sie eine Maschine, die prüft, ob das Band ausschliesslich aus abwechselnden Symbolen
0und1besteht.
Zusatzaufgabe 4.8.8Bauen Sie eine Maschine, die prüft, ob das erste und das letzte Zeichen des Bandes gleich sind.