Entscheidbarkeit, wenn A und Komplement semi entscheidbar |
30.05.2015, 14:52 | Auf diesen Beitrag antworten » |
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! |
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|