Turingmaschine

Die Turingmaschine (TM) wurde 1936 von Alan Turing als mathematisches Modell für Berechenbarkeit eingeführt. Sie besteht aus:

• Einem unendlich langen Band, aufgeteilt in Zellen, die jeweils ein Zeichen enthalten.
• Einem Schreib-/Lesekopf, der eine Zelle lesen, beschreiben und sich nach links oder rechts bewegen kann.
• Einer endlichen Zustandsmenge Q mit einem Startzustand q₀ und akzeptierenden Endzuständen.
• Einem Bandalphabet Γ (alle Zeichen, die auf dem Band stehen können, inkl. Leerzeichen □).
• Einem Eingabealphabet Σ ⊆ Γ (Zeichen der Eingabe).
• Einer Übergangsfunktion δ: Q × Γ → Q × Γ × {L, R, N}.

Die TM arbeitet in Schritten:

1. Der Kopf liest das Zeichen unter der aktüllen Position.
2. Anhand des aktüllen Zustands und des gelesenen Zeichens bestimmt die Übergangsfunktion: neuer Zustand, neues Zeichen (wird geschrieben), Bewegungsrichtung (L/R/N).
3. Der Kopf bewegt sich und der Zustand wechselt.
4. Dies wiederholt sich, bis ein Endzustand erreicht wird (Akzeptanz) oder die TM endlos läuft (keine Terminierung).

Beispiel: TM, die prüft, ob die Eingabe eine gerade Anzahl von Einsen enthält:

Zustände: {q0, q1, q_akz}
Startzustand: q0
Akzeptierend: q_akz
Regeln:
  (q0, 1) → (q1, 1, R)    // ungerade Einsen
  (q1, 1) → (q0, 1, R)    // wieder gerade
  (q0, □) → (q_akz, □, N)  // Ende: gerade → akzeptieren
  (q1, □) → Halt (verwerfen)  // Ende: ungerade

Die Church-Turing-These (1936) ist eine der wichtigsten Annahmen der theoretischen Informatik:

„Alles, was intuitiv berechenbar ist, kann von einer Turingmaschine berechnet werden.“

Die These ist nicht bewiesen (und nicht beweisbar im mathematischen Sinne), aber bisher hat sich kein Gegenbeispiel gefunden. Sie bedeutet: Jeder Computer, jede Programmiersprache kann höchstens das berechnen, was eine Turingmaschine berechnen kann.

Eine Universelle Turingmaschine (UTM) kann jede andere Turingmaschine simulieren. Sie erhält als Eingabe:

• Die Beschreibung (Programm) einer beliebigen TM M.
• Die Eingabe w für M.

Die UTM führt dann M auf w aus und liefert dasselbe Ergebnis. Die UTM ist das theoretische Vorbild moderner Computer: Ein Computer ist eine UTM, die verschiedene Programme (TM-Beschreibungen) ausführen kann.

Das Halteproblem fragt: Gibt es ein Programm, das für jede TM M und jede Eingabe w entscheidet, ob M auf w hält?

Turing bewies 1936: Nein! Das Halteproblem ist nicht entscheidbar (unlösbar). Es gibt keinen Algorithmus, der für alle Programme und Eingaben korrekt vorhersagen kann, ob das Programm terminiert oder endlos läuft.

Abitur-Tipp: Im Abitur wird häufig verlangt, eine einfache TM zu konstruieren (z. B. für Binäraddition oder Zeichenerkennung) oder die Arbeitsweise einer gegebenen TM Schritt für Schritt nachzuvollziehen. Präge dir die Bestandteile (Band, Kopf, Zustände, Übergangsfunktion) und die Church-Turing-These ein. Das Halteproblem ist ein beliebtes Thema für Verständnisfragen.