0 Daumen
303 Aufrufe
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?

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community