|
|
| 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!
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Jefferson1992: 30.05.2015 14:57.
|
|
