Q3.4 - Turingmaschine

Der Kellerautomat erweitert den endlichen Automaten um einen Stack, bleibt aber an eine bestimmte Speicherform gebunden: Zugriff gibt es nur auf das oberste Kellerelement. Fuer viele Berechnungen reicht diese Sicht nicht aus.

Eine Maschine soll Symbole nicht nur pruefen, sondern veraendern, Zwischenergebnisse festhalten, zurueckgehen, erneut lesen und am Ende ein Ergebnisband hinterlassen koennen. Die Turingmaschine modelliert genau diese allgemeinere Form schrittweiser Symbolverarbeitung.

• Aus Akzeptanz wird Verarbeitung: Eine Eingabe kann in ein Ergebnis ueberfuehrt werden.
• Aus festgelegtem Stack-Zugriff wird ein Band mit Lesen, Schreiben und Bewegung.
• Aus einzelnen Automaten fuer Sprachklassen wird ein Referenzmodell fuer algorithmische Loesbarkeit.

• Steuerwerk mit Zustaenden: endliche Menge von Arbeitszustaenden, inklusive Startzustand und Haltezustaenden.
• Band als potentiell unbegrenzter Speicher: Zellen enthalten Symbole und koennen laufend ueberschrieben werden.
• Lese-/Schreibkopf: liest aktuelles Symbol, schreibt neues Symbol und bewegt sich nach links/rechts (ggf. S fuer stehen).
• Eingabealphabet und Bandalphabet: Eingabesymbole sind Teil des Bandalphabets; zusaetzlich gibt es Hilfssymbole.
• Blank-Symbol: markiert leere Bandzellen (im Werkzeug meist _).
• Uebergangsfunktion: bestimmt aus Zustand und gelesenem Symbol den naechsten Einzelschritt.

Gegenueber dem Kellerautomaten ist das Band nicht einfach nur mehr Speicher. Es veraendert die Art des Zugriffs: Der Stack erlaubt LIFO-Zugriff auf das zuletzt abgelegte Symbol; die Turingmaschine arbeitet mit einer Kopfposition auf einem Band, liest und schreibt dort und bewegt sich kontrolliert nach links oder rechts. So wird Berechnung als veraendernde Arbeit an einer Symbolfolge modellierbar.

Das Automatendiagramm zeigt das Steuerwerk (Zustaende und Regeln), die Bandansicht zeigt den Speicherverlauf mit Kopfposition. Erst zusammen entsteht das Berechnungsmodell.

Im Turingmaschinen-Werkzeug werden Uebergangslabels kompakt im Format read/write,move dargestellt. Diese Notation ist mehr als eine Kurzschreibweise: Sie buendelt in einem Kantenlabel den elementaren Rechenschritt, den die Bandansicht danach sichtbar macht.

Das Label steht auf der Kante im Automatendiagramm, die Wirkung erscheint sofort in der Bandansicht: Symbolwechsel, Kopfbewegung und Folgezustand gehoeren untrennbar zusammen. Der Trace verbindet beide Ebenen, indem er aus einzelnen Regeln einen nachvollziehbaren Ablauf macht.

Eine Konfiguration besteht aus aktuellem Zustand, Bandinhalt und Kopfposition. Ein Schritt fuehrt genau vier Aktionen aus: lesen, schreiben, bewegen, Zustand wechseln. Der Trace ist die Folge aller Konfigurationen.

1. Aktuelles Bandsymbol lesen.
2. Passende Regel der Uebergangsfunktion waehlen.
3. Neues Symbol schreiben.
4. Kopf bewegen und Folgezustand setzen.

Die Visualisierung zeigt unmittelbar, wo der Zustand wechselt, welches Symbol unter dem Kopf gelesen wird, welche Regel aktiv ist und wie daraus der naechste Bandzustand entsteht. Genau diese Nachvollziehbarkeit macht den Trace zur didaktischen Bruecke zwischen Regeltext und Berechnungsablauf.

Eine Turingmaschine beschreibt Berechnung als Funktion auf Symbolfolgen. Bei akzeptierenden Automaten war das Ergebnis haeufig nur akzeptiert oder nicht akzeptiert. Bei einem Berechnungsmodell interessiert zusaetzlich, welches Ergebnis am Ende auf dem Band steht.

Dabei sind oft nicht alle Eingaben zugelassen oder erfolgreich berechenbar. Wenn eine Maschine fuer eine Eingabe haelt und ein Ergebnis liefert, ist die Funktion dort definiert. Wenn sie nicht haelt, ist die Funktion an dieser Stelle nicht definiert. Deshalb arbeitet man mit partiell definierten Funktionen.

• Definierte Eingaben: Die Maschine haelt und liefert das korrekte Ergebnisband.
• Nicht definierte Eingaben: Die Maschine muss nicht halten.

Diese Sicht verbindet Q3.4 mit Q3.5: Auch Registermaschinen beschreiben Berechnung ueber partielle Funktionen, nur mit anderem Speicher- und Befehlsmodell.

Die universelle Turingmaschine ist kein Bauplan fuer einen konkreten Schulcomputer, sondern ein Modellgedanke: Eine Maschine kann eine Maschinenbeschreibung und eine Eingabe lesen und den beschriebenen Lauf simulieren.

• Eine spezielle Turingmaschine loest genau eine festgelegte Verarbeitungsaufgabe.
• Eine universelle Turingmaschine erhaelt Maschinenbeschreibung + Eingabe.
• Sie simuliert dann die beschriebene Maschine auf dieser Eingabe.

Damit wird die Bruecke zur Programmierbarkeit moderner Computer sichtbar: Nicht fuer jedes Problem eine neue Hardware, sondern ein allgemeines System, das verschiedene Programme ausfuehrt.

Die Church-Turing-These ist kein beweisbarer Satz ueber alle denkbaren Verfahren, sondern eine theoretische Leitannahme: Formale Modelle wie Turingmaschine treffen den intuitiven Algorithmusbegriff.

Der Vergleich mit Registermaschine und WHILE-Programmen stuetzt diese Einordnung, weil unterschiedliche Modelle dieselbe Klasse berechenbarer Funktionen erfassen.

Gerade weil die Turingmaschine als allgemeines Berechnungsmodell dient, wird an ihr auch eine prinzipielle Grenze sichtbar: Simulieren ist nicht dasselbe wie allgemein vorhersagen.

Konkrete Maschinen kann man simulieren und ihr Verhalten Schritt fuer Schritt verfolgen. Unmoeglich ist jedoch ein allgemeines Verfahren, das fuer jede Maschine und jede Eingabe korrekt entscheidet, ob sie haelt.

Ein Werkzeug kann deshalb mit maxSteps nur praktische Laufgrenzen setzen. Das ist nuetzlich fuer Unterricht und Diagnose, loest aber das Halteproblem nicht.