This flashcard is just one of a free flashcard set. See all flashcards!
47
Beweis: Sprachen 
und 
rekursiv aufzählbar, so auch 
rekursiv aufzählbar
und rekursiv aufzählbar, so auch rekursiv aufzählbarBeweis anders, als bei anderen Sätzen, da 
Eingabe evtl. akzeptiert, M dies aber nie feststellen kann, da 
evtl. nicht terminiert ( und erkennen und nur)
=> verwende parallele Simulation der beiden TMn (statt einer sequentiellen)
- M verwendet zwei Bänder: auf einem wird auf dem anderen simuliert
- M merkt sich in ihrem Zustand, den momentanen Zustand von und
- pro Rechenschritt wird abwechselnd eine Rechenschritt von oder simuliert (ein bit gibt an, welche TM im aktuellen Rechenschritt simuliert wird)
=> sichergestellt, dass M akzeptiert, falls oder akzeptieren
Eingabe evtl. akzeptiert, M dies aber nie feststellen kann, da evtl. nicht terminiert ( und erkennen und nur)=> verwende parallele Simulation der beiden TMn (statt einer sequentiellen)
- M verwendet zwei Bänder: auf einem wird
auf dem anderen simuliert- M merkt sich in ihrem Zustand, den momentanen Zustand von
und - pro Rechenschritt wird abwechselnd eine Rechenschritt von
oder simuliert (ein bit gibt an, welche TM im aktuellen Rechenschritt simuliert wird)=> sichergestellt, dass M akzeptiert, falls
oder akzeptieren 