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
![](https://images.gutefrage.net/media/default/user/14_nmmslarge.png?v=1551279448000)
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