Turingmaschine Einführung

Anmerkungen

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)

Werbungen

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.