Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!

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