Warum ist diese Aussage falsch?

Question 1

Für jede Turing-Maschine T ist die Sprache L(T) genau dann entscheidbar, wenn T für jede Eingabe hält.

Question 2

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.

oswald · Answer 1 · 2022-02-17T08:33:51+0000

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.

1 Antwort