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
44
semi-entscheidbar/rekursiv aufzählbar
Eine Sprache L ist genau dann semi-entscheidbar, wenn L rekursiv aufzählbar ist

Beweis:

"<=": Konstruiere aus einem Auzähler für L eine TM M, die L erkennt
- zusätzliche Spur, die Rolle des Drucker übernimmt
- wenn neues Wort enummeriert wurde, vergleicht es M mit w
- falls wird w irgendwann enummeriert und von M akzeptiert
- falls wird w nicht akzeptiert, aber M hält auch nicht

"=>": Konstruiere aus eine TM M, die L erkennt einen Aufzähler
- führe i Schritte von M auf Wörtern aus (kanonische Reihenfolge)
- wird ein Wort akzeptiert, drucke es aus
- falls wird L nach endlich vielen Schritten gedruckt
- falls wird w nie gedruckt


Neuer Kommentar
Karteninfo:
Autor: hemag
Oberthema: Mathematik
Thema: Berechenbarkeit
Veröffentlicht: 16.03.2010

Abbrechen
E-Mail

Passwort

Login    

Passwort vergessen?
Deutsch  English