This flashcard is just one of a free flashcard set. See all flashcards!

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