| Jefferson1992 |
Entscheidbarkeit, wenn A und Komplement semi entscheidbar
Hallo,
Ich soll die Äquivalenz zwischen A entscheidbar und A und Komplement A semientscheidbar zeigen
Habe so angefangen:
Wenn L entscheidbar ist, gibt es ein X aus L, welches berechenbar ist. Man definiert ein X´, welches Semientscheidbar ist mit dem Inhalt r.
Dann gilt:
X´ Komplement L(r)={1, falls xL(r)=1 ; undefiniert, falls xL(r)=0
X´ Komplement L(r)={1, falls xL(r)=0 ; undefiniert, falls xL(r)=1
Da wir wissen, dass wenn XL entscheidbar ist, auch X Komplement L entscheidbar ist, heißt das, dass X´L und X´Komplement L berechenbar sind und somit L semientscheidbar und Komplement L semientscheidbar aus L entscheidbar folgen.
Leider komme ich mit dem Code nicht ganz klar, hoffe man kann es trotzdem entziffern.
Mir kommt dieser Beweis sehr schwammig vor und die andere Richtung fehlt noch,d a fehlt mir leider die Idee..
Danke! |
