Ein Beweis von Entscheidbar (Berechenbarkeit und Komplexität)?
Ich würde gern wissen, wie man diese Aussage "Wenn X semi-entscheidbar ist und Y entscheidbar ist, dann ist X \ Y semi-entscheidbar" zeigen kann.
Kann jmd bitte einmal beweisen, der gut auf Entscheidbarkeit ist?
1 Antwort
Beweisidee:
x element X\Y ist Äquivalent dazu, dass x in X und x nicht in Y ist.
Prüfe also zuerst, ob x in Y ist. Falls ja, ist x nicht in X\Y. Falls nein, musst du prüfen ob x in X ist. Dieser Entscheidungsprozess ist semi-entscheidbar (warum das genau der Fall ist, überlasse ich dir)
Woher ich das weiß:Studium / Ausbildung – Mache derzeit meinen Mathematik Master