VL-05 Unentscheidbarkeit II

Question 1

Wie lässt sich beweisen, dass Hϵ unentscheidbar ist?

Answer 1

Unterprogrammtechnik:
- Erzeuge eine TM M_w, welche als erstes w auf das Band schreibt
- Löse Hϵ für <M_w> und ϵ
- Damit löst Hϵ das Halteproblem für <M>w</M></M_w>

Question 2

Was besagt der Satz von Rice?

Answer 2

Alle nicht-trivialen Aussagen über TM sind unentscheidbar.

Es sei R die Menge der von TMen berechenbaren partiellen Funktionen.
Es sei S eine Teilmenge von R mit ∅ ⊂ S ⊂ R mit S != ∅ und S != R.
Dann ist die Sprache
L(S) = { ⟨M⟩ | M berechnet eine Funktion aus S }
nicht entscheidbar.

Question 3

Was sind die Abschlusseigenschaften von entscheidbaren Sprachen?

Answer 3

Entscheidbare Sprachen sind abgeschlossen unter Komplement, Vereinigung und Durchschnitt

Question 4

Ist der der Satz von Rice auf konkrete Instanzen von Problemen anwendbar?

Answer 4

Nein