VL-04 Unentscheidbarkeit I Flashcards
Gibt es unentscheidbare Probleme?
Ja, denn es gibt mehr Probleme als Turingmaschinen
Was ist eine abzählbare Menge?
Eine Menge ist abzählbar, sie leer ist oder es eine surjektive Funktion gibt c: N → M
- Die Elemente einer Menge können also durchnummeriert werden
Nenne Beispiele für abzählbar Mengen
- Natürlichen Zahlen
- Ganzen Zahlen
- Kanonische Aufzählung der Gödelnummern
Nenne ein Beispiel für eine überabzählbare Menge
- Potenzmenge von N
Warum gibt es unendscheidbare Probleme?
- Die Menge der Gödelnummern ist abzählbar (Kanonische Aufzählung)
- Die Menge der Entscheidungsprobleme entspricht der Potenzmenge von {0,1}* und ist somit überabzählbar (Beweis via Diagonalisierung)
Nenne unentscheidbare Problem
- Diagonalsprache
- Komplement der Diagonalsprache
- Halteproblem
Was ist die Diagonalsprache?
L = { w| w_i = w und M_i akzeptiert w nicht}
w_i und M_i jeweils das i-te Wort, die i-te TM in kanonischer Aufzählung
Wie funktioniert die Unterprogrammtechnik?
Sei L’ eine bekannte unentscheidbare Sprache. Wenn es möglich ist die Sprache L als Unterprogramm auszuführen und somit L’ entscheiden, ist folglich L auch unentscheidbar.
Welche Aussage lässt sich über das Komplement einer Sprache treffen bezüglich der Entscheidbarkeit.
L ist entscheidbar <-> Komplement von L ist entscheidbar
L ist unentscheidbar <-> Komplement von L ist unentscheidbar
Wie ist das Halteproblem definiert?
H = {<M>w | M hält auf die Eingabe von w}</M>
Wie lautet der Beweis das H nicht entscheidbar ist?
Unterprogrammtechnik mit Komplement der Diagonalsprache:
M_nDiag mit Eingabe: w
- Finde w_i = w und M_i
- M_H als Unterprogramm mit: <M_i>w_i
- Wenn M_H akzeptiert, simuliere <M_i> mit Eingabe w_i mit U und übernehme das Akzeptanzverhalten von U
- Wenn M_H verwirft, verwirft M_nDiag</M_i></M_i>
Somit entscheidet das Halteproblem das Komplement der Diagonalsprache, was bekanntermaßen unentscheidbar ist
