Turing-Maschine

Eine Turing-Maschine ist gegeben durch ein 7-Tupel , wobei:

• ist eine endliche Zustandsmenge
• ist ein endliches Eingabealphabet
• ist ein endliches Arbeitsalphabet
• ist die Transitionsfunktion mit Signatur
  • Deterministisch:
  • Nicht-Deterministisch:
• ist das Blank-Symbol
• ist die Menge der Endzustände

Siehe auch

• Chomsky-Hierachie
• Satz von Kuroda
• LBA

Notation der Übergangsfunktion

Deterministisch:

Nicht-Deterministisch:

Definition: Konfiguration

Eine Konfiguration ist gegeben durch ein Element .

• Erstes : Buchstabe(n) links des Schreib-Lese-Kopfes
• : Aktueller Zustand
• Zweites : Buchstabe(n) rechts des Schreib-Lese-Kopfes, beginnend auf dem Kopf

Beispiel für eine Konfiguration

Dabei zeigt der Schreib-Lese-Kopf auf die

Definition: Platz- und Zeitbeschränkung

Gegeben . Eine Turing-Maschine heißt -zeitbeschränkt und -platzbeschränkt, wenn für alle gilt: