Für jede Turing-Maschine T ist die Sprache L(T) genau dann entscheidbar, wenn T für jede Eingabe hält.
Warum ist diese Aussage falsch?
Sei T eine Turingmaschine, die für jede Eingabe hält.
Man kann eine Turingmaschine T' konstruieren, die bei Eingabe von Wörtern w ∈ L(T) akzeptierend hält und auf Wörtern w' ∉ L(T) nicht hält.
Wegen L(T') = L(T) ist L(T') entscheidbar. Aber T' hält nicht auf allen Eingaben.
Ein anderes Problem?
Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos