This flashcard is just one of a free flashcard set. See all flashcards!
50
Sind rekursiv aufzählbare Sprachen abgeschlossen gegen ihr Komplement?
Nein!
Beweis:
L rekursiv aufzählbar =>
rekursiv aufzählbar => L rekursiv => alle rekursiv aufzählbaren Sprachen sind rekursiv (Widerspruch!)
Beweis:
L rekursiv aufzählbar =>
rekursiv aufzählbar => L rekursiv => alle rekursiv aufzählbaren Sprachen sind rekursiv (Widerspruch!)