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 ₀ , 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}.

• q₀ 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 ₀ , B, F) mit

• Q = {q ₀ , q ₁ , q ₂ , q _f }
• X = {a, b}
• ∑ = {1}
• q ₀ = {q ₀ }
• 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 ₁ , 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 ₂ , 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)