Informatik Grundlagen – Turingmaschine und Berechenbarkeit
Karteikarten zum Thema „Informatik“ · 14 Karten · von atrio. Beispiele: Welche vier Komponenten definieren eine deterministische Turingmaschine formal? · Was…
Karten
14 KartenWelche vier Komponenten definieren eine deterministische Turingmaschine formal?
Rückseite
Eine deterministische Turingmaschine ist ein 7-Tupel (Z, Σ, Γ, δ, z0, □, F) mit Zustandsmenge Z, Eingabealphabet Σ, Bandalphabet Γ, Übergangsfunktion δ, Startzustand z0, Leerzeichen □ und Endzuständen F.
Was unterscheidet das Bandalphabet Γ vom Eingabealphabet Σ?
Rückseite
Σ ⊆ Γ gilt; Γ enthält zusätzlich das Leerzeichen □ und ggf. weitere Arbeitszeichen, die während der Berechnung auf dem Band erscheinen dürfen, aber nicht Teil der Eingabe sind.
Wie lautet die Signatur der Übergangsfunktion δ bei einer deterministischen Turingmaschine?
Rückseite
δ: Z × Γ → Z × Γ × {L, R, N} – sie bildet aktuellen Zustand und gelesenes Symbol auf neuen Zustand, zu schreibendes Symbol und Kopfbewegung (Links, Rechts, Nicht bewegen) ab.
Wann hält eine Turingmaschine in einem Endzustand an?
Rückseite
Die Maschine hält, wenn sie in einem Zustand aus F ist und für die aktuelle Konfiguration keine Übergang definiert ist – das Eingabewort wird dann akzeptiert.
Was besagt die Church-Turing-These?
Rückseite
Jede Funktion, die intuitiv als berechenbar gilt, kann von einer Turingmaschine berechnet werden – die These ist nicht beweisbar, aber allgemein akzeptiert.
Was ist eine universelle Turingmaschine (UTM)?
Rückseite
Eine UTM simuliert jede andere Turingmaschine: Sie erhält als Eingabe die Kodierung einer TM M und eines Eingabeworts w und führt die Berechnung von M auf w nach.
Wie unterscheidet sich eine nichtdeterministische Turingmaschine (NTM) von einer deterministischen?
Rückseite
Die Übergangsfunktion δ liefert eine Menge möglicher Folgekonfigurationen: δ: Z × Γ → 2^(Z × Γ × {L,R,N}); die NTM akzeptiert, wenn mindestens ein Rechenpfad in einem Endzustand endet.
Sind nichtdeterministische Turingmaschinen mächtiger als deterministische bzgl. Berechenbarkeit?
Rückseite
Nein: Jede NTM lässt sich durch eine DTM simulieren (mit exponentiellem Zeitaufwand), beide Modelle erfassen dieselbe Klasse berechenbarer Funktionen.
Was bedeutet es, dass eine Sprache entscheidbar (rekursiv) ist?
Rückseite
Es existiert eine Turingmaschine, die für jede Eingabe anhält und akzeptiert, falls das Wort in der Sprache liegt, andernfalls ablehnt – die Maschine hält also immer.
Was ist eine semi-entscheidbare (rekursiv aufzählbare) Sprache?
Rückseite
Es existiert eine Turingmaschine, die genau die Wörter der Sprache akzeptiert und anhält; für Wörter außerhalb der Sprache kann sie jedoch in eine Endlosschleife geraten.
Nenne das klassische Beispiel für ein unentscheidbares Problem.
Rückseite
Das Halteproblem: Gegeben eine TM M und Eingabe w, hält M auf w? Es gibt keine Turingmaschine, die dies für alle Paare (M, w) korrekt entscheidet.
Wie beweist man die Unentscheidbarkeit des Halteproblems?
Rückseite
Diagonalisierung: Annahme einer Entscheidermaschine H, Konstruktion einer Maschine D, die H auf sich selbst anwendet und das Gegenteil tut – Widerspruch zeigt, dass H nicht existieren kann.
Was besagt das Rice-Theorem?
Rückseite
Jede nicht-triviale semantische Eigenschaft von Turingmaschinen-sprachen (z. B. Endlichkeit, Leere, Regelmäßigkeit) ist unentscheidbar.
Wann sind zwei Turingmaschinen äquivalent?
Rückseite
Wenn sie dieselbe Sprache akzeptieren (bzw. dieselbe partielle Funktion berechnen) – also für jede Eingabe beide anhalten und akzeptieren oder beide ablehnen/endlos laufen.