0 Daumen
224 Aufrufe

Frage:

blob.png

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

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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

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

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community