VL-01 Turing-Maschinen Flashcards
Was ist die Definition eines Problems?
Ein Problem ist eine Relation der Form: R ⊆ Σ* x Σ*
Ein Paar (x,y) liegt dabei in R, wenn y eine zulässige Ausgabe, zu Eingabe x ist
Wann ist ein Problem eine Funktion, anstatt einer Relation?
Wenn es zu jeder Eingabe eine zulässige Ausgabe gibt:
Beispiel: Nachfolger von x
Was ist ein Entscheidungsproblem?
Ein Problem, bei dem die Ausgabe ja oder nein ist (bzw. 0 oder 1)
Σ* → {0, 1}
Was ist eine Sprache?
Eine Sprache L ist eine Teilmenge von Σ, welche durch ein entsprechendes Entscheidungsproblem definiert wird.
L = f −1(1) ⊆ Σ
Wie ist eine Turingmaschine definiert?
Durch das 7-Tupel (Q, Σ, Γ, B, q0, ¯q, δ):
Q die endliche Zustandsmenge
Σ das endliche Eingabealphabet
Γ ⊃ Σ das endliche Bandalphabet
B ∈ Γ \ Σ das Leerzeichen (Blank, in Bildern □)
q0 ∈ Q der Anfangszustand
¯q ∈ Q der Endzustand
δ : (Q \ {¯q}) × Γ → Q × Γ × {R, L, N}
die Zustands¨uberf¨uhrungsfunktion
Wann akzeptiert eine Turingmaschine ein Entscheidungsproblem?
Wenn das Ausgabewort mit einer 1 beginnt
Was ist eine rekursive Funktion?
Eine Funktion f : Σ* → Σ* heisst rekursiv (T-berechenbar),
wenn es eine TM gibt, die aus der Eingabe x
den Funktionswert f (x) berechnet.
Was ist eine rekursive Sprache?
Eine Sprache L ⊆ Σ* heisst rekursiv (T-entscheidbar),
wenn es eine TM gibt, die für alle Eingaben terminiert und
die Eingabe w genau dann akzeptiert, wenn w ∈ L ist.
Was ist die Konfiguration einer TM?
Eine Konfiguration einer TM ist ein String αqβ, mit q ∈ Q und
α, β ∈ Γ∗.
Bedeutung: auf dem Band steht αβ eingerahmt von Blanks, der
Zustand ist q, und der Kopf steht über dem ersten Zeichen von β.
Wie kann man den Zustandsraum einer TM erweitern?
Durch das verwenden von mehreren Spuren wird der Zustandsraum um|Γ|^k vergrößert
