Was ist eine Turingmaschine?
Was heißt eigentlich „berechenbar“?
Bei der Geburt der modernen Informatik stand eine Frage im Mittelpunkt: Was genau ist ein Algorithmus, also ein Verfahren, das man Schritt für Schritt ausführen kann, ohne nachzudenken? In den 1930er Jahren gaben Logiker wie Gödel, Church, Post und Turing darauf Antworten. Ihre Ansätze sahen völlig verschieden aus, stellten sich aber als gleich mächtig heraus. Das führte zur Church’schen These: Alles, was sich überhaupt berechnen lässt, lässt sich mit jedem dieser Modelle berechnen.
Besonders anschaulich ist das Modell von Alan Turing, die Turingmaschine. Sie ist unserer imperativen Programmierung sehr nahe. Mit ihr untersuchen wir in diesem Thema, wo die Grenzen des Berechenbaren liegen.
Quelle der Abbildungen: Wikipedia
Aufgabe 1: Video
Schau dir das Video zur Turingmaschine an und beantworte danach die Frage.
Das Video liegt bei YouTube und öffnet sich in einem neuen Tab.
Bestandteile einer Turingmaschine
Die Maschinen aus dem Einstieg waren Turingmaschinen. Eine Turingmaschine (mit einem Band) besteht aus
- einem nach links und rechts unbegrenzten Band, das in Felder eingeteilt ist. In jedem Feld steht ein Zeichen aus einem festgelegten Vorrat – bei uns
0,1oder nichts (das Blank, geschrieben#); - einem Schreib-/Lesekopf, der immer über genau einem Feld steht. Er liest das Zeichen dort, schreibt ein Zeichen hinein und bewegt sich ein Feld nach links oder rechts;
- einer Steuereinheit, die sich immer in einem bestimmten Zustand befindet. Was sie tut, legt ein Programm fest, die Transitionstabelle.
Die Anzeige aus dem Einstieg war also der Zustand der Maschine.
Ein Arbeitsschritt
Ausgehend vom aktuellen Zustand arbeitet die Turingmaschine in jedem Schritt so:
- Sie liest das Zeichen unter dem Schreib-/Lesekopf.
- In der Transitionstabelle sucht sie die Regel für aktuellen Zustand und gelesenes Zeichen.
- Sie schreibt das neue Zeichen (das kann auch dasselbe sein).
- Sie wechselt in den neuen Zustand (das kann auch derselbe sein).
- Sie bewegt den Kopf ein Feld nach links (
L) oder rechts (R).
Erreicht sie den Endzustand (bei uns h wie halt), hält sie an. Sie hält auch, wenn es für Zustand und Zeichen gar keine Regel gibt.
Zum Weiterlesen: die formale Definition
Formal ist eine Turingmaschine ein 7-Tupel TM = (Z, Σ, Γ, z0, #, ze, δ) mit
- einer endlichen Zustandsmenge Z,
- dem Eingabealphabet Σ (bei uns {0; 1}),
- dem Bandalphabet Γ ⊃ Σ (bei uns {0; 1; #}),
- dem Startzustand z0 ∈ Z,
- dem Blank # ∈ Γ \ Σ,
- dem Endzustand ze ∈ Z und
- der Überführungsfunktion δ: Jedem Paar (z, γ) aus Zustand und gelesenem Zeichen wird ein Tripel (γ′, z′, a) aus neuem Zeichen, neuem Zustand und Bewegung a ∈ {L, R} zugeordnet. In der Tabelle wird daraus das 5-Tupel (z, γ, γ′, z′, a).
Für den Unterricht reicht eine klare Vorstellung von der Arbeitsweise; die formale Definition verlangt der Lehrplan nicht.
Vereinbarungen laut Lehrplan
- Wir betrachten nur deterministische Turingmaschinen: Für jedes Paar aus Zustand und Zeichen gibt es höchstens eine Regel.
- Auf dem Band stehen nur
0und1(und leere Felder). Die 0 steht für den Wahrheitswert false, die 1 für true. - Eine natürliche Zahl n wird durch n aufeinanderfolgende Einsen dargestellt. Stehen mehrere Zahlen auf dem Band, trennt sie eine
0. - Zu Beginn und am Ende steht der Kopf unter dem am weitesten rechts stehenden Zeichen der Eingabe bzw. der Ausgabe. Eingaben und Zwischenergebnisse dürfen stehen bleiben.
- Programme werden als Transitionstabelle notiert. Die Tabelle muss nicht für jedes Paar eine Regel enthalten.
| Zustand | Zeichen | neues Zeichen | neuer Zustand | Bewegung |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | L |
Tipp: Beim Entwickeln einer Tabelle hilft ein Zustandsdiagramm. Jeder Zustand ist ein Kreis, jede Regel ein Pfeil, beschriftet mit gelesenes Zeichen ; neues Zeichen , Bewegung.
Die Maschinen vom Einstieg – jetzt mit Programm
Hier sind die Maschinen A und B noch einmal, diesmal mit ihrer Transitionstabelle und ihrem Zustandsdiagramm. Lass sie schrittweise laufen. Die Regel, die als Nächstes angewendet wird, ist blau hinterlegt, die zuletzt angewendete gelb.
Beschreibe die Aufgabe jedes Zustands von Maschine A in einem Satz, zum Beispiel: „Zustand 5 sucht den rechten Rand und verändert nichts.“
Welche Regel sorgt dafür, dass Maschine A am linken Rand des Bandinhalts umkehrt?
Maschine B braucht drei Zustände, obwohl sie nur eine 1 anhängt. Warum reichen zwei nicht?
Aufgabe 2: Vom Zustandsdiagramm zur Tabelle
Das folgende Zustandsdiagramm wurde mit dem Programm JFLAP erstellt. Die Bewegung N bedeutet: Der Kopf bleibt stehen.
- Übertrage das Diagramm Regel für Regel in die Transitionstabelle des Simulators. Arbeite die Zustände in der Reihenfolge 0, 1, h ab und beginne jeweils mit der Regel für #.
- Der Simulator meldet ein Problem. Beantworte dazu die Frage unter dem Simulator.
- Ändere die Tabelle so, dass die Maschine laut Lehrplan arbeitet, und teste sie mit
111.
Ohne Anmeldung wird deine Maschine nicht gespeichert. „Maschinen merken“ und „Datei speichern“ funktionieren trotzdem.
Ist die Maschine aus dem Diagramm deterministisch?
Welche Aufgabe erfüllt die Maschine (ohne die Regel mit N) bei der Bandbelegung #111#? Der Kopf startet unter der rechten 1.