Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
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!)