This flashcard is just one of a free flashcard set. See all flashcards!
32
Beweis: L unentscheidbar =>
unentscheidbar

Widerspruchsbeweis:
- nehme an es ex. TM
, die
entscheidet
=>
hält auf Eingabe w, gdw. 
- Konstruiere TM M, die
als Unterprogramm aufruft:
M startet
auf der vorliegenden Eingabe
M negiert Ausgabe von
=> M entscheidet offensichtlich L.
Widerspruch zur Unentscheidbarkeit von L.
=> Komplement der Diagonalsprache ist unentscheidbar
- nehme an es ex. TM


=>


- Konstruiere TM M, die

M startet

M negiert Ausgabe von

=> M entscheidet offensichtlich L.
Widerspruch zur Unentscheidbarkeit von L.
=> Komplement der Diagonalsprache ist unentscheidbar