Entscheidbarkeit, wenn A und Komplement semi entscheidbar

Neue Frage »

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!
 
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »