This flashcard is just one of a free flashcard set. See all flashcards!
31
Beweis: D ist nicht rekursiv
Widerspruchsbeweis:
- nehme an D sei rekursiv
- dann gibt es TM
, die D entscheidet
- wende
auf 
an
1.Fall:
liegt in D
- dann aktzeptiert die Eingabe , weil die Sprache entscheidet
- Wegen der Definition von D kann aber nicht in D liegen 
2.Fall: liegt nicht in D
- dann verwirft die Eingabe , weil die Sprache entscheidet
- Wegen der Definition von D muss aber in D liegen
- nehme an D sei rekursiv
- dann gibt es TM
, die D entscheidet- wende
auf an1.Fall:
liegt in D- dann aktzeptiert
die Eingabe , weil die Sprache entscheidet- Wegen der Definition von D kann
aber nicht in D liegen 2.Fall:
liegt nicht in D- dann verwirft
die Eingabe , weil die Sprache entscheidet- Wegen der Definition von D muss
aber in D liegen 