Turing Maschine Sprache und ihr komplement

Question

Frage:

Text erkannt:

Behauptung
richtig falsch
Für jede Sprache \( A \) gilt: Falls eine TM \( M \) existiert mit \( L(M)=A \), dann gibt es eine TM \( M^{\prime} \) mit \( L\left(M^{\prime}\right)=\bar{A} \).

Stimmt das?

Code:

Ich bin der Meinung dass das richtig ist mein Partner sagt nein, aber wir beide können unsere Argumente verstehen und wissen jetzt nicht wer recht hat :D

Answer 1

Die Aussage stimmt nicht. Eine Beweisidee findest du unter wikipedia://Halteproblem.

Würde die Aussage stimmen, dann wäre jede semientscheidbare Sprache auch entscheidbar.