CoboCards App FAQ & Wünsche Feedback
Sprache: Deutsch Sprache
Kostenlos registrieren  Login

Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

Alle Oberthemen / Mathematik / Berechenbarkeit / Berechenbarkeit I
47
Beweis: Sprachen und rekursiv aufzählbar, so auch rekursiv aufzählbar
Beweis 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
Neuer Kommentar
Karteninfo:
Autor: hemag
Oberthema: Mathematik
Thema: Berechenbarkeit
Veröffentlicht: 16.03.2010

Abbrechen
E-Mail

Passwort

Login    

Passwort vergessen?
Deutsch  English