Gegeben sei das folgende Problem:
Problem: TM-gleiche-Anz-as-bs
Gegeben: Turingmaschine M
Frage: Erzeugt M bei jeder Eingabe, bei der sie anhält, eine Ausgabe w, bei der die Anzahl a’s der Anzahl b’s entspricht (d.h. #a(w) = #b(w))?
a) Zeigen Sie mit dem Satz von Rice, dass TM-gleiche-Anz-as-bs nicht entscheidbar ist.
b) zeigen, dass TM-gleiche-Anz-as-bs auch nicht semientscheidbar ist.
