Semi-Entscheidbarkeit & Rekursive Aufzählbarkeit Flashcards
M erkennt L, wenn…
M jedes Wort aus L akzeptiert und kein Wort akzeptiert, das nicht in L enthalten ist.
L heißt semi-entscheidbar, wenn…
eine TM existiert, die die Sprache L erkennt.
Das Halteproblem ist… (entscheidbar/nicht entscheidbar/semi-entscheidbar)
nicht entscheidbar, aber semi-entscheidbar.
Definition: Ein Aufzähler für eine Sprache L⊆Σ* ist…
eine Variante der TM mit einem angeschlossenen Drucker.
Der Drucker des Aufzählers ist..
ein zusätzliches Ausgabeband, auf dem sich der Kopf nur nach rechts bewegen kann und auf dem nur geschrieben wird.
Ein Aufzähler funktioniert so:
- wird mit dem leerem Arbeitsband gestartet und gibt mit der Zeit alle Wörter in L auf dem Drucker aus
- Die ausgegebene Wörter immer durch ein Trennzeichen separiert, das nicht in Σ enthalten ist
- Der Aufzähler druckt ausschliesslich Wörter in L.
Definition: Wenn es für L einen Aufzähler gibt, so heißt L…
rekursiv aufzählbar.
L ist rekursiv aufzählbar genau dann, wenn L … ist.
semi-entscheidbar
Durchschnitt: Wenn L1 und L2 entscheidbar, dann L1 ∩ L2 ist …
entscheidbar
Durchschnitt: Wenn L1 und L2 rekursiv aufzählbar, dann L1 ∩ L2 ist…
rekursiv aufzählbar
Vereinigung: Wenn L1 und L2 entscheidbar, dann L1 ∪ L2 ist …
entscheidbar
Wenn L1 und L2 rekursiv aufzählbar, dann L1 ∪ L2 ist …
rekursiv aufzählbar
Wenn sowohl L⊆Σ* als auch ihr Komplement not L := Σ* \ L rekursiv aufzählbar, so ist L …
entscheidbar
Wenn L entscheidbar, ihr Komplement not L ist..
entscheidbar
Wenn L rekursiv aufzählbar, ihr Komplement not L ist nicht unbedingt..
rekursiv aufzählbar
Graphzusammenhang, Hamiltonkreis sind … Sprachen, wobei L … und not L ist ….
entscheidbare, rekursiv aufzählbar, rekursiv aufzählbar
Beispiele von entscheidbare Sprachen, wo sowohl L als auch not L rekursiv aufzählbar
Graphzusammenhang, Hamiltonkreis
H, H_epsilon, not D sind… Sprachen, mit ….. Komplement
rekursiv aufzählbar, nicht rekursiv aufzählbarem
not H, not H_epsilon, D sind… Sprachen, mit ….. Komplement
nicht rekursiv aufzählbare, rekursiv aufzählbarem
Beispiele von rekursiv aufzählbar Sprachen mit nicht rekursiv aufzählbarem Komplement
H, H_epsilon, not D
Beispiele von nicht rekursiv aufzählbar Sprachen mit rekursiv aufzählbarem Komplement
not H, not H_epsilon, D
Unentscheidbare Sprachen mit unentscheidbarem Komplement
H_tot, not H_tot
H_tot ist eine … Sprache mit … Komplement
nicht rekursiv (aufzählbare), nicht rekursiv (aufzählbarem)
Definition Reduktion zweier Sprachen
Seien L1 und L2 zwei Sprachen über einem Alphabet Σ. Dann heißt L1 auf L2 reduzierbar, wenn es eine berechenbare Funktion f : Σ* -> Σ* existiert, so dass für alle x ϵ Σ* gilt: x ϵ L1 <=> f(x) ϵ L2
Seien L1 und L2 zwei Sprachen über einem Alphabet Σ. Wenn es eine berechenbare Funktion f : Σ* -> Σ* existiert, so dass für alle x ϵ Σ* gilt: x ϵ L1 <=> f(x) ϵ L2 gilt, dann ist L1 auf L2 ….
reduzierbar
Definition Reduktion
Ein Algorithmus, der die Instanzen eines Startproblems als Spezialfälle eines Zielproblems formuliert.
Wenn L1 ≤ L2 und L2 rekursiv aufzählbar, so ist L1…
rekursiv aufzählbar
Wenn L1 ≤ L2 und L1 nicht rekursiv aufzählbar, so ist L2…
nicht rekursiv aufzählbar
Definition Totales Halteproblem
{Gödelnummer von M | M hält auf jeder Eingabe}
Wenn eine Sprache ist unentscheidbar, aber rekursiv aufzählbar, dann ihr Komplement ist…
nicht rekursiv aufzählbar
Htot ist…
nicht rekursiv aufzählbar
Not Htot ist…
nicht rekursiv aufzählbar
Aus A ≤ not A folgt dass…
Not A ≤ A
Wenn L1 ≤ L2 und L2 entscheidbar, dann ist L1…
L1 entscheidbar
Wenn L1 ≤ L2 und L1 nicht entscheidbar, dann L2 ist…
Nicht entscheidbar
