This flashcard is just one of a free flashcard set. See all flashcards!
49
Beweis: Sind 
und 
rekursiv aufzählbar, so ist L rekursiv.
und rekursiv aufzählbar, so ist L rekursiv. Beispiel: Halteproblem
H ist rekursiv aufzählbar, wäre
auch rekursiv aufzählbar, dann wäre H rekursiv 
Maschinen, die L bzw. 
erkennen.
TM M' entscheidet L durch parallele Simulation von
und 
auf Eingabe w:
- M' akzeptiert w, sobald M akzeptiert
- M' verwirft w, sobald akzeptiert
=> Terminierung: Da entweder
oder 
sicher
Folge aus dem Lemma: L ist nicht rekursiv gdw. mind. eine der beiden Sprache L oder nicht rekursiv aufzählbar ist
H ist rekursiv aufzählbar, wäre
auch rekursiv aufzählbar, dann wäre H rekursiv Maschinen, die L bzw. erkennen.TM M' entscheidet L durch parallele Simulation von
und auf Eingabe w:- M' akzeptiert w, sobald M akzeptiert
- M' verwirft w, sobald
akzeptiert=> Terminierung: Da entweder
oder sicherFolge aus dem Lemma: L ist nicht rekursiv gdw. mind. eine der beiden Sprache L oder
nicht rekursiv aufzählbar ist