Turingmaschine

Version vom 8. November 2026, 09:16 Uhr von Flbkwikiadmin (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „Die Turingmaschine ist das einfachste Modell, das alles berechnen kann, was ein Computer berechnen kann. Sie zeigt auch, wo diese Grenzen liegen. ==Definition== Eine Turingmaschine ist ein 7-Tupel <math>M = (Q, \Sigma, \Gamma, \delta, q0, \square, F)</math>: * <math>Q</math> ist die endliche, nicht leere Zustandsmenge. * <math>\Sigma</math> ist das Eingabealphabet. * <math>\Gamma</math> ist das Bandalphabet mit <math>\Sigma \subset \Gamma</…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

Die Turingmaschine ist das einfachste Modell, das alles berechnen kann, was ein Computer berechnen kann. Sie zeigt auch, wo diese Grenzen liegen.

Definition

Eine Turingmaschine ist ein 7-Tupel [math]\displaystyle{ M = (Q, \Sigma, \Gamma, \delta, q0, \square, F) }[/math]:

  • [math]\displaystyle{ Q }[/math] ist die endliche, nicht leere Zustandsmenge.
  • [math]\displaystyle{ \Sigma }[/math] ist das Eingabealphabet.
  • [math]\displaystyle{ \Gamma }[/math] ist das Bandalphabet mit [math]\displaystyle{ \Sigma \subset \Gamma }[/math].
  • [math]\displaystyle{ \delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\} }[/math] ist die Übergangsfunktion.
  • [math]\displaystyle{ q0 \in Q }[/math] ist der Startzustand.
  • [math]\displaystyle{ \square \in \Gamma \setminus \Sigma }[/math] ist das Leerzeichen.
  • [math]\displaystyle{ F \subseteq Q }[/math] ist die Menge der Endzustände.

Die Maschine arbeitet auf einem unbegrenzten Band, dessen Felder je ein Zeichen aus [math]\displaystyle{ \Gamma }[/math] tragen. Ein Lese-Schreib-Kopf steht auf genau einem Feld.

Arbeitsweise

Zu Beginn steht die Eingabe auf dem Band, alle übrigen Felder tragen [math]\displaystyle{ \square }[/math]. Die Maschine startet in q0, der Kopf steht auf dem ersten Zeichen der Eingabe.

Der Kopf liest ein Feld. Die Übergangsfunktion legt dann das Zeichen fest, das auf das Feld geschrieben wird, die Bewegung des Kopfes um ein Feld nach links (L) oder rechts (R) und den Folgezustand. Die Maschine hält in einem Endzustand oder wenn für den Zustand und das gelesene Zeichen kein Übergang definiert ist.

Entscheidbarkeit

Die These von Church und Turing besagt: Was überhaupt berechenbar ist, kann eine Turingmaschine berechnen. Ein Problem heißt entscheidbar, wenn eine Turingmaschine bei jeder Eingabe hält und mit ja oder nein antwortet.

Unentscheidbar ist das Halteproblem. Es fragt, ob ein Programm bei einer Eingabe irgendwann hält. Beweisidee: Angenommen, es gäbe ein Programm H, das für jedes Programm p und jede Eingabe e entscheidet, ob p bei e hält. Dann ließe sich ein Programm D bauen. D erhält ein Programm p und fragt H, ob p bei der Eingabe p hält. Antwortet H mit „hält“, läuft D endlos. Antwortet H mit „hält nicht“, hält D.

Wird D auf sich selbst angewendet, widerspricht jede Antwort von H. Sagt H, dass D bei der Eingabe D hält, läuft D endlos. Sagt H, dass D nicht hält, hält D. Also kann es H nicht geben.

Eine Folge: Kein Werkzeug findet alle Endlosschleifen.

Beispiele

Bits invertieren

Die Turingmaschine ersetzt jede 0 durch 1 und jede 1 durch 0. Sie hat die Zustände q0 (Startzustand) und q1 (Endzustand), das Eingabealphabet [math]\displaystyle{ \Sigma = \{0, 1\} }[/math] und das Bandalphabet [math]\displaystyle{ \Gamma = \{0, 1, \square\} }[/math]. Das Zeichen □ steht für das Leerzeichen.

Zustand liest schreibt bewegt Folgezustand
q0 0 1 R q0
q0 1 0 R q0
q0 □ □ L q1
 
Band, Zustand und Kopfposition beim Lauf für die Eingabe 10

Lauf für die Eingabe 10:

  1. q0 liest 1, schreibt 0 und geht nach rechts.
  2. q0 liest 0, schreibt 1 und geht nach rechts.
  3. q0 liest □, schreibt □ und geht nach links in q1. q1 ist ein Endzustand, die Maschine hält.

Das Ergebnis auf dem Band ist 01.