Turing Maschinen I Flashcards
Σ*
Kleenesche Abschluss von Σ, enthält alle Wörter über Σ
Problem als Relation R ⊆ Σ* x Σ’*
Ein Paar (x,y) liegt in R, wenn y eine Ausgabe zur Eingabe x ist
Problem als Funktion f : Σ* -> Σ’*
Suche Ausgabe f(x) ϵ Σ’* zur Eingabe x ϵ Σ*
Entscheidungsproblem-Form
f : Σ* -> {0,1}
L=f^-1 (1) ⊆ Σ*
Die zu dem f definierten Entscheidungsproblem gehörende Sprache
Turingmaschine Definition
7-Tupel (Q, Σ, Γ, B, q0, q-, δ)
Q
endliche Zustandsmenge
Σ
endliche Eingabealphabet
Γ ⊃ Σ
endliche Bandalphabet
B ϵ Γ\Σ
Blank
q0
Anfangszustand
q-
Endzustand
δ : ( Q{q-} ) x Γ -> Q x Γ x {R,L,N}
Zustandsüberführungsfunktion
Ende der Berechnung der TM
TM stoppt, wenn sie den Endzustand erreicht. Ausgabewort vom Band beginnend mit Kopfposition lesen.
M entscheidet L, wenn…
M auf jeder Eingabe hält und M genau die Wörter aus L akzeptiert.
Wenn TM eine Sprache entscheidet, so muss sie immer
halten
Eine Funktion f : Σ* -> Σ* heißt rekursiv(Turing-berechenbar), wenn…
es eine TM gibt, die aus der Eingabe x den Funktionswert f(x) berechnet.
Eine Sprache L ⊆ Σ* heißt rekursiv(Turing-entscheidbar), wenn…
es eine TM gibt, die für alle Eingabe terminiert und die Eingabe w genau dann akzeptiert, wenn w ϵ L ist.
Konfiguration einer TM
String αqβ mit qϵQ und α, β ϵ Γ*
α’q’β’ direkte Nachfolgekonfiguration von αqβ, falls…
α’q’β’ in einem Rechenschritt aus αqβ entsteht.
α’‘q’‘β’’ Nachfolgekonfiguration von αqβ, falls…
α’‘q’‘β’’ in endlich vielen Rechenschritten aus αqβ entsteht.
k-spurige TM
eine TM, bei der das Band in k Spuren eingeteilt ist. Der Kopf kann k Zeichen gleichzeitig lesen.
Speicher im Zustandsraum der TM erweitern
Qneu = Q x Γ^k
Bandalphabet von Mehrspurmaschinen erweitern
Γneu = Γ ∪ Γ^k
Laufzeit
Anzahl von Zustandsübertragungen bis zur Terminierung
Speicherbedarf
Anzahl von Bandzellen, die während der Berechnung besucht werden
M berechnet f : Σ* -> Σ’*, wenn…
für jedes Wort wϵ Σ* M auf Eingabe w terminiert und dabei die Ausgabe f(w) hat.
