Turing Machine Einführung
Eine Turingmaschine ist ein akzeptierendes Gerät, das die Sprachen (rekursiv aufzählbare Menge) akzeptiert, die durch Grammatiken vom Typ 0 erzeugt werden. Es wurde 1936 von Alan Turing erfunden.
Definition
Eine Turing-Maschine (TM) ist ein mathematisches Modell, das aus einem Band mit unendlicher Länge besteht, das in Zellen unterteilt ist, auf denen Eingaben erfolgen. Es besteht aus einem Kopf, der das Eingabeband liest. Ein Zustandsregister speichert den Zustand der Turingmaschine. Nach dem Lesen eines Eingabesymbols wird es durch ein anderes Symbol ersetzt, sein interner Status wird geändert und es bewegt sich von einer Zelle nach rechts oder links. Wenn das TM den Endzustand erreicht, wird die Eingabezeichenfolge akzeptiert, andernfalls abgelehnt.
Ein TM kann formal als 7-Tupel (Q, X, ∑, δ, q 0 , B, F) beschrieben werden, wobei -
Q ist eine endliche Menge von Zuständen
X ist das Bandalphabet
∑ ist das Eingabealphabet
δist eine Übergangsfunktion; δ: Q × X → Q × X × {Linksverschiebung, Rechtsverschiebung}.
q0 ist der Ausgangszustand
B ist das leere Symbol
F ist die Menge der Endzustände
Vergleich mit dem vorherigen Automaten
Die folgende Tabelle zeigt einen Vergleich der Unterschiede zwischen einer Turing-Maschine und einem endlichen Automaten und einem Pushdown-Automaten.
Maschine | Stack-Datenstruktur | Deterministisch? |
---|---|---|
Endlicher Automat | N / A | Ja |
Pushdown-Automat | Last In First Out (LIFO) | Nein |
Turing Maschine | Unendliches Band | Ja |
Beispiel einer Turingmaschine
Turingmaschine M = (Q, X, ∑, δ, q 0 , B, F) mit
- Q = {q 0 , q 1 , q 2 , q f }
- X = {a, b}
- ∑ = {1}
- q 0 = {q 0 }
- B = leeres Symbol
- F = {q f }
δ ist gegeben durch -
Bandalphabetsymbol | Gegenwärtiger Zustand 'q 0 ' | Gegenwärtiger Zustand 'q 1 ' | Gegenwärtiger Zustand 'q 2 ' |
---|---|---|---|
ein | 1Rq 1 | 1Lq 0 | 1Lq f |
b | 1Lq 2 | 1Rq 1 | 1Rq f |
Hier impliziert der Übergang 1Rq 1 , dass das Schreibsymbol 1 ist, das Band sich nach rechts bewegt und der nächste Zustand q 1 ist . In ähnlicher Weise impliziert der Übergang 1Lq 2 , dass das Schreibsymbol 1 ist, das Band sich nach links bewegt und der nächste Zustand q 2 ist .
Zeit- und Raumkomplexität einer Turingmaschine
Bei einer Turing-Maschine bezieht sich die zeitliche Komplexität auf das Maß dafür, wie oft sich das Band bewegt, wenn die Maschine für einige Eingabesymbole initialisiert wird, und die räumliche Komplexität ist die Anzahl der Zellen des geschriebenen Bandes.
Zeitkomplexität alle vernünftigen Funktionen -
T(n) = O(n log n)
TMs Raumkomplexität -
S(n) = O(n)