Eine Turingmaschine ist ein akzeptierendes Gerät, das die von Typ-0-Grammatiken erzeugten Sprachen (rekursiv aufzählbare Menge) annimmt. Sie wurde 1936 von Alan Turing erfunden.
Definition
Eine Turing-Maschine (TM) ist ein mathematisches Modell, das aus einem unendlich langen Band besteht, das in Zellen unterteilt ist, auf die eine Eingabe gegeben wird. Sie besteht aus einem Kopf, der das Eingabeband liest. Ein Zustandsregister speichert den Zustand der Turingmaschine. Nach dem Lesen eines Eingabesymbols wird dieses durch ein anderes Symbol ersetzt, ihr interner Zustand wird geändert, und sie bewegt sich von einer Zelle nach rechts oder links. Erreicht die TM den Endzustand, wird der Eingabestring akzeptiert, andernfalls verworfen.
Ein TM kann formal als 7-Tupel (Q, X, ∑, δ, q0, B, F) beschrieben werden, wobei –
-
Q eine endliche Menge von Zuständen ist
-
X ist das Bandalphabet
-
∑ ist das Eingabealphabet
-
δ ist eine Übergangsfunktion; δ : Q × X → Q × X × {Left_shift, Right_shift}.
-
q0 ist der Anfangszustand
-
B ist das Leersymbol
-
F ist die Menge der Endzustände
Vergleich mit dem vorherigen Automaten
Die folgende Tabelle zeigt einen Vergleich, wie sich ein Turing-Automat von einem Finiten Automaten und einem Pushdown-Automaten unterscheidet.
| Maschine | Stapel-Datenstruktur | Deterministisch? |
|---|---|---|
| Finiter Automaton | N.A | Ja |
| Pushdown Automaton | Last In First Out(LIFO) | Nein |
| Turing Maschine | Unendliches Band | Ja |
Beispiel für Turingmaschine
Turingmaschine M = (Q, X, ∑, δ, q0, B, F) mit
- Q = {q0, q1, q2, qf}
- X = {a, b}
- ∑ = {1}
- q0 = {q0}
- B = Leerzeichen
- F = {qf }
δ ist gegeben durch –
| Bandalphabet-Symbol | Anwesender Zustand ‚q0‘ | Anwesender Zustand ‚q1‘ | Anwesend Zustand ‚q2‘ |
|---|---|---|---|
| a | 1Rq1 | 1Lq0 | 1Lqf |
| b | 1Lq2 | 1Rq1 | 1Rqf |
Hier impliziert der Übergang 1Rq1, dass das Schreibsymbol 1 ist, das Band bewegt sich nach rechts, und der nächste Zustand ist q1. In ähnlicher Weise impliziert der Übergang 1Lq2, dass das Schreibsymbol 1 ist, das Band sich nach links bewegt und der nächste Zustand q2 ist.
Zeit- und Raumkomplexität einer Turingmaschine
Für eine Turingmaschine bezieht sich die Zeitkomplexität auf das Maß, wie oft sich das Band bewegt, wenn die Maschine für einige Eingabesymbole initialisiert wird, und die Raumkomplexität ist die Anzahl der Zellen des geschriebenen Bandes.
Die Zeitkomplexität aller sinnvollen Funktionen –
T(n) = O(n log n)
Die Raumkomplexität der TM –
S(n) = O(n)