0 Daumen
90 Aufrufe

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.

von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
0 Antworten

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community