This flashcard is just one of a free flashcard set. See all flashcards!

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