This flashcard is just one of a free flashcard set. See all flashcards!
57
Beweis:
ist nicht rekursiv aufzählbar


w Eingabe für

1.) Wenn w keine gültige GN ist, liegt w in


2.) Wenn w=<M>, so ist f(w)=<M'>. M' verhält sich auf Eingabe x wie folgt:
Falls |x|=i, simuliert M' die ersten i Schritte von M auf



f ist offensichtlich berechenbar.Falls w=<M> gilt:

=> M hält nicht auf Eingabe

=>


=>

=> f(w)=<M'>


=> M hält auf Eingabe

=>


=>

=> f(w)=<M'>
